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 of n is in Big-Oh of f of n iff there're constants and such that
for all
- เช่น
จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ
ตัวอย่างปัญหา ที่ใช้กรรมวิธีแก้ไขแบบ Divide & Conquer
Multiplication
การคูณกันของ ที่เป็น binary number ขนาด n-bit สามารถแยกออกได้เป็น
- สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด
นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit
Merge Sort
Fast Furier Transform
แหล่งข้อมูลอื่น
อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia
ใช้ยากจังน้อ