เวลาพหุนามการย่อคือ?

2024 ผู้เขียน: Fiona Howard | [email protected]. แก้ไขล่าสุด: 2024-01-10 06:43

ในทฤษฎีความซับซ้อนเชิงคำนวณ การลดเวลาพหุนามคือ วิธีการแก้ปัญหาหนึ่งโดยใช้วิธีอื่น การลดเวลาพหุนามมักใช้ในทฤษฎีความซับซ้อนเพื่อกำหนดทั้งคลาสความซับซ้อนและปัญหาที่สมบูรณ์สำหรับคลาสเหล่านั้น …

อะไรถือเป็นเวลาพหุนาม

อัลกอริธึมกล่าวกันว่าเป็นเวลาพหุนาม ถ้าเวลาทำงานของมันถูกขอบเขตบนด้วยนิพจน์พหุนามในขนาดของอินพุตสำหรับอัลกอริทึม นั่นคือ T(n)=O(n^k) สำหรับค่าคงที่ที่เป็นบวก k

คุณจะรู้ได้อย่างไรว่าสิ่งใดเป็นพหุนามพหุนาม

3 คำตอบ. อัลกอริธึมเป็นแบบพหุนาม (มีเวลาทำงานแบบพหุนาม) ถ้าสำหรับ k, C>0 บางตัว เวลาทำงานของอินพุตขนาด n จะอยู่ที่ Cnk มากที่สุด ในทำนองเดียวกัน อัลกอริธึมเป็นพหุนามถ้าสำหรับ k>0 บางตัว เวลาทำงานของอินพุตขนาด n คือ O(nk)

จะเกิดอะไรขึ้นหากลดเวลาแบบเอ็กซ์โปเนนเชียลได้

หากอนุญาตให้ลดเวลาแบบเอกซ์โปเนนเชียล มันสามารถแก้ปัญหาเดิมได้อย่างเต็มที่และสร้างตัวอย่างปัญหาเล็กๆ น้อยๆ ของเป้าหมาย ซึ่งหมายความว่าทุกปัญหาใน NP จะลดให้ทุก ปัญหาอื่นๆ จากการลดลงดังกล่าว ดังนั้นทุกปัญหาใน NP จึงสมบูรณ์ NP สำหรับการลดเวลาแบบเอ็กซ์โปเนนเชียล

อัลกอริทึมเลขชี้กำลังคืออะไร

อัลกอริธึมกล่าวกันว่าเป็นเวลาเลขชี้กำลัง ถ้า T(n) อยู่บนขอบบนด้วย 2^{poly( )} โดยที่ poly(n) คือพหุนามบางตัวใน n อย่างเป็นทางการมากขึ้น อัลกอริทึมเป็นเวลาชี้แจงถ้า T(n) ถูกล้อมรอบด้วย O(2^{nk) สำหรับค่าคงที่บางค่า k. Ref:Wiki}