【演算法】淺談 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)，我們可以計算 \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 就會等於無限大，與定義不合。下面關於 Ω 的證明也可以這樣想。

總結一些常見的時間複雜度比較：

1 < \log{n} < \sqrt{n} < n < n\log{n} < n^{2} < n!

Ω, Omega Notation


Ω 跟剛剛所提到的 Big-O 是完全相反的概念，他表示的是演算法的時間下限，也就是「最佳解」時候所花費的時間漸近線。
Ω 需要滿足方程式 0 \le cg(n) \le 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 \le {c_{1}}g(n) \le f(n) \le {c_{2}}g(n)，其中 {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 範圍內)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

我覺得你也會想看...