ที่จะช่วยเพิ่มประสิทธิภาพการทำงานของโปรแกรมที่เราเขียนมา โดยประสิทธิภาพที่จะช่วยคือในด้านการใช้หน่วยความจำที่น้อยลง
แต่ทำให้สามารถประมวลผลได้รวดเร็วขึ้น ซึ่ง Divide and Conquerเป็นหนึ่งในประเภทของอัลกอริทึมเหล่านั้น
Divide and Conquer คือ อัลกอริทึมประเภทหนึ่ง เรียกง่ายๆตามตัวเลยว่า แบ่งแยกและเอาชนะ Divide คือ แบ่ง ปัญหาที่พบเป็นปัญหาประเภทเดียวกันแต่ที่เล็กลง ขั้นตอนนี้โดยทั่วไปจะใช้วิธีการแบบเรียกซ้ำไปเรื่อยๆ
เพื่อแบ่งปัญหาจนกว่าจะไม่สามารถแบ่งปัญหานั้นๆย่อยลงไปอีกได้ และปัญหาที่ถูกแบ่งไปนั้น
ต้องยังเป็นส่วนหนึ่งของปัญหาเดิมที่เราต้องการจะแก้ไข
Conquer คือ แก้ปัญหาย่อยซ้ำๆ ในขั้นตอนนี้จะได้รับปัญหาย่อยที่แบ่งแล้วจำนวนมาก จากในขั้นDivide
โดยทั่วไปในขั้นตอนนี้ปัญหาต่างๆที่ถูกแบ่งจนไม่สามารถแบ่งได้แล้ว จะสามารถแก้ปัญหาได้ด้วยตัวเอง
หลังจากทั้งแบ่งและแก้ปัญหาในส่วนย่อยต่างๆไปแล้ว ก็จะต้องนำผลลัพธ์ที่ได้จากการแก้ปัญหาส่วนย่อยเหล่านั้นมารวมกัน
กลับมาเป็นชิ้นใหญ่ ที่จะสามารถแก้ปัญหาดั้งเดิมที่เราต้องการแก้ได้
ในการเขียนอัลกอริทึมแบบ Divide and Conquer นิยมเขียนแบบ recursive เพราะง่ายต่อการใช้แต่ก็สามารถเขียนแบบไม่recursive ได้แต่โดยทั่วๆไปเขียนแบบ recursive จะง่ายกว่ามาก
ตัวอย่างปัญหาที่ใช้ Divide and Conquerในการช่วยแก้ไขปัญหา
- Quicksort
- Merge Sort
- Binary Search
- Closest Pair of Points
จะทำให้เราเข้าใจปัญหาได้มากขึ้น แม้ว่าท้ายสุดจะไม่ใช่วิธีการออกแบบวิธีแก้ปัญหาที่ดีที่สุด แต่หากเราเริ่มด้วยวิธีนี้จะช่วยให้เราเห็นภาพ และทำความเข้าใจปัญหา
ที่เราจะแก้ไขได้ง่าย และช่วยให้เขียนโปรแกรมได้มีประสิทธิภาพ
อ้างอิง
https://www.freecodecamp.org/news/divide-and-conquer-algorithms/
https://baannapleangthai.com/algorithm-design-4-1-divide-conquer-%E0%B8%84%E0%B8%AD%E0%B8%99%E0%B9%80%E0%B8%8B%E0%B9%87%E0%B8%9B-%E0%B8%84%E0%B8%B7%E0%B8%AD/
https://marupatnote.home.blog/2021/06/25/4600/