ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบ่งแยกและเอาชนะ"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ลไม่มีความย่อการแก้ไข |
ลไม่มีความย่อการแก้ไข |
||
บรรทัด 3:
กลวิธีนี้เป็นพื้นฐานของขั้นตอนวิธีที่มีประสิทธิภาพจำนวนมากมาย เช่น [[ขั้นตอนวิธีการเรียงลำดับ|การเรียงลำดับ]] ([[การเรียงลำดับแบบเร็ว]] [[การเรียงลำดับแบบผสาน]]) [[การคูณเลขขนาดใหญ่]] ([[ขั้นตอนวิธีของคาราซูบา]]) การคำนวณ[[การแปลงฟูรีเยไม่ต่อเนื่อง]]
ในอีกด้าน การที่จะเข้าใจและสามารถออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะได้นั้นต้องใช้ทักษะในระดับหนึ่ง เพราะในการที่จะทำให้ขั้นตอนวิธีมีการเรียกซ้ำต่อไปได้เรื่อย ๆ ในเวลาที่ต้องการ อาจจะต้องหาวิธีสร้างปัญหาย่อยซึ่งซับซ้อนและยากมาก นอกจากนี้ การสร้างขั้นตอนวิธีแบ่งแยกและเอาชนะนั้นไม่มีขั้นตอนอย่างเป็นระบบ ตัวอย่างความซับซ้อนจากการวิเคราะห์หรือออกแบบขั้นตอนวิธีแบ่งแยกและเอาชนะ เช่น การคำนวณหา[[จำนวนฟีโบนัชชี]]ในเวลา <math>O(\log n)</math> โดยใช้
ขั้นตอนวิธีแบ่งแยกและเอาชนะ ยังรวมไปถึงขั้นตอนวิธีที่แต่ละปัญหาแบ่งออกเป็นปัญหาย่อยหลายส่วน แต่กลับใช้คำตอบหรือคำนวณคำตอบจากเพียงแค่ปัญหาย่อยเดียวเท่านั้น เช่น [[การค้นหาแบบทวิภาค]]บน[[แถวลำดับ]]ที่เรียงแล้ว (หรือขั้นตอน[[วิธีแบ่งครึ่ง]] สำหรับ[[การหาคำตอบของราก]]ใน[[การวิเคราะห์เชิงจำนวน]])<ref name=CLR>Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, ''Introduction to Algorithms'' (MIT Press, 2000).</ref> หากนิยามของขั้นตอนวิธีนี้รวมไปถึงขั้นตอนวิธีที่มีเพียงปัญหาย่อยเดียวด้วย อาจทำให้ทุก ๆ ขั้นตอนวิธีที่มีการเรียกซ้ำหรือมีวงวนกลายเป็น "การแบ่งแยกและเอาชนะ" ไปเสียหมด บางคนจึงนับว่าขั้นตอนวิธีจะเป็น "การแบ่งแยกและเอาชนะ" ก็ต่อเมื่อมีการแบ่งปัญหาออกเป็นปัญหาย่อย 2 ส่วนหรือมากกว่าเท่านั้น<ref>Brassard, G. and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.</ref> และเรียก "การลดและเอาชนะ" (decrease and conquer) สำหรับขั้นตอนวิธีที่มีเพียงปัญหาย่อยเดียวแทน<ref>Anany V. Levitin, ''Introduction to the Design and Analysis of Algorithms'' (Addison Wesley, 2002).</ref>
| |||