ความซับซ้อนเชิงการคำนวณ

แนวคิดในวิทยาการคอมพิวเตอร์

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

คลาสความซับซ้อน

คลาสความซับซ้อน

แอนิเมชันแสดงพื้นที่ความซับซ้อนของปัญหาทั้งหมด

ภาพแสดงพื้นที่ปัญหา P

คลาสความซับซ้อน -->	P (Polynomial Time)
ความหมาย	แก้ได้อย่างรวดเร็วและมีประสิทธิภาพ
ตัวอย่าง	การเรียงลำดับรายการ
อุปมา	"การจัดเรียงเอกสารตามลำดับตัวอักษร"
สาระสำคัญ	ถือเป็นปัญหา "ง่าย" ในแง่การคำนวณ

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

ภาพแสดงพื้นที่ปัญหา P และ NP

คลาสความซับซ้อน -->	NP (Non-deterministic Polynomial Time)
ความหมาย	ตรวจสอบคำตอบได้ แต่หาคำตอบใหม่ได้ยาก
ตัวอย่าง	ตรวจสอบว่าคำตอบของปริศนา Sudoku ถูกต้องหรือไม่
อุปมา	"ค้นหาเอกสารเฉพาะที่ข้อมูลไม่ครบ"
สาระสำคัญ	การตรวจสอบคำตอบ "ง่าย" แต่การหาคำตอบใหม่นั้นยาก

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

ภาพแสดงพื้นที่ปัญหา P, NP และ NP-Complete

คลาสความซับซ้อน -->	NP-Complete
ความหมาย	ยากที่สุดใน NP และพิเศษตรงที่แก้ปัญหา NP ทั้งหมดได้
ตัวอย่าง	ปัญหาพนักงานขายเดินทาง
อุปมา	"ต่อจิ๊กซอว์ซับซ้อน ตรวจสอบง่ายแต่แก้ยาก"
สาระสำคัญ	ยังไม่มีวิธีแก้ที่มีประสิทธิภาพ แต่ถ้าพบก็จะแก้ปัญหา NP ทั้งหมดได้

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

ภาพแสดงพื้นที่ปัญหา P, NP, NP-Complete และ NP-Hard

คลาสความซับซ้อน -->	NP-Hard
ความหมาย	ยากเท่ากับ NP-Complete หรือยากกว่า
ตัวอย่าง	การจัดตารางงานที่เหมาะสมที่สุดแบบซับซ้อน ซึ่งตรวจสอบไม่ได้
อุปมา	"จัดเวลาประชุมที่ดีที่สุดภายใต้เงื่อนไขมาก และตรวจสอบได้ยาก"
สาระสำคัญ	อาจแก้ไม่ได้จริงในทางปฏิบัติ

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

ไดอะแกรมแสดงคำถามการวิจัยอมตะว่า P=NP หรือไม่

แนวคิดในวิทยาการคอมพิวเตอร์