【演算法】淺談 Asymptotic analysis 漸進分析的三種符號：O、Ω 及 Θ

通常在演算法中，為了證明某個演算法執行 n 次項時所需要的時間，我們需要藉由一些比較視覺化的方式去展現出來。如果秉持著職人精神，我們可以把 n 帶入 1、2、3…、1000、…10000… 去跑，並將每次執行完成所需時間做成一張圖表，精神可貴，但時間不夠。為此我們需要以比較「數學化」的方式去分析每個演算法，這就是我們這章節需要介紹的 Asymptotic analysus 漸進分析了。

漸進分析的大綱是在於，當我執行的次數 n 接近於無限大的時候，我們的執行時間會是以何種趨勢去增長？可能是以對數形式 log ，也可能是以線性級數 ax+b，又或是以指數形式

$x^2$ 之類的形式去增長，找到他的最高上限 O，最低下限 Ω 以及平均上限下限 Θ。

O, Big-O Notation

Big-O 表示其演算法在「最壞情況」時所需要的時間上限，也是我們一般評定演算法速度的方法。
假設今天的演算法大致時間走勢趨近於方程式

$3n^2+2n+1$，那我們可以說他的 Big-O 表示法為

$O(n^2)$，也同時為他的時間複雜度(time complexity)

Big-O 需要滿足方程式

$0\le f(n)\le cg(n)$，其中 f(n) 為我們演算法的時間方程式，g(n) 為時間複雜度，c 為一常數。
如果需要證明 g(n) 為 f(n) 的上界(時間上限函式,Upper bounding function)，我們可以計算

$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=c$ 時 c 是否 ≥ 0，如果是即成立。(小提醒，∞ 並不在 c ≥ 0 範圍內)

小技巧，不用死背

$fracf(n)g(n)$ 的上下關係，只需要考慮到 f(n) 的最大次方數不能比 g(n) 還大，這樣想的話就會明白如果 f(n) 的最大次方數大於 g(n)，那當計算

$\underset{n\to \mathrm{\infty }}{lim}\frac{f(n)}{g(n)}=c$ 時，分子分母相消後還會存在至少一個 n 於分子，那這樣出來的 c 就會等於無限大，與定義不合。下面關於 Ω 的證明也可以這樣想。

Ω, Omega Notation

Ω 跟剛剛所提到的 Big-O 是完全相反的概念，他表示的是演算法的時間下限，也就是「最佳解」時候所花費的時間漸近線。
Ω 需要滿足方程式

$0\le cg(n)\le f(n)$，其中 f(n) 為我們演算法的時間方程式，g(n) 為時間複雜度，c 為一常數。
如果需要證明 g(n) 為 f(n) 的下界(時間下限函式,Lower bounding function)，我們可以計算

$\underset{n\to \mathrm{\infty }}{lim}\frac{g(n)}{f(n)}=c$ 時 c 是否 ≥ 0，如果是即成立。(小提醒，∞ 並不在 c ≥ 0 範圍內)

Θ, Theta Notation

Θ 比較像是剛剛提到的 Big-O 及 Ω 去做平均，也表示為平均時間複雜度。
Θ 需要滿足方程式

$0\le c_1\le f(n)\le c_2$，其中

$c_1$ 及

$c_2$ 均為常數。
如果需要證明 g(n) 為 f(n) 的平均界(時間平均函式,Tightly bounding function)，我們可以計算

$\underset{n\to \mathrm{\infty }}{lim}\frac{g(n)}{f(n)}=c$ 時 c 是否 > 0，如果是即成立。(小提醒，∞ 並不在 c > 0 範圍內)