摘要訊息 : 在不同程序步伐標準下, 漸近分析提供了演算法分析和比較的數學基礎.

0. 前言

我們在《程式碼效能分析》中提到, 對於空間複雜度和時間複雜度的理論分析, 不同的人會有不同的標準. 特別是針對時間複雜度, 有些人可能得到程式 P 的時間複雜度為 T_{P}(n) = 2n^{2} + 4n + 1, 而另外一些人由於不同的標準可能會得到 T_{P}(n) = n^{2} + 12n + 22. 在《程式碼效能分析》中我們強調, 這樣的比較只能在一個標準下和同任務不同程式的程式之間進行比較. 那麼在不同人有不同標準的前提下, 如何在不同標準下進行比較就成為了一個最大的問題.

漸近分析是數學分析的一個分支, 它專門用於分析函數在極限附近的行為, 特別是當實體特徵 n 特別大的時候. 因此, 漸近分析可以作為不同標準下的步伐函數的分析基礎.

Tip : 本文需要閣下具有數學分析中極限理論的基礎.

更新紀錄 :

• 2022 年 5 月 2 日進行第一次更新和修正.

1. 漸近比較

雖然在實體特徵 n 比較小的時候, 我們很難比較程式的步伐函數, 但是當 n 充分大 (n \to \infty) 的時候, 我們是可以精確地預計程式運作時間的增長, 以比較兩個程式的性能. 例如, 某個程式的步伐為 T_{1}(n) = c_{1}n^{2} + c_{2}n + c_{3} (c_{1} > 0, c_{1}, c_{2} 和 c_{3} 為任意常數), 另外一個程式的步伐為 T_{2}(n) = c_{4}n + c_{5} (c_{4} > 0, c_{4} 和 c_{5} 為任意常數). 當 n 充分大的時候, 第一個程式的程式步伐會比第二個程式的程式步伐大得多, 因為 \displaystyle {\lim \limits_{n \to \infty} \frac {c_{1}n^{2} + c_{2}n + c_{3}}{c_{4}n + c_{5}} = \infty}. 而對於 T_{1}(n) 來說, 若不考慮 c_{1}, c_{2} 和 c_{3} 的具體值, 當 n 增大的時候, 整個表達式的增長最終取決於第一項 c_{1}n^{2} 的增長. 令 R_{n} = \frac {c_{2}n + c_{3}}{c_{1}n^{2}}, 顯然當 n \to \infty 的時候同時有 R_{n} \to 0. 因此, 當 n 充分大, c_{2}n + c_{3} 與 c_{1}n^{2} 相比, 其大小無關緊要. 於是, 一個程式的運作時間可以近似得使用 c_{1}n^{2} 來表示.

設 n_{1} 和 n_{2} 是兩個關於 n 的較大值, 記 T(n) = c_{1}n^{2} + c_{2}n + c_{3}, 並令 T = \frac {t(n_{1})}{t(n_{2})}, 則有 \displaystyle {T(n) = \frac {t(n_{1})}{t(n_{2})} = \frac {c_{1}n_{1}^{2}+c_{2}n_{1}+c_{3}}{c_{1}n_{2}^{2}+c_{2}n_{2}+c_{3}}}. 由於 n_{1} 和 n_{2} 足夠大, 所以有 \displaystyle {T(n) \doteq \frac {c_{1}n_{1}^{2}}{c_{1}n_{2}^{2}} = \left ( \frac {n_{1}}{n_{2}} \right )^{2}}. 若 n_{1} = 2n, n_{2} = n, 則有 \displaystyle {T(n) = 4}. 即當實體特徵增大 2 倍的時候, 程式運作時間近似地增大到原來的 4 倍. 類似地, 令 n_{2} 保持不變, n_{1} = 3n, 則 T = 9; ... 最終我們認識到, 只要知道程式步伐的最大項為 n^{2} 就可以了, 其係數 c_{1} 也和 c_{2}n + c_{3} 那樣無關緊要.

綜上所述, 令 p(n) 和 q(n) 是兩個非負值函數, 若滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {q(n)}{p(n)} = 0 \text { 或 } \lim \limits_{n \to \infty} \frac {p(n)}{q(n)} = \infty} 時, 稱 p(n) 漸近地大於 q(n), q(n) 漸近地小於 p(n); 若滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {p(n)}{q(n)} = 0 \text { 或 } \lim \limits_{n \to \infty} \frac {q(n)}{p(n)} = \infty} 時, 稱 q(n) 漸近地大於 p(n), p(n) 漸近地小於 q(n); 若 \displaystyle {\lim \limits_{n \to \infty} \frac {p(n)}{q(n)} = \lim \limits_{n \to \infty} \frac {q(n)}{p(n)} = 1} 時, 稱 q(n) 漸近地等於 p(n), p(n) 漸近地等於 q(n).

2. 非漸近比較

假定程式 A 和程式 B 具有相同的功能, 有兩個人 H 和 W 對這兩個程式進行了步伐分析. H 對程式 A 分析後得到程式 A 的步伐函數 t_{A}^{\mathrm {H}}(n) = n^{2} + 3n, 對程式 B 分析後得到 t_{B}^{\mathrm {H}}(n) = n + 1; W 對程式 A 分析後得到程式 A 的步伐函數為 t_{A}^{\mathrm {W}}(n) = n^{2} + n, 對程式 B 分析後得到 t_{B}^{\mathrm {W}}(n) = n. 如果 H 和 W 這兩個人的分析是正確的, 那麼任何人的分析結果想要正確, 其必須滿足 \displaystyle {t_{A}(n) = c_{1}n^{2} + c_{2}n + c_{3}, t_{B}(n) = c_{4}n + c_{5}}. 其中, c_{1}, c_{2}, c_{3}, c_{4} 和 c_{5} 為任意常數, c_{1} > 0 且 c_{4} > 0.

顯然, t = t_{A}^{\mathrm {H}}(n) 和 t = t_{B}^{\mathrm {H}}(n) 是兩條不同的曲線 :

同樣地, t = t_{A}^{\mathrm {W}}(n) 和 t = t_{B}^{\mathrm {W}}(n) 也是兩條不同的曲線 :

最終, 不論 t_{A}(n) 與 t_{B}(n) 的結果如何, 只要分析正確, 必定有一個非負的均衡點 n_{0}. 當 n < n_{0} 的時候, 程式 A 更快; 當 n > n_{0} 的時候, 程式 B 更快.

3. 實用漸近記法

接下來, 我們將對漸近記法進行研究, 為的就是能夠得到更加通用的比較方法, 而不是像第 1 節那樣空虛的分析, 也不像第 2 節那樣計算過於繁瑣. 我們用 f(n) 和 g(n) 來表示兩個程式的空間複雜度或者時間複雜度函數. 其中, n 是實體特徵, f(n) \geq 0 且 g(n) \geq 0.

我們在《程式碼效能分析》中提到的程式步伐和時間複雜度實際上是廣義等價的概念, 因為它們最終都會變成相同的時間複雜度函數. 對於程式使用的空間和空間複雜度, 最終也將會被表示為空間複雜度函數. 漸近記法就是用複雜度函數中最大的那一項來描述複雜度.

實用定義 1. (大 O 記法) 標記 f(n) = O(g(n)) 表示函數 f(n) 漸近地小於或等於函數 g(n), 即 f(n) 和 g(n) 滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = 0 \text { 或 } \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = \lim \limits_{n \to \infty} \frac {g(n)}{f(n)} = c}. 其中, c > 0 且 c 是任意常數.

在漸近的意義上, 標記 f(n) = O(g(n)) 表示函數 g(n) 是函數 f(n) 的上限. 需要指出的是, 此處的大 O 記法的定義並非嚴格定義, 而是實用定義. 對於 f(n) = O(g(n)), 除了函數 f(n) = 0 以外, 函數 g(n) 習慣上是一個單位項, 即一個係數為 1 的單項, 而且通常是令 f(n) = O(g(n)) 能夠成立的最小單位項. 當 f(n) = 0 時, g(n) = 0. 例如, f(n) = 3n, 而 g(n) = 2n^{2}, 我們可以寫成 f(n) = O(2n^{2}), 但是更加通用的寫法是 f(n) = O(n^{2}).

在漸近分析中, 我們要確定一個最大項以表示複雜度, 而且把這個最大項的係數置為 1. 例如對於函數 \displaystyle {f(n) = 3n^{3} + 4n^{2} + 8n\log_{3} n + 6n + 5\log_{2} n + 4}, 的單位項分別是 n^{3}, n^{2}, n\log n, n, \log n 和 1. 若一個程式的程式步伐函數就是 f(n), 則其漸近複雜度為 O(n^{3}).

由於漸近分析是分析 n 充分大時的函數的工具, 所以 f(n) = O(g(n)) 與 O(g(n)) = f(n) 不同. 實際上, 後者沒有任何意義. 等號在此處表示的 "是" 的含義, 而非表面上相等的含義. 將 f(n) = O(g(n)) 翻譯為英文, 讀作 f(n) is big oh of g(n).

實用定義 1'. (多變數大 O 記法) 標記 f(n_{1}, n_{2}, ..., n_{m}) = O(g(n_{1}, n_{2}, ..., n_{m})) 表示多變數函數 f(n_{1}, n_{2}, ..., n_{m}) 漸近地小於或等於多變數函數 g(n_{1}, n_{2}, ..., n_{m}), 即 f(n_{1}, n_{2}, ..., n_{m}) 和 g(n_{1}, n_{2}, ..., n_{m}) 滿足 \displaystyle {\lim \limits_{n_{i} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = 0 \text { 且 } \lim \limits_{n_{j} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = c}. 其中, c \geq 0, c 為任意常數, i = 1, 2, ..., n 且 j = 1, 2, ..., i - 1, i + 1, i + 2, ..., n.

雖然實用定義 1 比較複雜, 但是實際上使用的時候比較簡單. 令 f(x_{1}, x_{2}, ..., x_{n}) 是一個複雜度函數, 其中任一項若漸近小於剩餘的項, 那麼都可以將其去除, 然後把最終剩下的項的係數更改為 1 就可以了. 例如 f(m, n) = m^{3} + 3m^{2}n + 10mn + 2n^{2} + n + 42, 可以記為 \displaystyle {f(m, n) = O(m^{3} + m^{2}n + n^{2})}.

實用定義 2. (Θ 記法) 標記 f(n) = \Theta(g(n)) 表示函數 f(n) 漸近地等於函數 g(n), 即 f(n) 和 g(n) 滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = \lim \limits_{n \to \infty} \frac {g(n)}{f(n)} = c}. 其中, c > 0 且 c 是任意常數.

實用定義 2'. (多變數 Θ 記法) 標記 f(n_{1}, n_{2}, ..., n_{m}) = \Theta(g(n_{1}, n_{2}, ..., n_{m})) 表示多變數函數 f(n_{1}, n_{2}, ..., n_{m}) 漸近地小於或等於多變數函數 g(n_{1}, n_{2}, ..., n_{m}), 即 f(n_{1}, n_{2}, ..., n_{m}) 和 g(n_{1}, n_{2}, ..., n_{m}) 滿足 \displaystyle {\lim \limits_{n_{i} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = c \text { 且 } \lim \limits_{n_{j} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} \neq \begin {cases} 0 \\ \infty. \end {cases}} 其中, c \geq 0, c 為任意常數, i = 1, 2, ..., n 且 j = 1, 2, ..., i - 1, i + 1, i + 2, ..., n.

實用定義 3. (Ω 記法) 標記 f(n) = \Omega(g(n)) 表示函數 f(n) 漸近地大於或等於函數 g(n), 即 f(n) 和 g(n) 滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = \infty \text { 或 } \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = \lim \limits_{n \to \infty} \frac {g(n)}{f(n)} = c}. 其中, c > 0 且 c 是任意常數.

實用定義 3'. (多變數 Ω 記法) 標記 f(n_{1}, n_{2}, ..., n_{m}) = \Omega(g(n_{1}, n_{2}, ..., n_{m})) 表示多變數函數 f(n_{1}, n_{2}, ..., n_{m}) 漸近地大於或等於多變數函數 g(n_{1}, n_{2}, ..., n_{m}), 即 f(n_{1}, n_{2}, ..., n_{m}) 和 g(n_{1}, n_{2}, ..., n_{m}) 滿足 \displaystyle {\lim \limits_{n_{i} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = \infty \text { 或 } \lim \limits_{n_{j} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = c}. 其中, c \geq 0, c 為任意常數, i = 1, 2, ..., n 且 j = 1, 2, ..., i - 1, i + 1, i + 2, ..., n.

實用定義 4. (小 o 記法) 標記 f(n) = o(g(n)) 表示函數 f(n) 漸近地小於函數 g(n), 即 f(n) 和 g(n) 滿足 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = 0}. 其中, c > 0 且 c 是任意常數.

實用定義 4'. (多變數小 o 記法) 標記 f(n_{1}, n_{2}, ..., n_{m}) = o(g(n_{1}, n_{2}, ..., n_{m})) 表示多變數函數 f(n_{1}, n_{2}, ..., n_{m}) 漸近地小於或等於多變數函數 g(n_{1}, n_{2}, ..., n_{m}), 即 f(n_{1}, n_{2}, ..., n_{m}) 和 g(n_{1}, n_{2}, ..., n_{m}) 滿足 \displaystyle {\lim \limits_{n_{i} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = 0 \text { 且 } \lim \limits_{n_{j} \to \infty}\frac {f(n_{1}, n_{2}, ..., n_{m})}{g(n_{1}, n_{2}, ..., n_{m})} = c}. 其中, c \geq 0, c 為任意常數, i = 1, 2, ..., n 且 j = 1, 2, ..., i - 1, i + 1, i + 2, ..., n.

對於函數 \displaystyle {f(n) = 3n^{3} + 4n^{2} + 8n\log_{3} n + 6n + 5\log_{2} n + 4}, 根據這些記法的定義, 我們可以同時得到 f(n) = O(n^{3}), f(n) = \Theta(n^{3}) 和 f(n) = \Omega(n^{3}). 大 O 記法在資料結構或者演算法的複雜度分析中是最常用的, 小 o 記法不太常見. 不過, 小 o 記法在數學分析中非常常見, 它就是高階無窮小的別名.

從漸近分析的意義上來說, 若有 f(n) = O(g(n)), 則函數 g(n) 是函數 f(n) 的上界; 若有f(n) = \Omega(g(n)), 則函數 g(n) 是函數 f(n) 的下界. 若有 f(n) = \Theta(g(n)), 那麼稱函數 f(n) 有界, 即函數 f(n) 既有上界也有下界.

有時候, 我們會遇到單個的 O(g(n)), \Theta(g(n)) 和 \Omega(g(n)), 那麼可以將其視為一個集合 :

• O(g(n)) : O(g(n)) = \left \{ f(n) : f(n) = O(g(n)) \right \};
• \Theta(g(n)) : \Theta(g(n)) = \left \{ f(n) : f(n) = \Theta(g(n)) \right \};
• \Omega(g(n)) : \Omega(g(n)) = \left \{ f(n) : f(n) = \Omega(g(n)) \right \}.

基於這種解釋, 於是有類似於 O(g_{1}(n)) = O(g_{2}(n)) 的表示方法.

我們給定經常在步伐函數中經常出現的項 :

這裡需要注意, 這裡給定的項係數都為 1. 但是在實際分析中, 項係數不一定為 1, 可能具有不同的值. 特別指出, 對於對數, 不妨設其底數為 a, 那麼有 \displaystyle {\log_{a} n = \log_{a} b \cdot \log_{b} n}. 其中, a > 1 且 b > 1. 因此, 對數函數的底數通常會被省略. 同時也說明了任意底數 a 的對數 (a > 1) 是漸近相等的.

根據增長的趨勢, 我們容易地得到這些項的大小排列 : \displaystyle {1 < \log n < n < n\log n < n^{2} < n^{2}\log n < n^{3} < 2^{n} < n!}. 其中, < 表示漸近小於, 而不是比較符號.

4. 漸近分析

Tip : 本節較難, 僅建議學習過數學分析中極限定義的讀者閱讀.

我們在第 3 節介紹了了大 O 記法, Ω 記法和 Θ 記法的實用定義. 如果閣下對數學具有高度敏感性, 那麼可以發現之前給出的實用定義還不夠詳細. 雖然我們已經給出了什麼叫做漸近大於, 漸近等於和漸近小於, 但是這些都不是精確的定義. 接著, 我們需要給出它們的精確定義, 否則某些定理或著結論我們沒有辦法去證明. 值得注意的是, 小 o 記法的定義可以由大 O 記法, Ω 記法和 Θ 記法的定義推出.

定義 1. (大 O 記法) 對於函數 f(n) 和 g(n), 若且唯若存在常數 c > 0 和正整數 N, 使得對於所有的 n \geq N 都有 \displaystyle {f(n) \leq cg(n)} 成立, 那麼我們記 f(n) = O(g(n)).

當 n \geq N 時, 有 f(n) \leq cg(n) 成立, 這說明當 n 充分大的時候, cg(n) 是 f(n) 的一個上界. 任取正整數 N, 函數值 f(n) 可能大於, 小於或等於函數值 cg(n), 但是一定存在一個正整數 N_{0}, 當 n \geq N_{0} 時, f(n) 的函數值永遠不會大於 cg(n) 的函數值. 例如 Figure 1-1 中, 當 n > \sqrt {2} - 1 時, 永遠不會有 T_{B}^{\mathrm {H}}(n) \leq T_{A}^{\mathrm {H}}(n) 成立.

和實用定義 1 類似, 對於 O(g(n)) 中的 g(n), 一般只是用一個變數 n 且係數為 1 的單項表示. 這個對於其它記法也是成立的.

斷言1. 證明 f(n) = 3n^{2}2^{n} + 4n2^{n} + 8n^{2} \neq O(2^{n}).

證明 :

我們使用歸謬法進行證明. 不妨設 f(n) = 3n^{2}2^{n} + 4n2^{n} + 8n^{2} = O(2^{n}). 根據大 O 記法的定義, 存在某個常數 c > 0 和一個正整數 N, 當 n \geq N 的時候, 有 \displaystyle {f(n) \leq c \cdot 2^{n}}, 即 \displaystyle {3n^{2}2_{n} + 4n2^{n} + 8n^{2} \leq c \cdot 2^{n}}. 不等式兩側同乘 \frac {1}{2^{n}}, 可得 \displaystyle {3n^{2} + 4n + \frac {8n^{2}}{2^{n}} \leq c}.

令 g(x) = 3x^{2} + 4x + \frac {8x^{2}}{2^{x}}, 則 g'(x) = 6x + 4 + 2^{3-x}x(2 - \ln 2x). 令 g'(x) = 0, 可知使得 g(x) = 0 的點 x = x_{0} < 0. 而 g(0) > 0, 則 g(x) 在 (0, + \infty) 上單調增加. 故對於任意 n > 0, g(n) 單調增加. 由於 c 是常數, 因此 3n^{2} + 4n + \frac {8n^{2}}{2^{n}} \leq c 僅在有限處成立. 因此假設不成立.

綜上所述, f(n) = 3n^{2}2_{n} + 4n2^{n} + 8n^{2} \neq O(2^{n}).

\blacksquare

事實上, 我們有 f(n) = 3n^{2}2^{n} + 4n2^{n} + 8n^{2} = O(n^{2}2^{n}).

f(n) = O(g(n)) 表明存在一個常數 c > 0 和正整數 N, 當 n \geq N 時, cg(n) 是 f(n) 的上限, 並未表明這個上限是否為 f(n) 的最小上限 (即上確界). 因此為了使得 f(n) = O(g(n)) 有實際意義, g(n) 應該儘量小. 例如 2n^{2} + n = O(n^{n}) 就沒有太大意義, 2n^{2} + n = O(n^{2}) 的實用意義比較大.

定理 1. 設函數 f(n) = a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{1}n + a_{0}, 其中 a_{m} > 0. 那麼 f(n) = O(n^{m}).

證明 :

首先, 我們注意到 n \geq 1, 於是我們可以得到 \displaystyle {f(n) \leq \sum \limits_{i = 0}^{m} |a_{i}| n^{i} \leq n^{m} \sum \limits_{i = 0}^{m} |a_{i}| n^{i - m} \leq n^{m} \sum \limits_{i = 0}^{m} |a_{i}|}. 根據的定義 1, 因此有 f(n) = O(n^{m}).

\blacksquare

定理 2. (大 O 記法比率定理) 假設函數 f(n) 和 g(n) 滿足極限 \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} 存在, 若且唯若存在常數 c 使得 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c} 成立時, 有 f(n) = O(g(n)).

證明 :

要證明這個定理成立, 其實就是要證明使得 f(n) = O(g(n)) 成立的充分必要條件是存在常數 c, 使得 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c}.

若有 f(n) = O(g(n)) 成立, 則根據定義 1, 存在常數 c > 0 和正整數 N, 當 n \geq N 時, 有 f(n) \leq cg(n), 即 \frac {f(n)}{g(n)} \leq c, 亦即 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c}.

\square

若 \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c 成立, 根據數列極限的定義, 存在正整數 N, 當 n \geq N 時, 有 \displaystyle {\left | \frac {f(n)}{g(n)} - c_{0} \right | \leq \varepsilon}. 其中, \lim \limits_{n \to \infty} \frac{f(n)}{g(n)} = c_{0} \leq c, \varepsilon > 0. 則有 \displaystyle {-\varepsilon + c_{0} \leq \frac {f(n)}{g(n)} \leq \varepsilon + c_{0}}, 即 f(n) \leq (\varepsilon + c_{0})g(n). 取 c = \max \left \{ 1, \varepsilon + c_{0} \right \}, 於是有 f(n) \leq cg(n) 成立.

\square

綜上所述, f(n) = O(g(n)) 成立的充分必要條件是存在常數 c, 使得 \displaystyle {\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c}.

\blacksquare

使用大 O 記法比率定理, 我們可以很快地得到 g(n). 例如有函數 f(n) = c_{1}n^{2} + c_{2}n + c_{3}, 其中 c_{1} > 0, 由於 \displaystyle {\lim \limits_{n \to \infty} \frac {c_{1}n^{2} + c_{2}n + c_{3}}{n^{2}} = c_{1}}, 任取 c (c \geq c_{1}), 有 f(n) \leq c_{1}n^{2}. 因此, 由大 O 記法比率定理可知 \displaystyle {f(n) = O(n^{2})}.

定義 2. (Ω 記法) 對於函數 f(n) 和 g(n), 若且唯若存在常數 c > 0 和正整數 N, 使得對於所有的 n \geq N 都有 \displaystyle {f(n) \geq cg(n)} 成立時, 我們記 f(n) = \Omega(g(n)).

定理 3. 設函數 f(n) = a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{1}n + a_{0}, 其中 a_{m} > 0, 那麼 f(n) = \Omega(n^{m}).

證明 :

我們通過不斷縮小 f(n), 可以觀察到 \displaystyle {\begin {aligned} f(n) &= a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{1}n + a_{0} \\ &\geq a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{1}n \\ &\geq a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{2}n^{2} \\ &\geq ... \\ &\geq a_{m}n^{m} + a_{m - 1}n^{m - 1} \geq a_{m}n^{m}. \end {aligned}} 根據定義 2, 有 \displaystyle {f(n) = \Omega(n^{m})}.

\blacksquare

定理 4. (Ω 記法比率定理) 假設函數 f(n) 和 g(n) 滿足極限 \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} 存在, 若且唯若存在常數 c 使得 \displaystyle {\lim \limits_{n \to \infty} \frac {g(n)}{f(n)} \leq c} 成立時, 有 f(n) = \Omega(g(n)).

這個定理的證明和大 O 記法比率定理的證明相同, 此處我們不再重複證明, 閣下也可以自己嘗試證明這個定理.

定義 3. (Θ 記法) 對於函數 f(n) 和 g(n), 若且唯若存在常數 c_{1} > 0, c_{2} > 0 和正整數 N, 使得對於所有的 n \geq N 都有 \displaystyle {c_{1}g(n) \geq f(n) \geq c_{2}g(n)} 成立時, 我們記 f(n) = \Theta(g(n)).

定理 5. 設函數 f(n) = a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{1}n + a_{0}, 其中 a_{m} > 0, 那麼 f(n) = \Theta(n^{m}).

證明 :

根據定理 1 和定理 3, 有 \displaystyle {a_{m}n^{m} \leq f(n) \leq n^{m} \sum \limits_{i = 0}^{m} |a_{i}|}. 取 c_{1} = a_{m}, c_{2} = \sum \limits_{i = 0}^{m} |a_{i}|, 根據定義 3, 有 f(n) = \Theta(n^{m})

\blacksquare

定理 6. (Θ 記法比率定理) 假設函數 f = f(n), g = g(n) 滿足極限 \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} 及 \lim \limits_{n \to \infty} \frac {g(n)}{f(n)} 存在, 若且唯若存在常數 c 使得 \displaystyle {\lim \limits_{n \to \infty} \frac {g(n)}{f(n)} \leq c \text { 且 } \lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c} 成立時, 有 f(n) = \Theta(g(n)).

Θ 記法比率定理結合大 O 記法比率定理和 Ω 記法比率定理 可以證明, 閣下可以自己嘗試證明.

通過對定理 5 和 Θ 記法比率定理的分析, 我們可以得到關於 Θ 記法的另外一種定義.

定義 3'. (Θ 記法) 對於函數 f(n) 和 g(n), 若有 f(n) = O(g(n)) 與 f(n) = \Omega(g(n)) 同時成立, 我們記 f(n) = \Theta(g(n)).

定義 4. (小 o 記法) 對於函數 f(n) 和 g(n), 若有 f(n) = O(g(n)) 與 f(n) \neq \Omega(g(n)) 同時成立, 我們記f(n) = o(g(n)).

小 o 記法經常用於步伐函數的分析. 在步伐函數的分析中, 小於 \Theta(n) 的部分通常可以忽略不計. 例如函數 f(n) = c_{1}n^{2} + c_{2}n + c_{3}, 其中 c_{1} > 0, 可以將 f(n) 記為 f(n) = c_{1}n^{2} + o(n^{2}). 在數學分析中, 這就是高階無窮小的用法之一.

我們在第 3 節說過, 大 O 記法和 Θ 記法比較常用, 而 Ω 記法不是很常用. 現在我們有了它們的精確定義, 來闡述一下得到這個斷言的原因. 大 O 記法實際上是程式步伐函數的上界, 也就是說若有 f(n) = O(g(n)), 那麼程式運作時間不會大於 cg(n); Ω 記法是程式步伐函數的下界, 也就是說若有 f(n) = \Omega(g(n)), 那麼程式運作時間不小於 cg(n); Θ 記法是程式步伐函數的確界, 也就說若有 f(n) = \Theta(g(n)), 那麼程式的運作時間會介於 c_{1}g(n) 和 c_{2}g(n) 之間. 其中, c > 0, c_{2} > c_{1} > 0, c, c_{1} 和 c_{2} 都為任意常數. 對於任意演算法來說, 我們非常自然地就會限制演算法運作時間的上界, 因為我們不希望演算法用時過長, 也就是時間複雜度過高. 然而, 我們幾乎不會關心一個演算法的運作時間的下界, 因為這幾乎沒什麼用. 因此, 大 O 記法比 Ω 記法要常用得多. 但是, 我們為什麼又會說 Θ 記法也比較常用呢? 這是因為對於很多演算法, 我們確實可以證明它的步伐函數存在下界, 與其模模糊糊地使用大 O 記法描述, 倒不如 Θ 記法更精確一些 (我在很多資料結構和演算法的文章中都使用了這種精確記法). 這就是為什麼有些人更喜歡 Θ 記法的原因. 但是要想要精確, 我們就必須證明步伐函數的下界存在, 大部分人不喜歡過多的證明, 因此大 O 記法會比 Θ 記法用得多一些. 一般來說, 如果我們證明了某個步伐函數的上界確實存在, 順手也證明了步伐函數也存在下界, 此時就會使用 Θ 記法; 否則, 我們更多地使用大 O 記法.

任取 \varepsilon > 0, 令 x > 0, 下面結論均成立 :

• 存在正整數 N, 當 n \geq N 時, 有 (\log n)x < (\log n)^{x + \varepsilon};
• 存在正整數 N, 當 n \geq N 時, 有 (\log n)x <n^{\varepsilon};
• 存在正整數 N, 當 n \geq N 時, 有 n^{x} < n^{x + \varepsilon};
• 存在正整數 N, 當 n \geq N 時, 有 n^{x} < 2^{n}
• 對於任意實數 y, 存在正整數 N, 當 n \geq N 時, 有 n^{x} (\log n)^{y} < n^{x + \varepsilon}.

使用函數的單調性就可以證明上述結論, 此處不再證明.

對於某些函數 f(n), 我們直接給出漸近分析中的某些結論 :

• f(n) = c \Rightarrow f(n) = \bigoplus(1);
• f(n) = \sum \limits_{i = 0}^{k} c_{i}n^{i} \Rightarrow f(n) = \bigoplus(n^{k});
• f(n) = \sum \limits_{i = 0}^{n} i \Rightarrow f(n) = \bigoplus(n^{2});
• f(n) = \sum \limits_{i = 0}^{n} i^{2} \Rightarrow f(n) = \bigoplus(n^{3});
• f(n) = \sum \limits_{i = 0}^{n} i^{k} (k > 0) \Rightarrow f(n) = \bigoplus(n^{k + 1});
• f(n) = \sum \limits_{i = 0}^{n} r^{i} (r > 1) \Rightarrow f(n) = \bigoplus(r^{n});
• f(n) = \sum \limits_{i = 0}^{n} \frac {1}{i} \Rightarrow f(n) = \bigoplus(\log n);
• f(n) = n! \Rightarrow f(n) = \bigoplus(\sqrt {n} (\frac {n}{e})^{n});
• f(n) = \bigoplus(g(n)) \Rightarrow \sum \limits_{n = a}^{b} f(n) = \bigoplus(\sum \limits_{n = a}^{b}g(n));
• f_{i}(n) = \bigoplus(g(n)) (1 \leq i \leq k) \Rightarrow \sum \limits_{i = 1}^{k}f_{i}(n) = \bigoplus(\max \limits_{1 \leq i \leq k}{g_{i}(n)});
• f_{i}(n) = \bigoplus(g(n)) (1 \leq i \leq k) \Rightarrow \prod \limits_{i = 1}^{k}f_{i}(n) = \bigoplus(\prod \limits_{i = 1}^{k}{g_{i}(n)});
• f_{1}(n) = O(g_{1}(n)), f_{2}(n) = \Theta(g_{2}(n)) \Rightarrow f_{1}(n) + f_{2}(n) = O(g_{1}(n) + g_{2}(n));
• f_{1}(n) = \Theta(g_{1}(n)), f_{2}(n) = \Omega(g_{2}(n)) \Rightarrow f_{1}(n) + f_{2}(n) = \Omega(g_{1}(n) + g_{2}(n));
• f_{1}(n) = O(g(n)), f_{2}(n) = \Theta(g(n)) \Rightarrow f_{1}(n) + f_{2}(n) = \Theta(g(n)).

其中, c > 0, c_{1} > 0, k 與 r 為正整數, c, c_{1}, c_{2}, ..., c_{n} 為任意常數, \bigoplus 表示 O、\Omega 和 \Theta 中的任意一個.

5. 演算法選擇

在演算法功能相同的情況下, 我們通常使用複雜度較小的演算法. 但是這個描述其實不太準確. 準確地說, 在實體特徵 n 比較大的時候, 我們選用複雜度較小的演算法. 若程式 P 的時間複雜度為 \Theta(n), 而程式 Q 的時間複雜度為 \Theta(n^{2}), 那麼可以斷定, 若 n 充分大, 那麼程式 P 的速度快於程式 Q. 而 n 充分大具體如何大, 是可以使用實際數字來表示的. 比如程式 P 的程式步伐函數為 P(n) = 6n + 1, 程式 Q 的程式步伐函數為 Q(n) = n^{2} + 2, 那麼令 Q(n) > P(n), 即 n^{2} + 2 > 6n + 1. 解得 n < -2\sqrt {2} + 3 或者 n > 2\sqrt {2} + 3. 由於 -2\sqrt {2} + 3 < 1, 因此這個解可以不必考慮. 大於 2\sqrt {2} + 3 的整數有很多, 任取一個作為 N, 當實體特徵 n > N 時, 程式 P 的速度更快. 但是如果 n \in \{ 1, 2, 3, 4, 5 \} 時, 程式 Q 速度更快. 這個其實在 Figure 1-1 和 Figure 1-2 中就可以體現出來.

C++ 標準樣板程式庫中的 std::sort 就結合了多種排序演算法. 當 n 比較小的時候, std::sort 會採用選擇排序法和插入排序法. 因為這個時候這兩個排序演算法比快速排序法還要快. 只有當 n 大到一定規模的時候, std::sort 才選用快速排序法. 當 n 非常大的時候, 會導致使用遞迴的快速排序法遞迴深度太高, 這個時候 std::sort 會採用合併排序法.

如果一個程式的時間複雜度是次數較高的多項式級別, 指數級別甚至階乘級別, 那麼隨著實體特徵 n 的增大, 那麼程式的程式步伐 (或者說程式的運作時間) 的增加速度會非常快, 最終導致程式運作緩慢. 因此, 在這樣的情況下, 我們應該儘量控制實體特徵 n 或著限制程式的使用. 一旦找到時間複雜度較低的演算法, 我們需要重新改寫這個程式.

漸近分析僅針對足夠大的 n 給出了程式的時間複雜度. 當 n 比較小的時候, 程式的運作時間可能不足以滿足漸近曲線. 為了確定漸近曲線以外的點, 我們需要檢查若干個 n 值所對應的運作時間, 此時就需要對程式步伐進行細緻分析.