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}$

กราฟแสดงตัวอย่าง Big-Oh ตามนิยาม

เช่น

$\ 3n^{2}+2n=O(n^{2})$

จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ $\ C=4,n_{0}=2$
$\ 3n^{2}+2n\leq c\cdot n^{2}$
$\ 3n^{2}+2n\leq 3n^{2}+n^{2}$

โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega ($\Omega$) เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น

---

ตัวอย่างปัญหา ที่ใช้กรรมวิธีแก้ไขแบบ Divide & Conquer

Multiplication

การคูณกันของ $\ x\cdot y$ ที่เป็น binary number ขนาด n-bit สามารถแยกออกได้เป็น

$\ x\cdot y=(2^{\frac {n}{2}}x_{L}+x_{R})\cdot (2^{\frac {n}{2}}y_{L}+y_{R})$

$\ x\cdot y=2^{n}x_{L}y_{L}+2^{\frac {n}{2}}(x_{L}y_{R}+y_{L}x_{R})+x_{R}y_{R}$

• สามารถสังเกตได้ว่า ประกอบไปด้วยพจน์ที่คูณกัน 4 ชุด

นิยาม Function ของเวลาที่ใช้ในการคำนวณตัวเลข n-bit เป็น $T(n)=2T({\frac {n}{2}})+O(n)$

จากภาพ Tree มีความสูง $\log {n}\,$ ทำให้ได้ว่า

$T(n)=cn[1+2+4+...+2^{n}]=cn\cdot 2^{\log {n}}[{\frac {1}{2^{\log {n}}}}+...+{\frac {1}{4}}+{\frac {1}{2}}+1]={\mathcal {O}}(n^{2})$

Gauss ได้เสนอวิธีการคูณในอีกรูปแบบหนึ่งที่ใช้การคูณเพียงสามครั้งจาก $x_{L}y_{R}+x_{R}y_{L}=(x_{L}+x_{R})(y_{L}+y_{R})-x_{L}y_{L}-x_{R}y_{R}\,$ ทำให้อัลกอลิธึ่มได้รับการปรับปรุงเป็น $T(n)=3T({\frac {n}{2}})+{\mathcal {O}}(n)$ ซึ่งเมื่อคำนวณในรูปแบบเดียวกับ Tree ด้านบนโดยถือว่าแต่ละ node จะมีลูกอยู่ 3 ชุดแทนที่จะเป็น 4 ชุด เราจะได้ว่า

$T(n)=cn({\frac {3}{2}})^{\log {n}}=n^{log_{2}{3}}=n^{1.59}$

Merge Sort

Merge Sort เป็นอัลกอลิธึ่มแบบ Devide-and-Conquer อีกอันหนึ่งที่ อาศัยการแบ่งข้อมูลออกเป็นส่วนเล็กๆ แล้วเรียงลำดับให้ถูกต้อง แล้วจึงนำข้อมูลที่เรียงแล้วกลับมาต่อกัน

กระบวนการทำ Merge Sort มีสามขั้นคือ

• การแบ่งส่วนข้อมูล ได้ทำได้ทันที
• การเรียงข้อมูล ที่แบ่งไปครึ่งๆ แล้ว ใช้เวลา $T({\frac {n}{2}})\,$
• การนำข้อมูลที่เรียงแล้วสองชุดมาต่อกันใช้เวลา ${\mathcal {O}}(n)$

โดยรวมแล้ว Merge Sort ใช้เวลาในการทำงาน $T(n)=T({\frac {n}{2}})+{\mathcal {O}}(n)$

หรือก็คือ ${\mathcal {O}}(n\log {n})$

Fast Furier Transform

FFT คืออัลกอลิธึ่มที่ใช้ในการหาผลคูณของสมการ Polynomial สองชุดเข้าด้วยกัน เพื่อใช้งานในด้าน Signal บางอย่าง โดยมีแนวคิดคือการหาสมการที่เป็นผลคุณของ Polynomial นั้นไม่จำเป็นที่จะต้องเกิดจากการนำสมการมาคุณกันจริงๆ แต่อาจสร้างได้จากคุณสมบัติของ Polynomial ดังนี้

• สมการ Polynomial ที่มี degree เป็น d ใดๆ สามารถสร้างขึ้นจากการหาค่าผลของสมการที่ตำแหน่งต่างๆ จำนวน d+1 ตำแหน่ง
• เมือนำสมการ Polynomial degree d สองสมการมาคูณกัน เราจะได้สมการ Polynomial degree เป็น 2d
• ดังนั้นหากเราหาค่าของสมการตั้งต้นสองสมการจำนวน 2d+1 จุด แล้วนำมาคูณกัน สุดท้ายแล้วเราจะได้ค่า 2d+1 จุดที่สามารถนำไป Interpolate กลับมาเป็นสมการผลคูณของ Polynomial สองสมการได้

---

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

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

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

Inner Product ใช้ในการพิสูจน์เรื่อง Manipulation