ผลต่างระหว่างรุ่นของ "204512/บรรยาย 2"
ไปยังการนำทาง
ไปยังการค้นหา
| แถว 13: | แถว 13: | ||
'''Definition 1''' | '''Definition 1''' | ||
| − | <math>\ T(n) = O( f(n) )</math> | + | <center> |
| − | + | <math>\ T(n) = O( f(n) )</math> <br /> | |
| + | <u>T of n</u> is in Big-Oh of <u>f of n</u> iff there're constants <math>\ c</math> and <math>\ n_0</math> such that <br /> | ||
<math>\ T(n) \le c \cdot f(n)</math> for all <math>\ n \ge n_0</math> | <math>\ T(n) \le c \cdot f(n)</math> for all <math>\ n \ge n_0</math> | ||
| + | </center> | ||
| − | เช่น <math>\ 3n^2 + 2n = O(n^2)</math | + | ; เช่น <br /> |
| − | + | : <math>\ 3n^2 + 2n = O(n^2)</math> | |
| − | <math>\ 3n^2 + 2n \le | + | จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ <math>\ C=4, n_0 = 2</math> <br /> |
| + | <math>\ 3n^2 + 2n \le c \cdot n^2</math> <br /> | ||
| + | <math>\ 3n^2 + 2n \le 3n^2 + n^2</math> | ||
---- | ---- | ||
รุ่นแก้ไขเมื่อ 18:08, 16 มิถุนายน 2550
เนื้อหา
เกริ่นนำ
หลักการของ 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
Merge Sort
Fast Furier Transform
แหล่งข้อมูลอื่น
อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia อธิบายเรื่อง Big-O-Notation ของ Wiki Pedia
ใช้ยากจังน้อ
