漸近分析基礎

考察一個程式的作業計數和程式步伐主要有兩個原因 :

預測程式運作的時間如何隨著實體特徵的變化而變化
對兩個相同功能的演算法, 比較它們的時間複雜度

在使用作業計數的時候, 我們通常選擇我們感興趣的部分而暫時忽略了其它因素. 因此, 這種方法在選擇的時候, 應該儘量謹慎

作業計數說明的僅僅是一個程式的部分工作, 而程式步伐要說明所有工作. 但是由於程式步伐沒有精確定義, 陳述式 x = y 以及 x = y + z / x % y 都可以算作是一個程式步伐. 於是, 對於同樣的程式, 不同的分析員所計算得到的程式步伐存在差異. 例如某一個分析員對於 for(auto i {0}; i < n; ++i) 這樣的迴圈, 他並不將 i 的初始化計入程式步伐. 因此, 由於程式步伐的定義不嚴謹, 不同的人得到的程式步伐在比較程式性能方面的用處並不大. 但是對於同一個人計算而得的程式步伐相差很大的程式碼, 如某個程式步伐為 $an + b$ ( $a > 0$ ), 另一個程式步伐為 $cn + d$ ( $c \gg d$ ), 那麼此事可以使用程式步伐來判定程式的性能

當實體特徵 $n$ 非常大 ( $n \rightarrow \infty$ ) 的時候, 此時使用程式步伐可以準確地預計程式的運作時間的增長, 以比較兩個程式的性能. 若某個程式的程式步伐為 $c_{1}n^{2} + c_{2}n + c_{3}$ ( $c_{1} > 0$ ), 另一個程式的程式步伐為 $c_{4}n + c_{5}$ ( $c_{4} > 0$ ). 當 $n$ 充分大的時候, 第一個程式的程式步伐會比第二個程式的程式步伐大得多 :

$\lim \limits_{n \to \infty} \frac {c_{1}n^{2}+c_{2}n+c_{3}}{c_{4}n+c_{5}} = \infty$

對程式步伐為 $c_{1}n^{2} + c_{2}n + c_{3}$ ( $c_{1} > 0$ ) 的程式, 若不考慮 $c_{1}$ , $c_{2}$ 和 $c_{3}$ 的具體值, 我們發現, 當 $n$ 增大的時候, 整個表達式的值最終取決於第一項 $c_{1}n^{2}$ 作比率函數 :

$R(n) = \frac {c_{2}n + c_{3}}{c_{1}n^{2}}$

當 $n$ 充分大的時候, 雖然 $R(n)$ 不會等於 $0$ , 但是會無限接近與 $0$ . 即當 $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})}$ , 則有

$T = \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}$ 足夠大, 因此有

$T \doteq \frac {c_{1}n_{1}^{2}}{c_{1}n_{2}^{2}} = (\frac {n_{1}}{n_{2}})^{2}$

若 $n_{1} = 2n$ , $n_{2} = n$ , 則有

$T = 4$

即當實體特徵增大 $2$ 倍的時候, 程式運作時間近似地增大到原來的 $4$ 倍. 類似地, 令 $n_{2}$ 保持不變, $n_{1} = 3n$ , 則 $T = 9$ ; ...

於是我們認識到只要知道程式步伐的最大項為 $n^{2}$ 就可以了, 其係數 $c_{1}$ 無關緊要

假定程式 A 和程式 B 具有相同的功能, 有兩個人 H 和 W 對這兩個程式進行了步伐分析. H 對程式 A 分析後得到程式 A 的程式步伐滿足 $t_{A}^{H}(n) = n^{2} + 3n$ , 對程式 B 分析後得到的結果為 $t_{B}^{H}(n) = 32n$ ; W 對程式 A 分析後得到程式 A 的程式步伐滿足 $t_{A}^{W}(n) = 2n^{2} + 6n$ , 對程式 B 分析後得到的結果為 $t_{B}^{W}(n) = 48n$ . 如果 H 的分析是正確的, 那麼任何人的分析結果想要正確, 其必須滿足

$t_{A}(n) = c_{1}n^{2} + c_{2}n + c_{3} (c_{1} > 0)$ , $t_{B}(n) = c_{4}n + c_{5} (c_{4} > 0)$

的結果. 其中, $c_{1}$ , $c_{2}$ , $c_{3}$ , $c_{4}$ 和 $c_{5}$ 為任意常數

顯然, 針對 H 的分析結果和 W 的分析結果, $t = t_{A}^{H}(n)$ 和 $t = t_{B}^{H}(n)$ 是兩條不同的曲線, $t = t_{A}^{W}(n)$ 和 $t = t_{B}^{W}(n)$ 也是兩條不同的曲線

對於 H 的分析結果, 它們有共同的交點, 即當 $n = 0$ 和 $n = 29$ 時, $t_{A}^{H}(n) = t_{B}^{H}(n)$ , 稱這樣的 $n$ 為程式的均衡點. 當 $n = 0$ 的時候, 無需分析; 當 $0 < n < 29$ 時, 程式 A 更快; 當 $n > 29$ 的時候, 程式 B 更快

再來看看 W 的分析結果

其均衡點為 $n = 0$ 或 $n = 21$ . 當 $n = 0$ 的時候, 無需分析; 當 $0 < n < 21$ 時, 程式 A 更快; 當 $n > 21$ 時, 程式 B 更快

最終, 不論 $t_{A}(n)$ 與 $t_{B}(n)$ 的結果如何, 只要分析正確, 必定有一個非零的均衡點. 此時, 我們會得到當 $n$ 位於均衡點左側的時候, 程式 A 更快; 當 $n$ 位於均衡點右側的時候, 程式 B 更快的結論, 無非是均衡點不同罷了. 為此, 有了漸近分析

漸近分析方法主要確定的是針對複雜函數中的最大項, 即針對當 $n$ 充分大的時候, 最終決定函數值大小的那一項進行分析. 漸近分析是數學分析的一個分支, 它是數學分析中描述函數在極限附近的行為的方法

令 $p(n)$ 和 $q(n)$ 是兩個非負值函數, 若且唯若

$\lim \limits_{n \to \infty} \frac {q(n)}{p(n)} = 0$ 或 $\lim \limits_{n \to \infty} \frac {p(n)}{q(n)} = \infty$

時, 稱 $p(n)$ 漸近地大於 $q(n)$ , $q(n)$ 漸近地小於 $p(n)$ ; 若且唯若

$\lim \limits_{n \to \infty} \frac {p(n)}{q(n)} = 0$ 或 $\lim \limits_{n \to \infty} \frac {q(n)}{p(n)} = \infty$

時, 稱 $q(n)$ 漸近地大於 $p(n)$ , $p(n)$ 漸近地小於 $q(n)$ ; 若且唯若

$\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)$

在接下來的討論中, 函數 $f(n)$ 和 $g(n)$ 等都是作為實體特徵 $n$ 的函數, 表示一個程式的空間複雜度或時間複雜度. 因為程式的空間複雜度或時間複雜度都是非負數, 實體特徵也是非負數, 因此對於任意非負的 $n$ , 我們都假定函數 $f$ 對實體特徵 $n$ 有非負值, 即

$f(n) \geq 0 (n \geq 0)$

我們給定經常在步伐分析中出現的項

項	名稱
$1$	常數
$\log n$	對數
$n$	線型
$n\log n$	$n$ 倍對數
$n^{2}$	平方
$n^{2}\log n$	平方對數
$n^{3}$	立方
$2^{n}$	指數
$n!$	階乘

要注意, 給定的項係數都為 $1$ , 但是在實際分析中, 它們的係數不一定為 $1$ , 可能具有不同的值. 特別指出, 對於對數, 不妨設其底數為 $a$ , 而

$\log_{a} n = \log_{a} b \cdot \log_{b} n (a > 1, b > 1)$

因此, 在步伐分析中, 係數通常會被省略. 因此, 任意底數 $a$ 的對數 ( $a > 1$ ) 是漸近相等的

根據增長的趨勢, 我們容易地得到這些項的大小排列 :

$1 < \log n < n < n\log n < n^{2} < n^{2}\log n < n^{3} < 2^{n} < n!$

其中, " $<$ " 表示漸近小於

漸近記法描述的是大實體特徵的時間複雜度, 我們將用它來分析程式步伐. 除此之外, 它還可以被用於分析空間複雜度和作業計數. 時間複雜度和程式步伐是同義詞. 如果實體特徵只含有一個變數, 如 $n$ , 漸近記法就用程式步伐中漸近最大的一項來描述複雜度

漸近記法 $f(n) = O(g(n))$ 表示函數 $f(n)$ 漸近小於或等於函數 $g(n)$ , 即

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = 0$ 或 $\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} = \lim \limits_{n \to \infty} \frac {g(n)}{f(n)} = 1$

稱這樣的漸近記法為大 O 記法. 在漸近的意義上, 函數 $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$

在漸近分析中, 我們要確定一個最大項以表示複雜度, 而且把這個最大項的係數置為 $1$ . 例如對於函數

$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})$

另外, $f(n) = O(g(n))$ 與 $O(g(n)) = f(n)$ 不同. 實際上, 後者沒有任何意義. 等號在此處表示的 "是" 的含義, 而非表面上相等的含義. 將 $f(n) = O(g(n))$ 翻譯為英文, 讀作 $f(n)$ is big oh of $g(n)$

當某個程式與兩個實體特徵相關的時候, 令 $t(m, n)$ 和 $u(m, n)$ 為兩項, 若且唯若

$\lim \limits_{n \to \infty} \frac {u(m, n)}{t(m, n)} = 0$ 且 $\lim \limits_{m \to \infty} \frac {u(m, n)}{t(m, n)} \neq \infty$

或

$\lim \limits_{n \to \infty} \frac {u(m, n)}{t(m, n)} \neq \infty$ 且 $\lim \limits_{m \to \infty} \frac {u(m, n)}{t(m, n)} = 0$

則稱 $t(m, n)$ 漸近地大於 $u(m, n)$ , $u(m, n)$ 漸近地小於 $t(m, n)$

對於多元的程序步伐函數, 大 O 記法的實用定義如下 :

令 $f(x_{1}, x_{2}, ..., x_{n})$ 是一個程式的程式步伐, 其中任一項若漸近小於剩餘的項, 那麼都可以將其去除
把最終剩下的項的係數更改為 $1$

例如 $f(m, n) = m^{3} + 3m^{2}n + 10mn + 2n^{2}$ , 那麼 $f(m, n) = O(m^{3} + m^{2}n + n^{2})$

除了大 O 記法之外, 還有大 Ω 記法、大 Θ 記法和小 o 記法. 若 $f(n)$ 漸近地大於或等於 $g(n)$ , 則記作 $f(n) = \Theta(g(n))$ ; 若 $f(n)$ 漸近地等於 $g(n)$ , 則記作 $f(n) = \Omega(g(n))$ ; 若 $f(n)$ 漸近地大於 $g(n)$ , 即當 $f(n) = O(g(n))$ 且 $f(n) \neq \Omega(g(n))$ , 則記作 $f(n) = o(g(n))$

大 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)) = \left \{ f(n) : f(n) = O(g(n)) \right \}$

$\Theta(g(n)) = \left \{ f(n) : f(n) = \Theta(g(n)) \right \}$

$\Omega(g(n)) = \left \{ f(n) : f(n) = \Omega(g(n)) \right \}$

基於這種解釋, 於是有類似於

$O(g_{1}(n)) = O(g_{2}(n))$

的表示方法

之前, 我們大致講述了大 O 記法、大 Ω 記法和大 Θ 記法的實用定義. 接著, 我們需要給出它們的精確定義, 否則, 某些定理或著結論我們沒有辦法去證明. 值得注意的是, 小 o 記法的定義可以由大 O 記法、大 Ω 記法和大 Θ 記法的定義推出, 因此之前我們對小 o 記法的定義已經是一個精確定義, 只不過我們需要補充大 O 記法、大 Ω 記法和大 Θ 記法的精確定義才能使的小 o 記法的定義精確

提示 : 如果你了解數學分析中的極限理論, 那麼接下來的內容對你來說非常容易掌握. 但是如果你沒有了解過極限理論, 那麼接下來你的學習可能有些吃力. 目前 Jonny'Blog 已經開通了數學 - 分析學欄目, 閣下可以去搜尋關於極限理論的文章, 此處不再對極限理論進行累贅. 如果你以後要學習極限理論, 而你又能夠理解下面的內容, 那麼這對於你以後學習極限理論非常有幫助

定義 1 (大 O 記法) : 對於函數 $f(n)$ 和 $g(n)$ , 若且唯若存在常數 $c > 0$ 和正整數 $N$ , 使得對於所有的 $n \geq N$ 都有

$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)$ 的函數值

函數 $g$ 作為函數 $f$ 的一個上界, 形式通常比較簡單. 一般只是用一個變數 $n$ 表示且係數為 $1$ 的單項

有了大 O 記法的嚴格定義, 我們可以證明某些斷言 :

斷言 : $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$ 的時候, 有

$f(n) \leq c \cdot 2^{n}$
即

$3n^{2}2_{n} + 4n2^{n} + 8n^{2} \leq c \cdot 2^{n}$
不等式兩側同乘 $\frac {1}{2^{n}}$ , 可得

$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})$
$證畢$

事實上, $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)$ 應該儘量小

根據大 O 記法的嚴格定義, 我們可以得到兩個定理

大 O 記法定理 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$ , 於是我們注意到不等式

$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}|$
根據大 O 記法的定義, 因此有 $f(n) = O(n^{m})$
$證畢$

大 O 記法定理 2 (大 O 記法比率定理) : 假設函數 $f = f(n)$ , $g = g(n)$ 滿足極限

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)}$

存在, 若且唯若存在常數 $c$ 使得

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$

時, 有 $f(n) = O(g(n))$

$證明$ :

要證明這個定理成立, 其實就是要證明使得 $f(n) = O(g(n))$ 成立的充分必要條件是存在常數 $c$ , 使得

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$
若有 $f(n) = O(g(n))$ 成立, 則根據大 O 記法的定義, 存在常數 $c > 0$ 和正整數 $N$ , 當 $n \geq N$ 時, 有

$f(n) \leq cg(n)$
即 $\frac {f(n)}{g(n)} \leq c$ , 亦即 $\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$
$充分性證畢$
若 $\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$ 成立, 根據數列極限的定義, 存在正整數 $N$ , 當 $n \geq N$ 時, 有

$|\frac {f(n)}{g(n)} - c_{0}| \leq \varepsilon$
其中, $\lim \limits_{n \to \infty} \frac{f(n)}{g(n)} = c_{0} \leq c$ , $\varepsilon > 0$ . 則有

$-\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)$ 成立

$必要性證畢$
綜上所述, $f(n) = O(g(n))$ 成立的充分必要條件是存在常數 $c$ , 使得

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$
$證畢$

使用這個定理, 我們可以很快地得到 $g(n)$ . 例如有函數 $f(n) = c_{1}n^{2} + c_{2}n + c_{3}$ , 其中 $c_{1} > 0$ , 由於

$\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 記法比率定理可知

$f(n) = O(n^{2})$

定義 2 (大 Ω 記法) : 對於函數 $f(n)$ 和 $g(n)$ , 若且唯若存在常數 $c > 0$ 和正整數 $N$ , 使得對於所有的 $n \geq N$ 都有

$f(n) \geq cg(n)$

成立時, 記 $f(n) = \Omega(g(n))$

大 Ω 記法也簡稱 Ω 記法

Ω 記法定理 1 : 如果 $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)$ , 可以觀察到

$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}$
根據 Ω 記法的定義, 有

$f(n) = \Omega(n^{m})$
$證畢$

Ω 記法定理 2 (O 記法比率定理) : 假設函數 $f = f(n)$ , $g = g(n)$ 滿足極限

$\lim \limits_{n \to \infty} \frac {f(n)}{g(n)}$

存在, 若且唯若存在常數 $c$ 使得

$\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$ 都有

$c_{1}g(n) \geq f(n) \geq c_{2}g(n)$

成立時, 記 $f(n) = \Theta(g(n))$

大 Θ 記法也簡稱 Θ 記法

Θ 記法定理 1 : 如果 $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})$

$證明$ :

由大 O 記法定理 1 和大 Ω 記法定理 1 的證明可知 :

$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}|$ , 根據大 Θ 記法的定義, 有 $f(n) = \Theta(n^{m})$
$證畢$

Θ 記法定理 2 (Θ 記法比率定理) : 假設函數 $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$ 使得

$\lim \limits_{n \to \infty} \frac {g(n)}{f(n)} \leq c$ 且 $\lim \limits_{n \to \infty} \frac {f(n)}{g(n)} \leq c$

時, 有 $f(n) = \Theta(g(n))$

結合大 O 記法比率定理和 Ω 記法比率定理就可以得證 Θ 記法比率定理, 因此這個定理我們不證, 閣下可以自己嘗試證明

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

定義 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})$ . 在數學分析中, 有一個定義和小 o 記法非常相似, 即高階無窮小

我們曾經說過, 大 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}$

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

我們已經將大 O 記法的定義推廣到了多元函數, 對於 Ω 記法、Θ 記法和小 o 記法同樣可以推廣到多元函數

對於某些函數 $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$ 中的任意一個

對於複雜度的應用, 前面已經說過了其中一種用法, 即在函式的功能相同的情況下, 我們通常使用複雜度較小的函式. 對於複雜度較小的這個描述, 用 $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 速度更快

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

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