204512/บรรยาย 2

บันทึกคำบรรยายวิชา 204512 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

จดบันทึกคำบรรยายโดย: (กรุณาใส่ด้วย)

เกริ่นนำ

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

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

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

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

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

---

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

Definition 1

Error

Too many requests (f061ab2)


If you report this error to the Wikimedia System Administrators, please include the details below.
Request served via cp5021 cp5021, Varnish XID 170001076
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:31 GMT
Sensitive client information
IP address: 158.108.32.49



$\ T(n)=O(f(n))$ 

T of n is in Big-Oh of f of n iff there're constants $\ c$ and 









Error

Too many requests (f061ab2)


If you report this error to the Wikimedia System Administrators, please include the details below.
Request served via cp5021 cp5021, Varnish XID 165844777
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:32 GMT
Sensitive client information
IP address: 158.108.32.49



$\ n_{0}$ such that 

$\ T(n)\leq c\cdot f(n)$ for all 









Error

Too many requests (f061ab2)


If you report this error to the Wikimedia System Administrators, please include the details below.
Request served via cp5021 cp5021, Varnish XID 150619456
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:33 GMT
Sensitive client information
IP address: 158.108.32.49



$\ n\geq n_{0}$

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

เช่น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 163221624
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:33 GMT


Sensitive client information

IP address: 158.108.32.49

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

จะเห็นได้ว่า definition 1 เป็นจริงได้เมื่อ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 157069057
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:33 GMT


Sensitive client information

IP address: 158.108.32.49

$\ C=4,n_{0}=2$
$\ 3n^{2}+2n\leq c\cdot n^{2}$

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 133650778
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:34 GMT


Sensitive client information

IP address: 158.108.32.49

$\ 3n^{2}+2n\leq 3n^{2}+n^{2}$

โดยทั่วไปแล้ว Big-Oh คือการแสดง Upper Bound ของฟังก์ขั่น ขณะที่ Big-Omega (

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 169412585
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:35 GMT


Sensitive client information

IP address: 158.108.32.49

$\Omega$) เป็นการแสดงถึง Lower Bound ของฟังก์ชั่น

---

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

Multiplication

การคูณกันของ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 159784743
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:35 GMT


Sensitive client information

IP address: 158.108.32.49

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 164534405
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:36 GMT


Sensitive client information

IP address: 158.108.32.49

$\ 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 เป็น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 170328757
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:36 GMT


Sensitive client information

IP address: 158.108.32.49

$T(n)=2T({\frac {n}{2}})+O(n)$

จากภาพ Tree มีความสูง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 163552295
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:36 GMT


Sensitive client information

IP address: 158.108.32.49

$\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 ได้เสนอวิธีการคูณในอีกรูปแบบหนึ่งที่ใช้การคูณเพียงสามครั้งจาก

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 163585892
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:37 GMT


Sensitive client information

IP address: 158.108.32.49

$x_{L}y_{R}+x_{R}y_{L}=(x_{L}+x_{R})(y_{L}+y_{R})-x_{L}y_{L}-x_{R}y_{R}\,$ ทำให้อัลกอลิธึ่มได้รับการปรับปรุงเป็น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 163354401
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:37 GMT


Sensitive client information

IP address: 158.108.32.49

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

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 132115817
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:37 GMT


Sensitive client information

IP address: 158.108.32.49

$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}})\,$
• การนำข้อมูลที่เรียงแล้วสองชุดมาต่อกันใช้เวลา
  

  Error

  Too many requests (f061ab2)

  If you report this error to the Wikimedia System Administrators, please include the details below.

  Request served via cp5021 cp5021, Varnish XID 169576404
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:38 GMT


  Sensitive client information

  IP address: 158.108.32.49

  ${\mathcal {O}}(n)$

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

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

Fast Furier Transform

กราฟแสดงการหาสมการผลลัพธ์จากการคูณค่าในแต่ละจุดของสมการตั้งต้น ภาพจากWalterzorn.com

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

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

Devide and Conconquer

เริ่มจากพิจารณาสมการ Polynomial degree-n ใดๆ เช่น เราสามารถหาค่าของจุดต่างๆ จำนวน n จุดได้ โดยหาค่าทั้งในฝั่งบวกและลบไปพร้อมๆ กัน เช่นพิจารณาจุด

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 168299831
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:39 GMT


Sensitive client information

IP address: 158.108.32.49

$\pm x_{1},\pm x_{2},\pm x_{3},...,\pm x_{n}$ เราจะสามารถแยกพิจารณากรณีคู่และคี่ไปพร้อมๆ กันได้โดยการแยกตัวประกอบเพื่อให้ทุกพจน์มี degree เป็นคู่เสมอ ดังเช่นตัวอย่าง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 160310468
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:39 GMT


Sensitive client information

IP address: 158.108.32.49

$f(x)=8+5x+4x^{2}+2x^{3}=(8+4x^{2})+x(5+2x^{2})\,$

การแยกเช่นนี้เป็นจริงเสมอสำหรับ Polnomial ใดๆ เราจึงแยกเป็น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 153859022
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:54 GMT


Sensitive client information

IP address: 158.108.32.49

$f(x)=f_{e}(x^{2})+xf_{o}(x^{2})\,$ เมื่อ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 134043645
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:40 GMT


Sensitive client information

IP address: 158.108.32.49

$f_{e}(x)\,$ เป็นพจน์คู่ของ $f(x)\,$ และ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 172163161
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:56 GMT


Sensitive client information

IP address: 158.108.32.49

$f_{o}(x)\,$ เป็นพจน์คี่ของ $f(x)\,$ โดยที่เมื่อคำนวณค่าออกมาเพียงครั้งเดียว เราสามารถหาค่าทั้งฝั่งบวกและลบได้ดังสมการ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 139877300
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:41 GMT


Sensitive client information

IP address: 158.108.32.49

$f(-x_{n})=f_{e}(x_{n}^{2})+xf_{o}(x_{n}^{2})$

จากข้างบนทำให้เราสามารถย่อยป้ญหาให้เล็กลงครึ่งหนึ่งได้ แต่ในระบบจำนวนจริงเราไม่สามารถแบ่งปัญหาให้เล็กลงไปกว่าครึ่งได้อีกเพราะการยกกำลังสองในครั้งแรกก็ทำให้เลขทุกตัวกลายเป็นจำนวนบวกไปหมด แต่เราสามารถใช้จำนวนเชิงซ้อนในรูปแบบ Root of Unity เพื่อให้สามารถแบ่งปัญหาลงไปเรื่อยๆ ได้โดยการใช้ Root of Unity มีคุณสมบัติที่น่าสนใจสองประการคือ

• มีคู่ตรงข้ามเสมอ ทำให้สามารถยกกำลังสองเพื่อหาค่าทั้งสองค่าในครั้งเดียวได้
• การยกกำลังสองในแต่ละครั้งจะทำให้ได้ Root of Unity ในอับดับที่ ${\frac {n}{2}}$ เสมอ

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

Interpolation

หลังจากที่เราพิจารณาจุดได้มากพอที่จะ Interpolate สมการของผลลัพธ์กลับออกมาได้แล้ว สิ่งที่เราต้องทำต่อไปคือการสร้างสมการที่เป็นผลคูณของสองสมการที่ผ่านมา โดยขณะที่การพิจารณาค่าที่ตำแหน่งต่างๆ ของ $f(x)\,$ นั้นได้ความเร็วเป็น แล้วก็ตาม แต่ความเร็วในการ Interpolate สมการกลับขึ้นมาก็ต้องนำมาพิจารณาด้วย

แต่คุณสมบัติของฟังก์ขั่น FFT ที่เราใช้ในการพิจารณาค่าในส่วนที่แล้ว มีคุณสมบัติที่น่าแปลกคือ

จาก $\langle values\rangle =FFT(\langle cofficients\rangle ,\omega )$ เราจะได้ว่า ซึ่งเนื่องจากสมการในการ Interpolate นั้นเป็นสมการเดียวกับที่ใช้ในการพิจารณาค่าทำให้เราได้ว่าอัลกอลิธึ่มนี้มีความเร็ว เสมอ

Proof of Interpolation

การที่เราสามารถพิจารณาค่าจำนวน n จุดของสมการ Polynomial ได้นั้น เราสามารถมองว่าเป็นการคูณกันระหว่าง Matrix ของ Coeffient และ Matrix ของตัวแปร ดังสมการต่อไปนี้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 164335086
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:42 GMT


Sensitive client information

IP address: 158.108.32.49

${\begin{bmatrix}f(x_{0})\\f(x_{1})\\\vdots \\f(x_{n-1})\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\cdots &\omega ^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega ^{n-1}&\omega ^{2(n-1)}&\cdots &\omega ^{(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\\vdots \\a_{n-1}\end{bmatrix}}$

เราให้ Matrix ของ $\omega$ ตรงกลางนั้นชื่อว่า M โดยมันมีรูปแบบที่เรียกว่า Vandermonde Matrix ที่ระบุว่า Matrix ในรูปแบบนี้จะมี Inverse เสมอ

การพิสูจน์สมการการ Interpolate นั้นทำโดยการมอง Matrix M เป็น Matrix ที่ Map เวคเตอร์จาก Space หนึ่งๆ ไปอีก Space หนึ่ง ซึ่งหากทุกแกนของ Space ใหม่นั้นตั้งฉากกันทั้งหมด เราจะสามารถบอกได้ว่าการ Inverse จะทำให้ได้ค่าเดิม คือ Coefficient กลับมาเสมอ และสามารถใช้สูตร

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 170329130
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:06:02 GMT


Sensitive client information

IP address: 158.108.32.49

$M_{n}(\omega )^{-1}={\frac {1}{n}}M_{n}(\omega ^{-1})$

ซึ่ง ก็ยังคงเป็น Root of Unity อยู่ ทำให้เราสามารถใช้อัลกอลิธึ่มเดิมทำงานได้ต่อไป

ขั้นตอนต่อไปคือการพิสูจน์ว่าแมทริกซ์ M นั้นทุก Column (ซึ่งเป็นเวคเตอร์) ตั้งฉากกันทั้งหมด โดยสามารถทำได้จากการทำ inner product ตามสมการ

$u\cdot v^{*}=u_{0}v_{0}^{*}+u_{1}v_{1}^{*}+\cdots +u_{n-1}v_{n-1}^{*}$ โดยที่ $v^{*}\,$ คือ Conjugate ของ

โดยที่การทำ inner product จะให้ผลลัพธ์สูงสุดเมื่อเวคเตอร์ขนานกัน และให้ผลลัพธ์เป็นศูนย์เมื่อเวคเตอร์ตั้งฉากกัน

ในกรณีของ M ที่กล่าวถึงข้างต้น เมื่อเราเลือกคอลัมน์ i และ j ใดๆ มาหามุมระหว่างกันแล้วจะได้ inner product ว่า

$1+\omega ^{i-j}+\omega ^{2(i-j)}+\cdots +\omega ^{(n-1)(i-j)}$

ซึ่งเป็นอนุกรมเลขาคณิตที่มีอัตราส่วนเป็น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 170491916
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sat, 31 Jan 2026 18:05:44 GMT


Sensitive client information

IP address: 158.108.32.49

$\omega ^{(i-j)}$ ทำให้เราได้ผลลัพธ์ของอนุกรมเป็น ${\frac {1-\omega ^{n(i-j)}}{1-\omega ^{i-j}}}$ แต่เนื่องจาก $\omega$ เป็น Root of Unity ทำให้$\omega ^{n}=1$ เสมอ อนุกรมนี้จึงได้ 0 ทั้งหมดนี้เราจึงได้พิสูจน์ว่าเราสามารถใช้อัลกอลิธึ่ม FFT ในการทำ Interpolate สมการกลับมาได้ และทำให้อัลกอลิธึ่มรวมใช้เวลาการทำงานอยู่ใน ${\mathcal {O}}(n\log {n})$

---

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

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

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

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