ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบ่งแยกและเอาชนะ"

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข
บรรทัด 15:
=== ประสิทธิภาพของขั้นตอนวิธี ===
ขั้นตอนวิธีแบ่งแยกและเอาชนะมักจะช่วยในการสร้างขั้นตอนวิธีที่มีประสิทธิภาพ เช่น การคูณอย่างรวดเร็วด้วย[[ขั้นตอนวิธีของคาราซูบา]] การเรียงลำดับอย่างรวดเร็วด้วย[[การเรียงลำดับแบบเร็ว]]หรือ[[การเรียงลำดับแบบผสาน]] การคูณเมทริกซ์ด้วย[[ขั้นตอนวิธีของสแตรสเซน]] หรือการคำนวณ[[การแปลงฟูรีเยไม่ต่อเนื่อง]]แบบเร็ว
 
ในตัวอย่างทั้งหมดที่กล่าวมา ขั้นตอนวิธีแบ่งแยกและเอาชนะช่วยในการลด[[ความซับซ้อนในการคำนวณ]]ได้อย่างมีนัยยะสำคัญ ยกตัวอย่างเช่นการเรียงลำดับแบบผสาน ซึ่งคำนวณ[[การเรียกซ้ำ#กรณีฐาน|กรณีฐาน]]ได้ในเวลาคงที่ และการแบ่งและรวมปัญหาในแต่ละครั้งใช้เวลา <math>O(n)</math> เมื่อ ''n'' คือขนาดปัญหาที่กำลังแก้ในขณะนั้น จะได้ว่าประสิทธิภาพโดยรวมของขั้นตอนวิธี คือ <math>O(n \log n)</math> ซึ่งดีกว่า[[ขั้นตอนวิธีการเรียงลำดับ|การเรียงลำดับ]]แบบอื่น ๆ ที่คิดค้นขึ้นมาก่อนหน้านั้น ซึ่งส่วนใหญ่จะใช้เวลา <math>O(n^2)</math>
 
== อ้างอิง ==