ผลต่างระหว่างรุ่นของ "พี (ความซับซ้อน)"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
|||
บรรทัด 10:
* การเพิ่มขนาดของอินพุตเป็นสองเท่าส่งผลให้เวลาการทำงานโตขึ้นเป็นค่าคงที่เท่านั้น (ในแง่นี้ให้เปรียบเทียบกับฟังก์ชันที่เป็น exponential) ซึ่งการเพิ่มขนาดของอินพุตเป็นสองเท่าอาจจะทำให้เวลาการทำงานโตขึ้นเป็นกำลังสองหรือมากกว่านั้น
* ฟังก์ชันพหุนามมีสมบัติปิดภายใต้ composition นั่นก็คือ หากเรามีอัลกอริทึม A ที่ทำงานรวดเร็ว (เป็นฟังก์ชันพหุนามกับขนาดของอินพุต) และอัลกอริทึม B สามารถเรียกใช้อัลกอริทึม A เพื่อทำงานได้ หากเรารู้ว่า B เรีัยกใช้ A เป็นจำนวนครั้งที่เป็นฟังก์ชันพหุนาม เวลาการทำงานรวมก็จะยังเป็นฟังก์ชันพหุนามอยู่ หรือหากจะพูดให้เป็นทางการก็คือ <math>P^P =P </math> (ปัญหาที่อยู่ในพี มีสมบัติปิดภายใต้การเรียกใช้ออราเคิล) สมบัตินี้ทำให้เราสามารถออกแบบอัลกอริทึมที่มีประสิทธิภาพโดยการมองอีกอัลกอริทึมหนึ่งเป็นกล่องดำ (Black Box) ได้
== ความสัมพันธ์กับกลุ่มอื่นๆ ==
| |||