204512/บรรยาย 2

เกริ่นนำ

หลักการของ Divide and Conquer Algorithm ประกอบไปด้วย 3 ส่วนดังนี้

1.แตกย่อยปัญหาเป็นชิ้นเล็ก หลายชิ้น

2.ทำการแก้ปัญหาย่อยเหล่านี้ด้วยวิธีการที่คล้ายกัน

3.คำตอบสุดท้ายหาได้จากการสรุปคำตอบทั้งหมดของทุกปัญหาย่อย

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

---

การวิเคราะห์เปรียบเทียบ Algorithm โดยการหา Big O Notation

Definition 1

$\ T(n)=O(f(n))$ 
"T of n is in Big-Oh of f of n" iff there're constants $\ c$ and $\ n_{0}$ such that
$\ T(n)\leq c\cdot f(n)$ for all $\ n\geq n_{0}$

เช่น $\ 3n^{2}+2n=O(n^{2})$
จะเห็นได้ว่าเมื่อ $\ C=4$
$\ 3n^{2}+2n\leq 3n^{2}+n^{2}$ เมื่อ $\ n_{0}=2$

---

---

แหล่งข้อมูล​อื่น​

อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia

ใช้ยากจังน้อ