# 【演算法】淺談 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 ≤ f(n) ≤ cg(n)$，其中 f(n) 為我們演算法的時間方程式，g(n) 為時間複雜度，c 為一常數。
如果需要證明 g(n) 為 f(n) 的上界(時間上限函式,Upper bounding function)，我們可以計算 $\lim_{n\to\infty}\frac{f(n)}{g(n)} = c$ 時 c 是否 ≥ 0，如果是即成立。(小提醒，∞ 並不在 c ≥ 0 範圍內)

小技巧，不用死背 $frac{f(n)}{g(n)}$ 的上下關係，只需要考慮到 f(n) 的最大次方數不能比 g(n) 還大，這樣想的話就會明白如果 f(n) 的最大次方數大於 g(n)，那當計算 $\lim_{n\to\infty}\frac{f(n)}{g(n)} = c$ 時，分子分母相消後還會存在至少一個 n 於分子，那這樣出來的 c 就會等於無限大，與定義不合。下面關於 Ω 的證明也可以這樣想。

## Ω, Omega Notation
Ω 跟剛剛所提到的 Big-O 是完全相反的概念，他表示的是演算法的時間下限，也就是「最佳解」時候所花費的時間漸近線。
Ω 需要滿足方程式 $0 ≤ cg(n) ≤ f(n)$，其中 f(n) 為我們演算法的時間方程式，g(n) 為時間複雜度，c 為一常數。
如果需要證明 g(n) 為 f(n) 的下界(時間下限函式,Lower bounding function)，我們可以計算 $\lim_{n\to\infty}\frac{g(n)}{f(n)} = c$ 時 c 是否 ≥ 0，如果是即成立。(小提醒，∞ 並不在 c ≥ 0 範圍內)

## Θ, Theta Notation
Θ 比較像是剛剛提到的 Big-O 及 Ω 去做平均，也表示為平均時間複雜度。
Θ 需要滿足方程式 $0 ≤ {c_{1}} ≤ f(n) ≤ {c_{2}}$，其中 ${c_{1}}$ 及 ${c_{2}}$ 均為常數。
如果需要證明 g(n) 為 f(n) 的平均界(時間平均函式,Tightly bounding function)，我們可以計算 $\lim_{n\to\infty}\frac{g(n)}{f(n)} = c$ 時 c 是否 > 0，如果是即成立。(小提醒，∞ 並不在 c > 0 範圍內)