分類目錄：《算法設計與分析》總目錄
相關文章：
算法學基礎（一）：算法學概述
算法學基礎（二）：分析算法
算法學基礎（三）：漸進記號

---

第《算法學基礎（二）：分析算法》中定義了算法運行時間的增長量級簡單地刻畫了算法效率，并且還允許我們比較可選算法的相對性能。一旦輸入規模$n$變得足夠大，最壞情況運行時間為$\Theta (n\lg n)$的歸并排序將戰勝最壞情況運行時間為$\Theta (n^2)$的插入排序。正如我們在分析插入排序時所做的工作，雖然有時我們能夠確定一個算法的精確運行時間，但是通常并不值得花力氣來計算它以獲得多余的精度。對于足夠大的輸入，精確運行時間中的倍增常量和低階項被輸入規模本身的影響所支配。

當輸入規模足夠大，使得只有運行時間的增長量級有關時，我們要研究算法的漸近效率。也就是說，我們關心當輸入規模無限增加時，在極限中，算法的運行時間如何隨著輸入規模的變大而增加。通常，漸近地更有效的某個算法對除很小的輸入外的所有情況將是最好的選擇。

本文以及后文將給出幾種標準方法來簡化算法的漸近分析。首先定義幾類“漸近記號”，其中，我們已經見過的一個例子是$\Theta$記號。然后，我們給出算法分析領域經常使用的幾種記號約定。

漸近記號、函數與運行時間

正如我們寫插入排序的最壞情況運行時間為$\Theta (n^2)$時那樣，我們將主要使用漸近記號來描述算法的運行時間。然而，漸近記號實際上應用于函數?；仡櫼幌?#xff0c;我們曾把插入排序的最壞情況運行時間刻畫為$a{n}^2+bn+c$，其中$a$、$b$和$c$是常量。通過把插入排序的運行時間寫成$\Theta (n^2)$，我們除去了該函數的某些細節。因為漸近記號適用于函數，我們所寫成的$\Theta (n^2)$就是函數$a{n}^2+bn+c$，所以上述情況碰巧刻畫了插入排序的最壞情況運行時間。

算法分析領域常常對其使用漸近記號的函數通?？坍嬎惴ǖ倪\行時間。但是漸近記號也可以適用于刻畫算法的某個其他方面（例如，算法使用的空間數量）的函數，甚至可以適用于和算法沒有任何關系的函數。

即使我們使用漸近記號來刻畫算法的運行時間，我們也需要了解意指哪個運行時間。有時我們對最壞情況運行時間感興趣。然而，我們常常希望刻畫任何輸入的運行時間。換句話說，我們常常希望做出一種綜合性地覆蓋所有輸入而不僅僅是最壞情況的陳述。我們將看到完全適合刻畫任何輸入的運行時間的漸近記號。

漸近記號

$\Theta$記號

在《算法學基礎（二）：分析算法》中，我們發現插入排序的最壞情況運行時間為$T(n)=\Theta (n^2)$。這意味著：對一個給定的函數$g(n)$，用$\Theta (g(n))$來表示以下函數的集合：
$$\Theta (g(n))=\{f(n)：?c_1>0,c_2>0,n_0>0，?n\ge n_0，0\le c_{1}g(n)\le f(n)\le c_{2}g(n)\}$$

若存在正常量$c_1$和$c_2$，使得對于足夠大的$n$，函數$f(n)$能“夾入”$c_{1}g(n)$與$c_{2}g(n)$之間，則$f(n)$）屬于集合$\Theta (g(n))$。因為$\Theta (g(n))$是一個集合，所以可以記$f(n)\in \Theta (g(n))$，以指出$f(n)$是$\Theta (g(n))$的成員。作為替代，我們通常記$f(n)=\Theta (g(n))$以表達相同的概念。因為我們按這種方式活用了等式，所以你可能感到困惑，但是在后面的文章中我們將看到這樣做有其好處。

下圖(a)給出了函數$f(n)$與$g(n)$的一幅直觀畫面，其中$f(n)=\Theta (g(n))$。對在$n_0$及其右邊$n$的所有值，$f(n)$的值位于或高于$c_{1}g(n)$且位于或低于$c_{2}g(n)$。換句話說，對所有$n\le n_0$，函數$f(n)$在一個常量因子內等于$g(n)$。我們稱$g(n)$是$f(n)$的一個漸近緊確界。

$\Theta (g(n))$的定義要求每個成員$f(n)\in \Theta (g(n))$均漸近非負，即當$n$足夠大時，$f(n)$非負。其中，漸近正函數就是對所有足夠大的$n$均為正的函數。因此，函數$g(n)$本身必為漸近非負，否則集合$\Theta (g(n))$為空。所以我們假設用在$\Theta$記號中的每個函數均漸近非負。這個假設對本章定義的其他漸近記號也成立。

在《算法學基礎（二）：分析算法》中我們介紹了$\Theta$記號的一種非形式化的概念，相當于扔掉低階項并忽略最高階項前的系數。直覺上，一個漸近正函數的低階項在確定漸近確界時可以被忽略，因為對大的$n$，它們是無足輕重的。當$n$較大時，即使最高階項的一個很小的部分都足以支配所有低階項。因此，將$c_1$置為稍小于最高階項系數的值并將$c_2$置為稍大于最高階項系數的值能使$\Theta$記號定義中的不等式得到滿足。最高階項系數同樣可以被忽略，因為它僅僅根據一個等于該系數的常量因子來改變$c_1$和$c_2$。

作為一個例子，考慮任意二次函數$f(n)=a{n}^2+bn+c$，其中$a$、$b$和$c$均為常量且$a>0$。扔掉低階項并忽略常量后得$f(n)=\Theta (n^2)$。為了形式化地證明相同的結論，我們取常量$c_1=\frac{a}{4}$，$c_2=\frac{7a}{4}$且$n_0=2\max (\frac{|b|}{a},\sqrt{\frac{|c|}{a}})$。可以證明對所有$n\ge n_0$，有$0\le c_1{n}^2\le a{n}^2+bn+c\le c_2{n}^2$。一般來說，對任意多項式$p(n)={\sum }_{i=0}^d{a}_i{n}^i$，其中$a_i$為常量且$a_d>0$，我們有$p(n)=\Theta (n^d)$。

因為任意常量是一個$0$階多項式，所以可以把任意常量函數表示成$\Theta (n^0)$或者$\Theta (1)$。然而，后一種記號是一種輕微的活用，因為該表達式并未指出什么變量趨于無窮e。我們將經常使用記號$\Theta (1)$來意指一個常量或者關于某個變量的一個常量函數。

$O$記號

記號漸近地給出一個函數的上界和下界。當只有一個漸近上界時，使用$O$記號。對于給定的函數$g(n)$，用$O(g(n))$來表示以下函數的集合：

$$O(g(n))=\{f(n)：?c>0,n_0>0，?n\ge n_0，0\le f(n)\le cg(n)\}$$

我們使用$O$記號來給出函數的一個在常量因子內的上界。上圖(b)展示了$O$記號背后的直覺知識。對在$n_0$及其右邊的所有值$n$，函數$f(n)$的值總小于或等于$cg(n)$。

我們記$f(n)=O(g(n))$以指出函數$f(n)$是集合$O(g(n))$的成員。注意，$f(n)=\Theta (g(n))$蘊涵著$f(n)=O(g(n))$，因為$\Theta$記號是一個比$O$記號更強的概念。按集合論中的寫法，我們有$\Theta (g(n))?O(g(n))$。因此，關于任意二次函數$f(n)=a{n}^2+bn+c$，其中$a>0$，在$\Theta (n^2)$中的證明也證明了任意這樣的二次函數在$O(n^2)$中。也許更令人驚奇的是當$a>0$時，任意線性函數$an+b$也在$O(n^2)$中，我們可以很容易證明這個結論。

但是在文獻中，有時我們發現$O$記號非形式化地描述漸近確界，即已經使用$\Theta$記號定義的東西。使用$O$記號，我們常常可以僅僅通過檢查算法的總體結構來描述算法的運行時間。例如，《排序算法（一）：插入排序》中插入排序算法的雙重嵌套循環結構對最壞情況運行時間立即產生一個$O(n^2)$的上界：內層循環每次迭代的代價以$O(1)$為上界，下標$i$和$i$均最多為$n$，對于$n^2$個$i$和$j$值對的每一對，內循環最多執行一次。

既然$O$記號描述上界，那么當用它來限制算法的最壞情況運行時間時，關于算法在每個輸入上的運行時間，我們也有一個界，這就是前面討論的綜合性陳述。因此，對插入排序的最壞情況運行時間的界$O(n^2)$也適用于該算法對每個輸入的運行時間。然而，對插入排序的最壞情況運行時間的界$\Theta (n^2)$并未暗示插入排序對每個輸入的運行時間的界也是$\Theta (n^2)$）。例如，我們在當輸入已排好序時，插入排序的運行時間為$\Theta (n)$。從技術上看，稱插入排序的運行時間為$O(n^2)$有點不合適，因為對給定的$n$，實際的運行時間是變化的，依賴于規模為$n$的特定輸入。當我們說“運行時間為$O(n^2)$”時，意指存在一個$O(n^2)$的函數$f(n)$，使得對$n$的任意值，不管選擇什么特定的規模為$n$的輸入，其運行時間的上界都是$f(n)$。這也就是說最壞情況運行時間為$O(n^2)$。

$\Omega$記號

正如$O$記號提供了一個函數的漸近上界，$\Omega$記號提供了漸近下界。對于給定的函數$g(n)$，用$\Omega (g(n))$來表示以下函數的集合：

$$\Omega (g(n))=\{f(n)：?c>0,n_0>0，?n\ge n_0，0\le cg(n)\le f(n)\}$$

上圖?給出了$\Omega$記號的直觀解釋。對在$n_0$及其右邊的所有值$n$，$f(n)$的值總大于或等于$cg(n)$。

根據目前所看到的這些漸近記號的定義，容易證明以下重要定理：對任意兩個函數$f(n)$和$g(n)$，我們有$f(n)=\Theta (g(n))$，當且僅當$f(n)=O(g(n))$且$f(n)=\Omega (g(n))$。

當稱一個算法的運行時間為$\Omega (g(n))$時，我們意指對每個$n$值，不管選擇什么特定的規模為$n$的輸入，只要$n$足夠大，對那個輸入的運行時間至少是$g(n)$的常量倍。等價地，我們再對一個算法的最好情況運行時間給出一個下界。例如，插入排序的最好情況運行時間為$\Omega (n)$，這蘊涵著插入排序的運行時間為$\Omega (n)$。

所以插入排序的運行時間介于$\Omega (n)$和$O(n)$，因為它落入$n$的線性函數與$n$的二次函數之間的任何地方。而且，這兩個界是盡可能漸近地緊確的：例如，插入排序的運行時間不是$\Omega (n)$，因為存在一個輸入，對該輸入，插入排序在$\Theta (n)$時間內運行。然而，這與稱插入排序的最壞情況運行時間為$\Omega (n^2)$并不矛盾，因為存在一個輸入，使得該算法需要$\Omega (n^2)$的時間。

$o$記號

由$O$記號提供的漸近上界可能是也可能不是漸近緊確的。界$2n^2=O(n^2)$是漸近緊確的，但是界$2n=O(n^2)$卻不是。我們使用$o$記號來表示一個非漸近緊確的上界。形式化地定義$o(g(n))$為以下集合：

$$o(g(n))=\{f(n)：?c>0,?n_0>0，?n\ge n_0，0\le f(n)\le cg(n)\}$$

例如，$2n=o(n^2)$，但是$2n^2=o(n^2)$。$O$記號與$o$記號的定義類似。主要的區別是在$f(n)=O(g(n))$中，界$0\le f(n)\le cg(n)$對某個常量$c>0$成立，但在$f(n)=o(g(n))$，界$0\le f(n)\le cg(n)$對所有常量$c>0$成立。直觀上，在$o$記號中，當$n$趨于無窮時，函數$f(n)$相對于$g(n)$來說變得微不足道了，即：
$$\underset{n\to +\infty }{\lim }\frac{f(n)}{g(n)}=0$$

$\omega$記號

$\omega$記號與$\Omega$記號的關系類似于$o$記號與$O$記號的關系。我們使用$\omega$記號來表示一個非漸近緊確的下界。它形式化定義是：

$$\omega (g(n))=\{f(n)：?c>0,?n_0>0，?n\ge n_0，0\le cg(n)\le f(n)\}$$

然而，我們還可以用另一種方式定義$\omega$記號：
$$f(n)\in \omega (g(n))?g(n)\in o(f(n))$$

同樣，關系$f(n)=\omega (g(n))$也蘊含著：
$$\underset{n\to +\infty }{\lim }\frac{f(n)}{g(n)}=\infty$$

也就是說，如果這個極限存在，那么當n趨于無窮時，$f(n)$相對于$g(n)$來說變得任意大了。

等式和不等式中的漸近記號

我們已經看到漸近記號可以如何用于數學公式中。例如，在介紹$O$記號記$n=O(n^2)$。我們還可能寫過$2n^2+3n+1=2n^2+\Theta (n)$。當漸近記號獨立于等式或不等式的右邊時，如在$n=O(n^2)$中，我們已經定義等號意指集合的成員關系:$n\in O(n^2)$。然而，一般來說，當漸近記號出現在某個公式中時，我們將其解釋為代表某個我們不關注名稱的匿名函數。例如，公式$2n^2+3n+1=2n^2+\Theta (n)$意指$2n^2+3n+1=2n^2+f(n)$，其中$f(n)$是集合$\Theta (n)$中的某個函數。在這個例子中，假設$f(n)=3n+1$，該函數確實在$\Theta (n)$中。

按這種方式使用漸近記號可以幫助消除一個等式中無關緊要的細節與混亂。例如，在《分治策略（一）：基礎知識》中，我們把歸并排序的最壞情況運行時間表示為遞歸式$2T(\frac{n}{2})+\Theta (n)$。如果只對$T(n)$的漸近行為感興趣，那么沒有必要準確說明所有低階項，它們都被理解為包含在由項$\Theta (n)$表示的匿名函數中。

一個表達式中匿名函數的數目可以理解為等于漸近記號出現的次數。例如，在表達式$\sum O(i)$中，只有一個匿名函數（一個$i$的函數）。因此，這個表達式不同于$O(1)+O(2)+?+O(n)$，實際上后者沒有一個清晰的解釋。

在某些例子中，漸近記號出現在等式的左邊，例如：$2n^2+\Theta (n)=\Theta (n^2)$。我們使用以下規則來解釋這種等式：無論怎樣選擇等號左邊的匿名函數，總有一種辦法來選擇等號右邊的匿名函數使等式成立。因此，我們的例子意指對任意函數$f(n)\in \Theta (n)$，存在某個函數$g(n)\in \Theta (n^2)$，使得對所有的$n$，有$2n^2+f(n)=g(n)$。換句話說，等式右邊比左邊提供的細節更粗糙。

漸近記號的比較

實數的許多關系性質也適用于漸近比較。下面假定$f(n)$和$g(n)$漸近為正。

傳遞性

$$f(n)=\Theta (g(n))\text{and}g(n)=\Theta (h(n))?f(n)=\Theta (h(n))$$
$$f(n)=O(g(n))\text{and}g(n)=O(h(n))?f(n)=O(h(n))$$
$$f(n)=\Omega (g(n))\text{and}g(n)=\Omega (h(n))?f(n)=\Omega (h(n))$$
$$f(n)=o(g(n))\text{and}g(n)=o(h(n))?f(n)=o(h(n))$$
$$f(n)=\omega (g(n))\text{and}g(n)=\omega (h(n))?f(n)=\omega (h(n))$$

自反性

$$f(n)=\Theta (f(n))$$
$$f(n)=O(f(n))$$
$$f(n)=\Omega (f(n))$$

對稱性

$$f(n)=\Theta (g(n))?g(n)=\Theta (f(n))$$
$$f(n)=O(g(n))?g(n)=\Omega (f(n))$$
$$f(n)=o(g(n))?g(n)=\omega (f(n))$$

三分性

對任意兩個實數$a$和$b$，下列三種情況恰有一種必須成立：$a<b$，$a=b$，$a>b$。雖然任意兩個實數都可以進行比較，但不是所有函數都可漸近比較。也就是說，對兩個函數$f(n)$和$g(n)$，也許$f(n)=O(g(n))$和$f(n)=\Omega (g(n))$都不成立。

總結

以上是生活随笔為你收集整理的算法设计与分析——算法学基础（三）：渐进记号的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。