CoE KKU

เราจะใช้นิยามคณิตศาสตร์ต่อไปนี้ในการวิเคราะห์อัลกอริทึมตลอดบทเรียนของเรา

นิยาม 2.1: $T(n) = O(f(n))$ ถ้ามีค่า $c$ และ $n_0$ เป็นค่าคงที่ที่เป็นบวกซึ่งทำให้ $T(n) \leq cf(n)$ เมื่อ $n > n_0$.

นิยาม 2.2: $T(n)= \Omega(f(n))$ ถ้ามีค่า $c$ และ $n_0$ เป็นค่าคงที่ที่เป็นบวกซึ่งทำให้ $T(n) \geq cf(n)$ เมื่อ $n > n_0$.

นิยาม 2.3: $T(n)= \Theta(f(n))$ ก็ต่อเมื่อ $T(n) = O(f(n))$ และ $T(n)= \Omega(f(n))$.

นิยาม 2.4: $T(n) = o(p(n))$ ถ้าสำหรับค่าคงที่ $c$ ใด ๆ แล้วจะมีค่า $n_0$ ที่จะได้ว่า $T(n) < cp(n)$ เมื่อ $n > n_0$ หรืออาจกล่าวได้ ว่า $T(n) = o(p(n))$ ถ้า $T(n) = O(p(n))$ และ $T(n) ≠ \Theta(p(n))$.

นิยาม 2.5: $T(n) = ω(p(n))$ ถ้าสำหรับค่าคงที่ $c$ ใด ๆ แล้วจะมีค่า $n_0$ ที่จะได้ว่า $T(n) > cp(n)$ เมื่อ $n > n_0$ หรืออาจกล่าวได้ ว่า $T(n) = ω(p(n))$ ถ้า $T(n) = Ω(p(n))$ และ $T(n) ≠ \Theta(p(n))$

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

เบื้องหลังของนิยามเหล่านี้คือ การสร้างสิ่งที่เรียกว่า ลำดับเชิงเปรียบเทียบ (relative order) ระหว่างฟังก์ชันต่าง ๆ นั่นเอง เมื่อพูดถึงฟังก์ชัน 2 ฟังก์ชันแล้วก็มักจะมีจุดต่าง ๆ หลายจุดที่ฟังก์ชันหนึ่งมีค่าน้อยกว่าอีกฟังก์ชันหนึ่งได้ ดังนั้นจึงไม่มีความหมายที่จะพูดว่า $f(n) < g(n)$

ดังนั้นเราจะใช้วิธีการเปรียบเทียบอัตราการเติบโต (rates of growth) ระหว่างฟังก์ชันซึ่งมีความสำคัญต่อการวิเคราะห์อัลกอริทึม ดังเช่นถึงแม้ว่า $1000n$ มีค่ามากกว่า $n^2$ เมื่อ $n$ มีค่าน้อย ๆ อย่างไรก็ตาม $n^2$ จะมีอัตราการโตขึ้นด้วยอัตราที่เร็วกว่าขณะที่ $n$ มีค่าเพิ่มมากขึ้น ดังนั้น จึงกล่าวว่า $n^2$ เป็นฟังก์ชันที่มีขนาดใหญ่กว่า ซึ่งจะเห็นว่าจุดเปลี่ยนของกรณีนี้คือ เมื่อ $n = 1000$ นิยาม 2.1 กล่าวว่า ในที่สุดแล้วนับจากจุด $n_0$ จุดหนึ่งขึ้นไปแล้ว $cf(n)$ มีค่าอย่างน้อยที่สุดได้เท่ากับ $T(n)$

ดังนั้นถ้าเราตัดค่าคงที่ออกไป ฟังก์ชัน $f(n)$ มีค่าน้อยที่สุดได้เท่ากับค่าฟังก์ชัน $T(n)$ เท่านั้น สำหรับกรณีตัวอย่างข้างบนนี้ เรามี $T(n) = 1000n$, $f(n) = n^2$ , $n_0 = 1000$ และ $c = 1$ หรือเราอาจจะใช้ค่า $n_0 = 10$ และ $c = 100$ ก็ได้เช่นกัน ดังนั้น เราสามารถกล่าวได้ว่า $1000n = O(n^2)$ (เรียกว่ามันมี order เป็น n-squared) สัญลักษณ์ที่ใช้นี้เรียกว่า Big-Oh notation และปกติจะใช้คำว่า “Big-Oh . .. .” แทนคำว่า “order . . . ”

ถ้าเราใช้เครื่องหมายเปรียบเทียบการไม่เท่ากันเป็นตัวเปรียบเทียบอัตราการโต (growth rate) แล้วกล่าวสำหรับนิยามแรกแล้วกล่าวได้ว่า growth rate ของ $T(n)$ น้อยกว่าหรือเท่ากับ ($\leq$) growth rate ของ $f(n)$ สำหรับนิยามที่สอง $T(n) = \Omega(g(n))$, เป็นการกล่าวว่า growth rate ของ $T(n)$ มากกว่าหรือเท่ากับ ($\geq$) growth rate ของ $g(n)$ สำหรับนิยามที่สาม $T(n) = \Theta(h(n))$, เป็นการกล่าวว่า growth rate ของ $T(n)$ เท่ากับ ( $=$ ) growth rate ของ h(n)

สำหรับนิยาม T(n) = o(p(n)) เป็นการกล่าวว่า growth rate ของ T(n) น้อยกว่า (<) growth rate ของ p(n) จากนิยาม T(n) = ω(p(n)) เป็นการกล่าวว่า growth rate ของ T(n) มากกว่า (>) growth rate ของ p(n) และ ซึ่งจะแตกต่างจาก Big-Oh, เนื่องจากสำหรับ Big-Oh ฟังก์ชันทั้งสองอาจจะมี growth rates เท่ากันได้ และ ค่า c เป็นค่าใดๆ ทุกค่า

เมื่อเรากล่าวว่า $T(n) = O(f(n)$ เราก็จะประกันได้ว่าฟังก์ชัน $T(n)$ จะโตด้วยอัตราที่ไม่มากไปกว่าอัตราการโตของ $f(n)$ นั่นคือ $f(n)$ เป็นขอบเขตบน (upper bound) ของ $T(n)$ นั่นเอง และในขณะเดียวกับที่มันก็มีความหมายว่า $f(n) = \Omega(T(n))$ ด้วยนั้นเราก็อาจกล่าวได้ว่า $T(n)$ เป็นขอบเขตล่าง (lower bound) ของ $f(n)$

ตัวอย่างเช่น $n^3$ โตเร็วกว่า $n^2$, ดังนั้นเราอาจกล่าวได้ว่า $n^2 = O(n^3)$ หรือ $n^3 = \Omega(n^2)$ ถ้าให้ $f(n) = n^2$ และ $g(n) = 2n^2$ แล้ว ฟังก์ชันทั้งสองก็จะโตด้วยอัตราที่เท่ากัน ดังนั้นทั้ง $f(n) = O(g(n))$ และ $g(n) = \Omega(f(n))$ จึงเป็นจริง เมื่อฟังก์ชันสองฟังก์ชันโตในอัตราเท่า ๆ กัน การจะกำหนดให้ใช้ $\Theta()$ หรือไม่นั้นขึ้นอยู่กับกรณีเฉพาะนั้น ๆ

ถ้า $g(n) = 2n^2$ แล้วการกล่าวว่า $g(n) = O(n^4)$, $g(n) = O(n^3)$, และ $g(n) = O(n^2)$ ในทางเทคนิคแล้วล้วนถูกต้องทั้งสิ้น แต่แน่นอนว่าคำตอบสุดท้ายย่อมเป็นคำตอบที่ดีที่สุด การเขียนว่า $g(n) = \Theta(n^2)$ ไม่เพียงแต่กล่าวว่า $g(n) = O(n^2)$ เท่านั้นแต่ยังหมายถึงว่ามันเป็นคำตอบที่ดีที่สุดเท่าที่จะเป็นได้ด้วย (tight)

กฎที่ควรทราบ คือ

กฎข้อที่ 1: ถ้า $T1(n) = O(f(n))$ และ $T2(n) = O(g(n))$, แล้วจะได้ว่า (a) $T1(n) + T2(n) = O(f(n)+g(n))$, (ซึ่งความจริงแล้วก็คือ $max (O(f(n)), O(g(n)))$ นั่นเอง) (b) $T1(n) * T2(n) = O(f(n) * g(n))$

กฎข้อที่ 2: ถ้า $T(n)$ เป็น polynomial ที่มี degree $k$ แล้ว $T(n) = \Theta(n^k)$

กฎข้อที่ 3: $log^k n = O(n)$ สำหรับค่าคงที่ $k$ ใด ๆ ซึ่งหมายความว่า logarithms เป็นฟังก์ชันที่โตช้ามาก

ด้วยสิ่งที่กล่าวมาแล้วสามารถจัดลำดับของ growth rate ดังรูป 2.1 และรูปที่ 2.2 แสดงกราฟของฟังก์ชันซึ่งจะเห็นการเติบโตได้

รูปที่ 2.1 ฟังก์ชันจัดเรียงตามลำดับของ growth rate

สำหรับ กฎข้อที่ 1(a) มีค่าคงที่ $c_1, c_2, n_1,$ และ $n_2$ ที่ $T1(n) \leq c_1f(n)$ สำหรับ $n > n_1$ และ $T2(n) \leq c_2g(n)$ สำหรับ $n > n_2$ ให้ $n_0 = max(n_1, n_2)$ ดังนั้น ที่ $n > n_0$ แล้ว $T1(n) \geq c_1f(n)$ และ $T2(n) \geq c_2g(n)$ จะได้

$T1(n) + T2(n) \geq c_1f(n) + c_2g(n)$

ให้ $c_3 = max(c_1, c_2)$ จะได้

\begin{align*} T1(n) + T2(n) & \geq c_3f(n) + c_3g(n) \\ & \geq c_3(f(n) + g(n)) \\ & \geq c_3 max(f(n), g(n)) \\ & \geq c\ max(f(n), g(n)) \\ \end{align*} เมื่อ $c = 2c_3$ และ $n > n_0$

สำหรับ กฎข้อที่ 1(b) \begin{align*} T1(n) ∙ T2(n) & \geq c_1f(n) ∙ c_2g(n) \\ & \geq c_3(f(n) ∙ g(n)) \text{เมื่อ }c_3 = c_1 * c_2 \text{และเมื่อ }n ≥ n_0 \\ \end{align*}

ทฤษฎีบทที่ 2.1

ให้ $f(n) = ∑_{i=0}^m a_i n^i $ เป็น polynomial ของ $n$ ที่มี order $m$ จะได้ว่า $f(n) = O(n^m)$

พิสูจน์ เนื่องจาก $f(n) = a_m n^m + a_{m-1} n^{m-1} + ⋯ + a_1 n+a_0$ และ Triangular inequality จะได้ \begin{align*} |f(n)| & ≤ |a_m|n^m + |a_{m-1}| n^{m-1} + ⋯ + |a_1|n + |a_0| \\ & ≤ |a_m|n^m + |a_{m-1}| n^m + ⋯ + |a_1|n^m + |a_0|n^m,\ \ \ n≥1 \\ & = (∑_{i=1}^m|a_i|)n^m = Cn^m, \text{เมื่อ} C = ∑_{i=1}^m |a_i | \\ & = O(n^m) \end{align*}

ดังนั้น เมื่อ $n$ มีค่ามากพอ เทอมนำหน้าของ polynomial (มี degree ของ $n$ สูงสุด) จะมีอิทธิพลมากที่สุดต่อค่าฟังก์ชัน

ตัวอย่างที่ 2.1 ให้ $f(n)=50n^3-6n+23$ ให้แสดงว่า $f(n)=O(n^3)$

วิธีทำ $f(n)=50n^3-6n+23$ ดังนั้น \begin{align*} |f(n)| & = |50n^3-6n+23| \\ & ≤ |50n^3 |+|-6n|+|23|, \ \ \ \text{triangular inequality} \\ & = 50n^3+6n+23 \\ & ≤ 50n^3+6n^3+23n^3, \ \ \ \text{when } n≥1 \text{(note } n_0=1 ) \\ & = 79n^3 \\ \end{align*} ดังนั้น โดยให้ $C = 79$ จะได้ว่า $f(n)=O(n^3)$

เมื่อ $n$ มีค่ามากพอจะพบว่า order functions เปรียบเทียบกันดังนี้ :

$$O(1) < O(lg n) < O(n) < O(n lg n) < O(n2) < O(n3) < O(2n) < O(n!) $$

หมายความว่า ถ้ามีอัลกอริทึม 2 อัลกอริทึมที่ใช้ในการแก้ปัญหาเดียวกัน โดยอัลกอริทึมหนึ่งเป็น $O(n)$ และอีกอัลกอริทึมหนึ่งเป็น $O(lg n)$ โดยที่มีอย่างอื่น ๆ เหมือนกัน นั่นหมายความว่า อัลกอริทึมที่ 2 ทำงานได้เร็วกว่า

ตัวอย่างที่ 2.2 จงแสดงให้เห็นว่า $n! = O(n^n)$ และ $lg (n!) = O(n lgn)$.

วิธีทำ

\begin{align*} n! & = n ∙ (n-1) ... 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 \\ & < n ∙ n ... n ∙ n , \text{เมื่อ} n > 1 \\ & = n^n = O(n^n) \text{(Note โดย} C = 1 \text{)} \\ \end{align*}

เนื่องจาก $n! < n^n$ จากข้างบน \begin{align*} lg\ n! & < n\ lg\ n \ \ \text{(Note: If } 0 < x < y, \text{then }lg\ x < lg\ y.)\\ & = O(n\ lg\ n) \\ \end{align*}

ตัวอย่างที่ 2.3 ให้แสดงว่า $f(n)=6n^2+5n+7lg n!$ มี Big-O เท่าไร

วิธีทำ เนื่องจาก $6n^2= O(n^2)$ และ $5n = O(n)$, ดังนั้น $6n^2+5n = Max(O(n^2),O(n))=O(n^2)$ และ $7=O(1)$, และ $lg\ n! =O(n lg\ n)$ จากตัวอย่าง 2.1 ข้างบน ดังนั้น \begin{align*} 7 lg\ n! & = O(1)∙O(n \lg\ n) \\ & = O(1∙n\ lg\ n) \\ & = O(n\ lg\ n)\\ \end{align*} เนื่องจาก $lg\ n ≤ n,n\ lg\ n ≤ n^2$ สำหรับ $n ≥ 1$ ดังนั้น $f(n) = O(n^2) + O(n\ lg\ n) = O(n^2)$

ตัวอย่างที่ 2.4 ให้ $f(n)=(3n^2+4n-5) lg\ n$ มี Big-O เท่าไร

วิธีทำ เนื่องจาก $3n^2+4n-5= O(n^2)$ และ $lg\ n = O(lg\ n)$ ดังนั้น \begin{align*} f(n) & = (3n^2+4n-5)\ lg n \\ & = O(n^2)∙O(lg n) \\ & = O(n^2\ lg\ n)\\ \end{align*}

ตัวอย่างที่ 2.5 ให้ $f(n)=50n^3-6n+23$ มี Big-$\Omega$ เท่าไร

วิธีทำ เมื่อ $n ≥ 0$ จะได้ว่า $50n^3-6n+23 ≥ 50n^3$

ดังนั้น เมื่อ $C = 50$ และ $g(n)=n^3$ จะได้ว่า $f(n) ≥ C∙g(n)$ สำหรับทุก ๆ ค่าของ $n ≥ 0$ ดังนั้น $f(n)=\Omega(n^3)$ และ $n_0=0$

ตัวอย่างที่ 2.5 ให้ $f(n)=(3n^2+4n-5)\ lg\ n$ มี Big-$\Theta$ เท่าไร

วิธีทำ จากตัวอย่างที่ 2.3 $f(n)=O(n^2\ lg\ n)$ เมื่อ $n≥1$ นอกจากนี้ เราจะได้ \begin{align*} (3n^2+4n-5)\ lg\ n & ≥ 3n^2\ lg\ n\\ f(n) & ≥ 3(n^2\ lg\ n) \\ f(n) & = \Omega(n^2\ lg\ n)\\ f(n) & = O(n^2\ lg\ n) = \Omega(n^2\ lg\ n),\\ f(n) &= \Theta(n^2\ lg\ n) \end{align*}

ประเด็นอื่น ๆ ที่จะกล่าวถึง ประการแรกคือ ในเทอมของ Big-O จะไม่เขียนระบุค่าคงที่และไม่เขียนระบุเทอมที่มีกำลังน้อยกว่า ดังนั้น จึงไม่เขียน $T(n) = O(2n^2)$ หรือ $T(n) = O(n^2 + n)$ ทั้งสองกรณีนี้เขียนได้เป็น $T(n) = O(n^2)$ นั่นหมายความว่า ในการวิเคราะห์ที่ต้องการ Big-O ก็สามารถใช้วิธีลัดได้ เช่น ไม่ต้องใส่ใจกับ order ต่ำ ๆ คือตัดทิ้งได้ รวมทั้งค่าคงที่ เช่นกัน

ประการที่สอง, เราสามารถพิจารณาหา relative growth rates ของฟังก์ชันสองฟังก์ชัน เช่น $f(n)$ และ $g(n)$ ได้ด้วยการคำนวณ $\lim_{n \to +\infty} \frac{f(n)}{g(n)}$, ด้วยการใช้ L'Hopital's rule ถ้าจำเป็น*

L’Hopital’s rule: ถ้า $\lim_{n \to +\infty} f(n) = \infty$ และ $\lim_{n \to +\infty} g(n) = \infty$, จะได้ว่า $$\lim_{n \to +\infty} \frac{f(n)}{g(n)} = \lim_{n \to +\infty} \frac{f'(n)}{g'(n)}$$ เมื่อ $f'(n)$ และ $g'(n)$ เป็น derivative ของ $f(n)$ และ $g(n)$ ตามลำดับ

ค่าของ limit ที่อาจเป็นไปได้มี 4 ทางด้วยกัน ดังนี้

• ถ้า limit มีค่าเป็น 0: หมายความว่า $f(n) = o(g(n))$
• ถ้า limit เป็นมีค่าเป็นค่าคงที่ $c \geq 0$: หมายความว่า $f(n) = \Omega(g(n))$
• ถ้า limit มีค่าเป็น $\infty$ หมายความว่า $g(n) = o(f(n))$
• ถ้า limit ขึ้นลงแบบ oscillates: หมายความว่า ไม่มีความสัมพันธ์กัน (this will not happen in our context)

ตัวอย่างที่ 2.6 แสดงให้เห็นว่า $log\ n = o(n)$

วิธีทำ เนื่องจากทั้ง $log n$ และ $n$ เข้าสู่ $\infty$ เมื่อ $n$ เข้าสู่ $\infty$ จึงใช้ L’Hopital’s rule กับ $\frac{log\ n}{n}$ และ เนื่องจาก $log\ n = (log\ e)*(log_e\ n)$ ดังนั้น derivative ของ $log n$ คือ $(log\ e)(\frac{1}{n})$ นั่นคือ $$ \lim_{n\to +\infty}⁡ \frac{(log\ n)'}{n'} = \lim_{n\to +\infty}⁡ ((log\ e)(\frac{1}{n})) = 0 $$ ดังนั้น $log n = o(n).$

ตัวอย่างที่ 2.7 เปรียบเทียบอัตราการเพิ่มของฟังก์ชัน $\frac{1}{2} n(n-1)$ และ $n^2$ $$\lim_{n\to +\infty}⁡ \frac{\frac{1}{2}n(n-1)}{n^2} = \frac{1}{2} $$ $$\lim_{n\to +\infty} \frac{n^2-n}{n^2} = \frac{1}{2} $$ $$\lim_{n\to +\infty}⁡ (1-\frac{1}{n}) = \frac{1}{2} $$ เนื่องจากลิมิตมีค่าเป็นค่าคงที่ที่เป็นค่าบวก ดังนั้นอัตราการเพิ่มของฟังก์ชันทั้งสองจึงเท่ากัน หรือกล่าวได้ว่า $\frac{1}{2}n(n-1) ∈ Θ(n^2)$

ตัวอย่างที่ 2.8 เปรียบเทียบอัตราการเพิ่มของฟังก์ชัน $log_2⁡n$ และ $\sqrt n$

$$ \lim_{n\to +\infty}⁡ \frac{log_2⁡n}{\sqrt n} = \lim_{n\to +\infty}⁡ \frac{(log_2⁡n)'}{(\sqrt n)'} $$ $$=\lim_{n\to +\infty}((log_2⁡e ) 1/n)/(\frac{1}{(2\sqrt n)})$$ $$=2 log_2⁡e \lim_{n\to +\infty} \frac{ \sqrt n}{n} = 0$$

เนื่องจากลิมิตมีค่าเป็นค่าเป็นศูนย์ ดังนั้นอัตราการเพิ่มของฟังก์ชัน $log_2⁡n$ จึงน้อยกว่าของ $\sqrt n$ หรือกล่าวได้ว่า $log_2⁡n \in o(\sqrt n) $