204512/บรรยาย 2

Divide and Conquer Algorithms

หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้ 1. แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น 2. ทำการแก้ปัญหาย่อยเหล่านี้ด้วยวิธีการที่คล้ายกัน 3. คำตอบสุดท้ายหาได้จากการสรุปคำตอบทั้งหมดของทุกปัญหาย่อย

ดังจะเห็นได้จากปัญหาทั้งในชีวิตประจำวัน และปัญหาทางทฤษฎีคอมพิวเตอร์ สามารถเปรียบเทียบกรรมวิธี Divide and Conquer Algorithm กับ Lagacy Algorithm ได้ว่ามีประสิทธิ์ภาพต่างกันมากน้อยเพียงใด ซึ่งวิธีที่เปรียบเทียบเป็นที่นิยมโดยทั่วไปคือการหา Big O Notation มาเปรียบเทียบกัน

---