Asymptotic Notations

動機與定義

研究演算法的時候, 經常需要了解: 如果輸入資料量增加, 則演算法執行時間會增加多少? 執行時間長短, 是資料量多寡的函數 -- 執行時間長短 = f(資料量多寡), 而我們又有點懶得把這個函數算得很仔細, 所以希望可以用 "這個函數的成長速率大約是..." 的方式來描述它就好。 這一章我們就暫時忘記演算法, 只 純粹從數學的角度, 專心研究如何用偷懶的方法籠統地表示函數的 成長速率 (growth rate); 表達函數成長速率的符號, 叫做 asymptotic notations。 "Asymptote" 是漸近線。 許多不同的曲線, 可以有相同的漸近線; 同樣地, 許多不同的函數, 也可以有相同的 asymptotic notation。 我們研究的範圍是非負的數列。 也就是說, 以下談到 g(n) 時, 都假設 n 是 0 或正整數, 且 g(n) 的值大於等於零。 請複習離散數學的 「集合 sets」, 「函數 functions」 等觀念。

我們希望能夠用數學符號表達: 「函數 f(n) 的成長速率比函數 g(n) 的成長速率快」, 「函數 f(n) 成長速率和函數 h(n) 的成長速率差不多快」。 換句話說, 等一下我們要定義的符號, 就像是比較數字時所使用的 < = > 等等符號一樣, 唯一的差別是我們的對象是函數而不是數字。 比較函數可不像比較數字那麼簡單, 因為函數是一條曲線, 不單單是一個點。 如果兩條曲線相對位置忽高忽低, 我們如何比較呢? 在看嚴謹的數學定義之前, 我們先直覺地描述一下兩個原則:

  1. 「小時候胖不算胖」 原則: 我們只在乎 n 很大的時候, 該函數的表現。 畢竟我們想比較的是 長遠的趨勢 而不是一時的高下。 換句話說, 眼光要放遠, 不要在意眼前的狀況, 要看很久, 很久, 很久以後的未來。 現在使用 windows 的人口遠遠超過使用 linux 的人口, 可是...等著瞧吧 :-)
  2. 「方格紙 y 軸可以均勻縮放」 原則: 均勻縮放方格紙 y 軸所得到的圖形, 算做與原圖形的成長速率一樣快。 例如所有斜率大於零的線性函數 y = a x + b, a > 0 都當做一樣快; 又例如畫在方格紙上面的直線與拋物線, 我們希望說拋物線永遠看起來成長比較快, 即使你將直線所在的方格紙均勻拉高也一樣。 這個原則的用意有二: 其一達到籠統比較的目的, 讓我們不必關心太多細節; 其二關心細節也沒有太大的意義 -- 同樣的演算法, 在不同速度的機器上跑, 所花的時間不同: 
            執行時間長短1 = f1(資料量多寡)
        執行時間長短2 = f2(資料量多寡)
    但演算法還是同一個, 我們希望說: 這兩個函數 f1 與 f2 的成長速率 "差不多"。

以下就是正式的定義:

定義裡面的 n0 就是 「轉大人的那一天」; 而 b 與 c 則是方格紙 y 軸放大/縮小的倍數。 注意: 定義中的 n0, b 與 c 並沒有「唯一的正確答案」 (也就是說你可以保守一點, 取大一點的 n0, 大一點的 c, 小一點的 b 總不會出錯。)

以下的類比, 可以幫助你思考, 不過請切記, 這只是類比, 不是公式!

比較函數 f 與 g f 屬於 O(g) f 屬於 Omega(g) f 屬於 Theta(g) f 屬於 o(g) f 屬於 omega(g)
比較數字 a 與 b a <= b a >= b a = b a < b a > b

做幾個簡單的例子感受一下

例一: f(n) = 2 n^2 - 9 n - 12 請用最簡單, 最精確的 asymptotic notation 描述 f(n) 的成長速率。 其實當 n 很大很大時, - 9 n 與 2 n^2 比起來, 根本無足輕重。 如果說 2 n^2 是九牛, - 9 n 就是一毛; 如果說 - 9 n 是杯水, 2 n^2 就是車薪。 至於 -12, 那就是一毛上面的一隻細菌; 或者說是杯水裡面的兩滴。 所以 f(n) 屬於 Theta(2 n^2)。 不過根據 「方格紙原則」, 可以更簡寫成 f(n) 屬於 Theta(n^2)。

從例一可以推論出: 所有的多項式函數, 其實只需要看最高次項的次數就可以了。 例如若 f(n) = 0.25 n^7 - 3 n^5 + 26 n^ - 49 n + 144 則 f(n) 屬於 Theta(n^7); 用中文講就是 "f(n) 的成長速率與 n^7 差不多"。 擒賊先擒王。

另外提醒大家: Theta(2n^2-9n-12) = Theta(n^2) 是 集合的相等 ("與某甲差不多高的人所成集合 等於 與某乙差不多高的人所成集合"); 千萬不要寫成 2n^2-9n-12 = n^2 ("某甲等於某乙") 那就大錯特錯了。

例二: 請用 asymptotic notation 比較 f(n) = lg(n^3) 與 g(n) = log5(n^7) 兩函數的成長快慢。 因為我們資管系, 所以把所有的 log 都換成以 2 為底比較習慣 :-) f(n) = 3 lg(n) 而 g(n) = 7 log5(n) = 7 lg(n)/lg(5) 兩函數只差常數倍, 所以成長速率一樣快, 也就是說 f(n) 屬於 Theta(g(n))。

例三: f(n) = 2 sqrt(n) + 9 lg (n)。 請用最簡單, 最精確的 asymptotic notation 描述 f(n) 的成長速率。 這裡需要判斷 2 sqrt(n) 與 9 lg(n) 誰是九牛, 誰是一毛。 根據方格紙原則, 其實只需要比較 sqrt(n) 與 lg(n) 的快慢。 似乎還是有點難。 沒關係, 當你沒有頭緒的時候, 最簡單的方法就是真的代幾個 很大 的數字進去看看:

n 1 1K 1M 1G 1T
根號 n 1 31.6 1K 31.6K 1M
lg(n) 1 10 20 30 40

所以 lg(n) 屬於 o(sqrt(n)), 不困難吧? 基本上只需要有一部電子計算機, 就沒有什麼比不出來的函數。 如果函數不太複雜, 且你懂得挑選漂亮的數字, 那麼連計算機都不需要, 像這裡一樣。 又或者如果有一個簡單的數學繪圖軟體, 例如 gnuplot 下個指令, 就一目瞭然。 Q: 請比較這三個函數的成長速率: f(n) = (lg(n))^3, g(n) = lg(n^3), h(n) = 三次根號 n。 本頁原始碼當中的答案, 是否令你吃驚? 記得: 比較函數的成長速率, 要看很久, 很久, 很久以後的表現才算數。

Polynomial, Polylog, Exponential

從多項式的例子當中我們很容易得到推論: O(1) 包含於但不等於 O(三次根號 n) 包含於但不等於 O(根號 n) ... O(n) ... O(n^2) ... O(n^3) ... O(n^100) ... 成長速率約為 Theta(n^c) (c 為大於零的常數, 例如 1/3, 1/2, 1, 2, 3, 100, ... 等等) 的函數, 統稱其 growth rate 為 polynomial。

又從 lg 的例子當中發現, lg(n) 的 3 次方, 都還是比 n 的 1/3 次方成長得慢。 除了代入數字之外, 也可以用 gnuplot 畫畫看: 

    pow(x,y) = exp(log(x)*y)
    f(x) = pow(x,1.0/3)
    g(x) = pow(log(x),3)
    plot f(x),g(x)
    set xrange [1:1e6]
    replot
    set xrange [1:1e30]
    replot
    set xrange [1:1e14]
    replot

那麼 f(n) = (lg(n))^1000 與 g(n) = n^0.001 誰成長得比較快呢? 這次需要非常, 非常, 非常大的數字才看得出來:

n 1 1K 1T ... 2^1M 2^1G
f(n) - 2^3320 2^5320 ... 2^(2K) 2^(3K)
g(n) 1 1K 16K ... 2^(1K) 2^(1M)

難怪 linux 很難推廣, 因為真的要很久, 很久, 很久以後, 它才會超越 windows 的市場佔有率; 可是一般人沒有耐性看那麼遠, 所以沒有人願意相信 linux 將來會是主流 :-)

從以上我們看出, 在成長最慢的 polynomial 函數之下, 還擠著一堆互有高低的函數: O(1) 包含於但不等於 O(lg n) 包含於但不等於 O((lg n)^2) ... O((lg n)^1000) ... O(n^0.001)。 成長速率約為 Theta((lg n)^c) (c 為大於零的常數, 例如 1, 2, 1000, ... 等等) 的函數, 統稱其 growth rate 為 poly-logarithmic 或簡稱 poly-log。

另一方面, 2^n 的成長速率明顯地比 n^2 快。 我們不禁懷疑 2^(n/1000) 的成長速率還是比 n^1000 快。

n 1 1K 1M 1G
2^(n/1000) 1 2 10^300 10^(300K)
n^1000 1 10^(3K) 10^(6K) 10^(9K)

原來在成長最快的 polynomial 函數之上, 還有許多成長更快, 甚至彼此不同等級的函數! O(n^1000) 包含於但不等於 O(1.0007^n) 包含於但不等於 O(1.007^n) ... O(2^n) ... O(3^n) ... 。 成長速率約為 Theta(C^n) (c 為大於 1 的常數, 例如 1.001, 1.1, 2, 3 ... 等等) 的函數, 統稱其 growth rate 為 exponential。 (註: 2^(1/100)=1.0069556, 2^(1/1000)=1.0006934 )

如果說 polynomial 等級的函數是 格列佛, 那麼 poly-log 就是小人國; exponential 就是大人國。 Q: f(n) = n * lg(n) 是那一國的?

例: 比較 f(n) = 3^n n^7 (lg n)^5 與 g(n) = 5^n n^3 (lg n)^7 兩函數的成長速率快慢。 這裡, 兩個函數的 growth rate 都已經用最簡單的方式表達, 無法再化簡, 也就是說, f(n) 屬於 Theta(3^n n^7 (lg n)^5) 及 g(n) 屬於 Theta(5^n n^3 (lg n)^7) 已是最簡的寫法。 (註: 九牛一毛定理只能用在加法, 不能用在乘法; 要不然, n^7 = n^4 * n^3 ...) 想像兩個函數相除: f(n)/g(n) 會趨近於 0, 還是趨近於無窮大? 相除之後我們發現其實就是在比較三對 factors 的影響力。 當然是 exponential 部分的影響力最大, 所以 f(n) 屬於 o(g(n))。 一般說來, 遇到這種相乘的兩相比較, 如果 exponential 部分相當, 就比 polynomial 部分; 如果 polynomial 也相當, 最後才比 poly-log 部分。 就像在比數字大小一樣, 如果說 exponential 部分相當於十位數, 那麼 polynomail 部分就相當於個位數, 而 poly-log 部分就相當於小數點以下第一位。

數學感好的同學, 可能注意到 big-O-notation 與微積分裡面的極限好像有點關係。 沒錯, 其實這裡我們直覺地套用了一個定理: 兩函數的比值如果趨近於 0, 則表示放在分子處的函數成長速率較慢; 比值如果趨近於無窮大, 則表示放在分子處的函數成長速率較快; 至於比值如果趨近於一個正數 (重點是非零), 就表示兩函數成長速率相當。 作業: 請將上述定理翻譯成數學式。 答案在 定理摘要 某處。 (但若極限不存在, 未必就表示兩函數成長速率無法比較。)

有助於計算的技巧與公式

上述的定理摘要裡面, 有很多定理; 但請不要害怕, 即使不會用數學式嚴格證明, 也很容易猜出答案。 我們隨便舉一個定理來當做例子: 若 f(n) 屬於 O(g(n)), 且 g(n) 屬於 O(h(n)), 則 f(n) 與 h(n) 之間有什麼關係? 下面這個方法非常好用:

        數學前提 .....> 數學結論 
           |                  ^
           |                  |
           v                  |
        中文前提 -----> 中文結論

以本定理為例, 前提如果翻成中文, 就是: "f 成長速率不超過 g, 且 g 成長速率不超過 h" 結論當然就是: "f 成長速率不超過 h" 最後翻譯回數學式, 就是: f(n) 屬於 O(h(n))。 作業: 若 f(n) 屬於 O(g(n)), 且 g(n) 屬於 O(f(n)), 則可以得到什麼結論? 請用上述翻譯的方式推導出你的結論。 答案在本頁原始碼某處。

總之, 可以把 O 想成有點像是 <= 把 Omega 想成有點像是 >= 把 Theta 想成有點像是 =。 另外還有 o 有點像是 < 以及 omega 有點像是 >。 當然要注意這些符號定義出來的東西都是集合, 所以 寫法 與數字的大於等於小於很不相同; 但 想法 是類似的。 (常見錯誤寫法: 錯!錯!錯!==>f O b<==錯!錯!錯! 小考時, 比錯大小, 但符號正確, 還可以考慮給部分分數; 但如果像這樣寫, 一定不給分!)

例: 請估計 f(n) 的成長速率: 

	    (3^n + n) * sqrt(n^5 + 4n^2 + 9) * (log_10(n^2-5n+3))^3
    f(n) =  ---------------------------------------------------
	    (2^n + lg n) * (n^2 + sqrt(n)) * (log_16(n^3-2n+5))^7

分子各項的成長速率分別與 3^n, n^2.5, (lg n)^3 差不多; 分母各項的成長速率分別與 2^n, n^2, (lg n)^7 差不多, 所以 f(n) 屬於 Theta( (1.5)^n * n^0.5 / (lg n)^4 )。 這裡很直覺地用到幾個 (沒有教過) 的定理, 請按照上述方式翻譯成中文, 推想出結論, 再翻譯成數學式:

  1. 若 f1 屬於 Theta(g1) 且 f2 屬於 Theta(g2) 則 f1*f2 屬於 ...?
  2. 若 f1 屬於 Theta(g1) 且 f2 屬於 Theta(g2) 則 f1/f2 屬於 ...?

「小時候胖不算胖」 原則, 「方格紙 y 軸可以均勻縮放」 原則, 以及 「九牛一毛/杯水車薪」 定理, 雖然經常用到, 但請勿誤用。 例:

總之, 這些原則/定理, 要用在 函數整體, 不一定能從函數當中很深的地方隨便挖一項出來亂用。 一個不太精確的觀察給數學不好的同學參考: 躲在指數部分的函數, 需要算得很精確; 躲在多項式或根號裡面的項, 可以用 「適用於最外層的原則/定理」 先簡化; 躲在 log 裡面的項, 不僅可以用上述原則/定理, 有時還可以忽略更多東西。

至於想要走研究路線的同學, 要知道上述技巧是只問結果不問過程的 「補習班式速學法」; 嚴謹的證明方式應該從定義裡面的 C 與 n0 出發。

更多參考資料: 定理摘要, 一些例題, 及 Wilf 書中的 1.1 節。

Theta(f(n)) 包含於 O(f(n)), 又 Theta(f(n)) 包含於 Omega(f(n))。 事實上 Theta(f(n)) 正好等於 「O(f(n)) 交集 Omega(f(n))」

級數求和

  1. 請複習離散數學的 「遞迴關係式 recurrence relations」 及 「數學歸納法 mathematical induction」。
  2. 1 + 2 + 3 ... + n = n(n+1)/2
  3. 1 + 4 + 9 ... + n^2 = n(n+2)(2n+1)/6
  4. Q: 猜猜看 1^7 + 2^7 + 3^7 ... + n^7 屬於 Theta(n^?)
  5. 1 + r + r^2 + r^3 ... + r^n = (r^(n+1)-1)/(r-1) 屬於 Theta(r^n)
  6. 若 |r| < 1 則 r + 2r^2 + 3r^3 ... = r/(1-r)^2
  7. 1 + 1/2 + 1/3 ... + 1/n 屬於 Theta(lg n) (可以用畫圖, 積分得出。) (常用!)
  8. ln (n!) 大約等於 n ln (n) (Stirling's approximation) (常用!)
  9. The Master Theorem: 不需要記這個公式; 但是遇到合適的場合, 要記得有這個公式可以用。

一些練習題

以下較進階

Asymptotic Notations 的三一律 ... 並沒有!

數字的比較, 有 「三一律」; 函數的比較並沒有。 也就是說, 兩個數字 a 與 b 相比較時, 不是 a<b 或是 a=b 就是 a>b ; 但兩個函數 f 與 g 相比較時, 可能 f 既不屬於 o(g) 也不屬於 Theta(g), 也不屬於 omega(g)。 例如 f(n) = n 與 g(n) = n^(1+sin(n)) 兩者就無法比較成長速率的快慢。

Big-O Notation 與 Binary Relations

請複習離散數學的 「關係 relations」。 若在「所有非負數列所成的集合」上面定義一個二元關係 (binary relation) "f @ g <==> f(n) is in Theta(g(n))", 則 @ 滿足 transitivity, reflexivity, 及 symmetry。 也就是說 @ 是一個 equivalence relation。 @ 所定義出來的 equivalence classes 在「所有非負數列所成的集合」上造成一個分割 (partition)。 用 O, Theta, Omega, o, omega 等運算在這些 equivalence classes 所成的集合上如法泡製, 定義出相對應的 binary relations, 則可看出 O 與 Omega 都是 partial ordering relations。