แก้ไขปัญหาที่ยาก

ขั้นตอนวิธีแบ่งแยกและเอาชนะเป็นวิธีในการแก้ปัญหาที่ยากบางปัญหาได้อย่างดี เช่น ปัญหาหอคอยแห่งฮานอย ในการที่จะแก้ปัญหานี้ สิ่งที่ต้องการมีเพียงวิธีการแบ่งปัญหาเป็นปัญหาย่อย และวิธีการในการประกอบคำตอบของปัญหาย่อยมาเป็นคำตอบของปัญหาดั้งเดิม

ประสิทธิภาพของขั้นตอนวิธี

ขั้นตอนวิธีแบ่งแยกและเอาชนะมักจะช่วยในการสร้างขั้นตอนวิธีที่มีประสิทธิภาพ เช่น การคูณอย่างรวดเร็วด้วยขั้นตอนวิธีของคาราซูบา การเรียงลำดับอย่างรวดเร็วด้วยการเรียงลำดับแบบเร็วหรือการเรียงลำดับแบบผสาน การคูณเมทริกซ์ด้วยขั้นตอนวิธีของสแตรสเซน หรือการคำนวณการแปลงฟูรีเยไม่ต่อเนื่องแบบเร็ว

ในตัวอย่างทั้งหมดที่กล่าวมา ขั้นตอนวิธีแบ่งแยกและเอาชนะช่วยในการลดความซับซ้อนในการคำนวณได้อย่างมีนัยยะสำคัญ ยกตัวอย่างเช่นการเรียงลำดับแบบผสาน ซึ่งคำนวณกรณีฐานได้ในเวลาคงที่ และการแบ่งและรวมปัญหาในแต่ละครั้งใช้เวลา O ( n ) {\displaystyle O(n)} เมื่อ n คือขนาดปัญหาที่กำลังแก้ในขณะนั้น จะได้ว่าประสิทธิภาพโดยรวมของขั้นตอนวิธี คือ O ( n log ⁡ n ) {\displaystyle O(n\log n)} ซึ่งดีกว่าการเรียงลำดับแบบอื่น ๆ ที่คิดค้นขึ้นมาก่อนหน้านั้น ซึ่งส่วนใหญ่จะใช้เวลา O ( n 2 ) {\displaystyle O(n^{2})}