第2章 算法分析基礎(chǔ)

一旦確信一個(gè)算法是正確的，下一個(gè)重要的步驟就是分析算法。算法分析是指對(duì)算法利用時(shí)間和空間這兩種資源的效率進(jìn)行研究。本章討論衡量算法效率的時(shí)間復(fù)雜度和空間復(fù)雜度，算法的最好、平均和最壞情況時(shí)間復(fù)雜度，討論用于算法分析的漸近表示法，介紹如何使用遞推關(guān)系來(lái)分析遞歸算法的方法及分?jǐn)偡治黾夹g(shù)。

2.1 算法復(fù)雜度

同一個(gè)問(wèn)題可以編寫(xiě)多個(gè)算法來(lái)求解，這些算法所消耗的計(jì)算機(jī)資源（計(jì)算時(shí)間和存儲(chǔ)空間）多少不同。算法的復(fù)雜度是指運(yùn)行一個(gè)算法所需的時(shí)間和空間資源的量。

2.1.1 什么是好的算法

人們總是希望算法具有許多良好的特性。一個(gè)好的算法應(yīng)具有以下4個(gè)重要特性。

（1）正確性（correctness）：毫無(wú)疑問(wèn)，算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿(mǎn)足預(yù)先規(guī)定的功能和性能要求。

（2）簡(jiǎn)明性（simplicity）：算法應(yīng)思路清晰、層次分明、容易理解、利于編碼和調(diào)試。

（3）效率（efficiency）：算法應(yīng)有效使用存儲(chǔ)空間，并具有高的時(shí)間效率。

（4）最優(yōu)性（optimality）：算法的執(zhí)行時(shí)間已達(dá)到求解該類(lèi)問(wèn)題所需時(shí)間的下界。

算法的正確性是指在合法的輸入下，算法應(yīng)實(shí)現(xiàn)預(yù)先規(guī)定的功能和計(jì)算精度要求。與算法正確性直接相關(guān)的是程序的正確性。對(duì)于大型程序，人們無(wú)法奢望它“完全正確”，而且這一點(diǎn)也往往無(wú)法證實(shí)，這就引出對(duì)程序健壯性（robustness）的要求。程序健壯性是指當(dāng)輸入不合法數(shù)據(jù)時(shí)，程序應(yīng)能做適當(dāng)處理而不至于引起嚴(yán)重后果。一個(gè)程序也許不能做到完全正確，但可以要求它是健壯的。其含義是：當(dāng)程序萬(wàn)一遇到意外時(shí)，能按某種預(yù)定方式做出適當(dāng)處理。正確性和健壯性是相互補(bǔ)充的。正確的程序并不一定是健壯的，而健壯的程序并不一定絕對(duì)正確。一個(gè)可靠的程序應(yīng)當(dāng)能在正常情況下正確地工作，而在異常情況下，亦能做出適當(dāng)處理，這就是程序的可靠性（reliability）。

注意，本書(shū)假定算法的輸入都是合法輸入，而不進(jìn)行輸入檢測(cè)，但在算法的實(shí)際應(yīng)用中，應(yīng)當(dāng)對(duì)輸入數(shù)據(jù)實(shí)施必要的檢測(cè)來(lái)保證程序的健壯性。

算法的簡(jiǎn)明性要求算法的邏輯清晰，簡(jiǎn)單明了，并且是結(jié)構(gòu)化的，從而使算法易于閱讀和理解，并易于編碼和調(diào)試。算法的簡(jiǎn)明性沒(méi)有嚴(yán)格定義的尺度可以度量，在很大程度上取決于審視者的眼光。但簡(jiǎn)明性并不是可有可無(wú)的特性，它是算法設(shè)計(jì)者需努力爭(zhēng)取的一個(gè)重要特性，因?yàn)楹?jiǎn)單的算法往往更容易理解和實(shí)現(xiàn)，相應(yīng)的程序也會(huì)因此而減少錯(cuò)誤（bug）。此外，一個(gè)簡(jiǎn)單明了的算法就像一篇優(yōu)美的說(shuō)明文，令閱讀者賞心悅目。但遺憾的是，簡(jiǎn)單的算法并不一定是高效的。

算法的效率是指執(zhí)行一個(gè)算法所需的計(jì)算時(shí)間和存儲(chǔ)空間。當(dāng)程序規(guī)模較大時(shí)，算法的效率問(wèn)題是算法設(shè)計(jì)必須面對(duì)的一個(gè)關(guān)鍵問(wèn)題。必須重視算法的效率分析。然而為了換取一定的效率，犧牲算法的可讀性，在現(xiàn)代程序設(shè)計(jì)中并不是明智之舉。因此，算法設(shè)計(jì)者往往需要在算法的簡(jiǎn)明性和效率之間做出謹(jǐn)慎的選擇。折中和結(jié)論（tradeoffs and consequences）是計(jì)算機(jī)學(xué)科的重要概念之一。

算法的最優(yōu)性與所求解的問(wèn)題自身的復(fù)雜程度有關(guān)。例如，對(duì)于在n個(gè)元素的集合中尋找一個(gè)最大元素的問(wèn)題，分析表明，任何通過(guò)元素之間比較的方式來(lái)求解此問(wèn)題的正確算法，至少需要進(jìn)行n-1次元素間的比較運(yùn)算。如果某人編寫(xiě)一個(gè)算法，聲稱(chēng)他的算法對(duì)任意一個(gè)有n個(gè)元素的集合，僅需執(zhí)行n-2次元素比較便可求得集合中的最大元素，那么，可以肯定，該算法不可能是正確的。如果一個(gè)實(shí)際的正確算法，在最壞情況下的確只需n-1次元素比較便可求得最大元素，那么它可稱(chēng)為最優(yōu)的。因?yàn)?span id="ik4lhdd" class="italic">n-1次元素比較是求最大元問(wèn)題所需時(shí)間的下界。本書(shū)將討論排序和查找問(wèn)題的時(shí)間下界。然而遺憾的是，許多看似簡(jiǎn)單的問(wèn)題，至今仍無(wú)法知曉求解該問(wèn)題所需的時(shí)間下界是多少，如：矩陣乘法。

2.1.2 影響程序運(yùn)行時(shí)間的因素

一個(gè)程序的運(yùn)行時(shí)間是程序運(yùn)行從開(kāi)始到結(jié)束所需的時(shí)間。影響程序運(yùn)行時(shí)間的因素主要有：

（1）程序所依賴(lài)的算法；

（2）問(wèn)題規(guī)模和輸入數(shù)據(jù)；

（3）計(jì)算機(jī)系統(tǒng)性能。

首先，很容易想到，對(duì)于同一程序和相同的輸入數(shù)據(jù)，如果在不同的計(jì)算機(jī)上運(yùn)行該程序，所需的運(yùn)行時(shí)間幾乎可以肯定是不同的。這是因?yàn)橛?jì)算機(jī)的硬件性能可能不同，特別是處理器（CPU）速度可能相差很多。程序設(shè)計(jì)語(yǔ)言及其編譯器不同，生成的目標(biāo)代碼的效率也會(huì)各異。操作系統(tǒng)也是影響計(jì)算機(jī)系統(tǒng)性能的因素之一。這就是說(shuō)，算法運(yùn)行所需的時(shí)間依賴(lài)于計(jì)算機(jī)軟、硬件系統(tǒng)。

如果排除計(jì)算機(jī)的因素，假定在完全相同的計(jì)算機(jī)環(huán)境下運(yùn)行程序，情況又如何呢？

很顯然，求解同一個(gè)問(wèn)題的不同算法，其程序運(yùn)行時(shí)間一般不同。一個(gè)好的算法運(yùn)行時(shí)間較少。算法自身的好壞對(duì)運(yùn)行時(shí)間的影響是根本的和起決定作用的。例如，使用不同的排序算法對(duì)同一組元素進(jìn)行排序，程序運(yùn)行的時(shí)間通常是不相同的。

程序的一次運(yùn)行是針對(duì)所求解問(wèn)題的某一特定實(shí)例（instance）而言的。例如，執(zhí)行一個(gè)排序算法，需要輸入一組待排序的元素，對(duì)該組特定元素的排序是排序問(wèn)題的一個(gè)實(shí)例。待排序的元素個(gè)數(shù)是一個(gè)排序問(wèn)題實(shí)例的重要特征（characteristics），它直接影響排序算法的執(zhí)行時(shí)間和所需的存儲(chǔ)空間。因此，分析算法性能需要考慮的一個(gè)基本特征是問(wèn)題實(shí)例的規(guī)模（size）。使用同一個(gè)排序算法對(duì)100個(gè)整數(shù)進(jìn)行排序與對(duì)10000個(gè)整數(shù)進(jìn)行排序所需的時(shí)間很顯然是不同的。

問(wèn)題的規(guī)模一般是指輸入數(shù)據(jù)的量，必要時(shí)也考慮輸出數(shù)據(jù)的量。對(duì)于兩個(gè)m×n矩陣加法問(wèn)題的規(guī)模，通常考慮輸入矩陣的元素個(gè)數(shù)，它正比于m×n；但對(duì)于一個(gè)由計(jì)算機(jī)隨機(jī)生成并打印一個(gè)矩陣的算法來(lái)說(shuō)，其運(yùn)行時(shí)間與所生成的矩陣元素的個(gè)數(shù)有關(guān)，即與輸出數(shù)據(jù)的量有關(guān)。還有一種情況，例如，現(xiàn)代密碼算法需要進(jìn)行超過(guò)200位長(zhǎng)度的十進(jìn)制數(shù)運(yùn)算，顯然算法的運(yùn)行時(shí)間與輸入（輸出）數(shù)據(jù)的數(shù)值大小有關(guān)，此時(shí)，問(wèn)題的規(guī)模必須考慮數(shù)據(jù)的數(shù)值大小。設(shè)x是這樣的數(shù)，可以考慮以x的二進(jìn)制形式表示的比特?cái)?shù)b=logx+1（本書(shū)使用logn表示以2為底的對(duì)數(shù)log2n。）來(lái)度量x的數(shù)據(jù)量。數(shù)據(jù)的總輸入量可以用各個(gè)數(shù)的長(zhǎng)度之和來(lái)計(jì)算。

如果在同一個(gè)計(jì)算機(jī)系統(tǒng)上運(yùn)行同一個(gè)程序，問(wèn)題實(shí)例的規(guī)模也相同，則運(yùn)行時(shí)間是否就一定相同呢？一個(gè)熟悉的例子是使用冒泡排序算法分別對(duì)100個(gè)已從小到大有序的整數(shù)排序，以及對(duì)隨機(jī)選擇的100個(gè)整數(shù)進(jìn)行排序，它們所需的排序時(shí)間通常是不同的。這就是說(shuō)，問(wèn)題的規(guī)模相同，輸入數(shù)據(jù)的狀態(tài)（如排列次序）不同，所需的時(shí)間開(kāi)銷(xiāo)也會(huì)不同。

2.1.3 算法的時(shí)間復(fù)雜度

1.抽象機(jī)模型

從上面討論可以看到，一個(gè)程序運(yùn)行的時(shí)間與計(jì)算機(jī)系統(tǒng)的性能有關(guān)。為了消除計(jì)算機(jī)因素對(duì)算法分析的影響，現(xiàn)假定算法（程序）運(yùn)行在一臺(tái)抽象的計(jì)算機(jī)模型上，它不依賴(lài)于實(shí)際的計(jì)算機(jī)軟、硬件系統(tǒng)。設(shè)抽象機(jī)提供由m個(gè)基本運(yùn)算（也可稱(chēng)為語(yǔ)句）組成的運(yùn)算集O={O1, O2, …, Om}，每個(gè)運(yùn)算都是基本的，它們的執(zhí)行時(shí)間是有限常量。同時(shí)設(shè)執(zhí)行第i個(gè)運(yùn)算Oi所需的時(shí)間是ai，1≤i≤m。因此，一個(gè)算法對(duì)于給定輸入在抽象機(jī)上的一次執(zhí)行過(guò)程，表現(xiàn)為執(zhí)行一個(gè)基本運(yùn)算的序列。

2.時(shí)間復(fù)雜度

一個(gè)算法的時(shí)間復(fù)雜度（time complexity）是指算法運(yùn)行所需的時(shí)間。

設(shè)有一個(gè)在抽象機(jī)上運(yùn)行的算法A，I是某次運(yùn)行時(shí)的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運(yùn)行時(shí)間T是n和I的函數(shù)，記做T(n, I)。又設(shè)在該次運(yùn)算中抽象機(jī)的第i個(gè)基本運(yùn)算Oi的執(zhí)行次數(shù)為βi，1≤i≤m，βi也是n和I的函數(shù)，記做βi(n, I)。那么，算法A在輸入為I時(shí)的運(yùn)行時(shí)間是：

這就是算法的時(shí)間復(fù)雜度。式中，輸入數(shù)據(jù)I代表問(wèn)題的一個(gè)實(shí)例，n是問(wèn)題的規(guī)模。

3.最好、最壞和平均時(shí)間復(fù)雜度

前面提到，對(duì)于許多算法，即使問(wèn)題的規(guī)模相同，如果輸入數(shù)據(jù)I不同，算法所需的時(shí)間開(kāi)銷(xiāo)也會(huì)不同。

例如，在一個(gè)有n個(gè)元素的數(shù)組中查找一個(gè)指定元素，某個(gè)搜索算法從第一個(gè)元素開(kāi)始，一次檢查一個(gè)數(shù)組元素。如果待查元素恰好是第一個(gè)元素，則所需的查找時(shí)間最短，這就是算法的最好情況（best case）。如果待查元素是最后一個(gè)元素，所需的查找時(shí)間最長(zhǎng)，則是算法執(zhí)行時(shí)間的最壞情況（worst case）。如果需要多次在數(shù)組中查找元素，并且假定以某種概率查找每個(gè)元素，最典型的是以相等概率查找每個(gè)元素，在這種情況下，就會(huì)發(fā)現(xiàn)算法需平均檢索約n/2個(gè)元素，這是算法時(shí)間代價(jià)的平均情況（average case）。

本書(shū)使用B(n)、W(n)和A(n)分別表示算法的最好、最壞和平均情況時(shí)間復(fù)雜度。設(shè)I∈Dn，Dn是規(guī)模為n的所有合法輸入的集合，并設(shè)I'和I*分別是Dn中使得算法運(yùn)行有最好和最壞情況的實(shí)例（輸入數(shù)據(jù)），P(I)是實(shí)例I（I∈Dn）在具體應(yīng)用中被使用的概率，則算法的上述三種情況時(shí)間復(fù)雜度可分別定義如下：

這三種時(shí)間復(fù)雜度從不同角度反映算法的效率，各有用途，也各有局限性。其中，比較容易分析和計(jì)算，并且也最有實(shí)際價(jià)值的是最壞情況時(shí)間復(fù)雜度。在本書(shū)中，算法分析的重點(diǎn)也主要集中在對(duì)最壞情況時(shí)間復(fù)雜度的分析和計(jì)算上。

還有一種類(lèi)型的時(shí)間效率稱(chēng)為分?jǐn)傂省Ｋ⒉会槍?duì)算法的單次運(yùn)行，而是計(jì)算算法在同一數(shù)據(jù)結(jié)構(gòu)上執(zhí)行一系列運(yùn)算的平均時(shí)間。也許單次運(yùn)算的時(shí)間代價(jià)較高，但n次運(yùn)算的總運(yùn)行時(shí)間除以n的平均時(shí)間效率并不差，這就是分?jǐn)傂省ｊP(guān)于分?jǐn)傂蕦⒃谏院笞錾钊胗懻摗?/p>

2.1.4 使用程序步分析算法

從上面討論可知，程序運(yùn)行時(shí)間不僅與算法的優(yōu)劣和輸入數(shù)據(jù)直接相關(guān)，還與運(yùn)行程序的計(jì)算機(jī)軟、硬件環(huán)境有關(guān)。為了分析算法的效率，總希望略去計(jì)算機(jī)系統(tǒng)因素，對(duì)算法自身的特性進(jìn)行事前分析（priori analysis），即在算法實(shí)際運(yùn)行前分析算法的效率。這種分析結(jié)果顯然不可能是程序運(yùn)行時(shí)間的具體值，而是運(yùn)行時(shí)間的一種事前估計(jì)。算法的事后測(cè)試（posteriori testing）是通過(guò)運(yùn)行程序，測(cè)試一個(gè)程序在所選擇的輸入數(shù)據(jù)下實(shí)際運(yùn)行所需要的時(shí)間。

前面關(guān)于算法時(shí)間復(fù)雜度的概念是在抽象機(jī)模型上定義的。對(duì)于用程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的算法，應(yīng)如何分析其時(shí)間復(fù)雜度呢？可以設(shè)想，如果我們將程序設(shè)計(jì)語(yǔ)言中的循環(huán)語(yǔ)句的執(zhí)行過(guò)程，視為其循環(huán)體（其中不嵌套循環(huán)）的重復(fù)執(zhí)行過(guò)程，并對(duì)每次函數(shù)調(diào)用單獨(dú)計(jì)算它的時(shí)間。那么，就可將抽象機(jī)模型上定義的概念用于分析由具體程序設(shè)計(jì)語(yǔ)言描述的算法。對(duì)于用C/C++語(yǔ)言描述的算法，可將每種可執(zhí)行語(yǔ)句（除循環(huán)語(yǔ)句外）看成一種基本運(yùn)算；對(duì)于循環(huán)語(yǔ)句，需計(jì)算其循環(huán)體的執(zhí)行次數(shù)。這就可以通過(guò)一個(gè)算法在給定輸入下所執(zhí)行的總的語(yǔ)句條數(shù)來(lái)計(jì)算算法的時(shí)間復(fù)雜度。下面定義的程序步概念可進(jìn)一步簡(jiǎn)化算法分析。它并不直接計(jì)算總的語(yǔ)句執(zhí)行條數(shù)，而是將若干條語(yǔ)句合并成一個(gè)程序步來(lái)計(jì)算。

一個(gè)程序步（program step）是指在語(yǔ)法上或語(yǔ)義上有意義的程序段，該程序段的執(zhí)行時(shí)間必須與問(wèn)題實(shí)例的規(guī)模無(wú)關(guān)。

現(xiàn)以程序2-1求數(shù)組元素之和為例來(lái)說(shuō)明如何計(jì)算一個(gè)算法的程序步數(shù)。設(shè)n個(gè)元素存放在一維數(shù)組list中，count是全局變量，用來(lái)計(jì)算總的程序步數(shù)。在程序中，語(yǔ)句count++;與數(shù)組求和的算法無(wú)關(guān)，只是為了計(jì)算程序步數(shù)而添加的。忽略所有count++;語(yǔ)句，便是一個(gè)數(shù)組求和程序。可以看到，這里被計(jì)算的每一程序步的執(zhí)行時(shí)間，均與問(wèn)題實(shí)例的規(guī)模n（數(shù)組元素的個(gè)數(shù)）無(wú)關(guān)。該程序的總程序步數(shù)為2n+3。

【程序2-1】 求數(shù)組元素累加之和的迭代程序

float Sum(float list[], const int n)
{
     float tempsum=0.0;
     count ++; //針對(duì)賦值語(yǔ)句
     for (int i=0; i<n; i++){
          count ++; //針對(duì)for循環(huán)語(yǔ)句
          tempsum+=list[i];
          count ++; //針對(duì)賦值語(yǔ)句
     }
     count ++; //針對(duì)for的最后一次執(zhí)行
     count ++; //針對(duì)return語(yǔ)句
     return tempsum;
}

程序2-2是求數(shù)組元素之和的遞歸程序。為了確定這一遞歸程序的程序步，首先考慮當(dāng)n=0時(shí)的情況。很明顯，當(dāng)n=0時(shí)，程序只執(zhí)行if條件判定和第二個(gè)return語(yǔ)句，所需的程序步數(shù)為2。當(dāng)n＞0時(shí)，程序在執(zhí)行if條件判定后，將執(zhí)行第一個(gè)return語(yǔ)句。此return語(yǔ)句不是簡(jiǎn)單返回，而是在調(diào)用函數(shù)RSum(list,n-1)后，再執(zhí)行一次加法運(yùn)算后返回。讀者同樣可以移去程序RSum中所有count++;語(yǔ)句，得到一般的數(shù)組求和遞歸程序。

設(shè)RSum(list,n)的程序步為T(n)，RSum(list,n-1)的程序步為T(n-1)，那么，當(dāng)n＞0時(shí)，T(n)=T(n-1)+2。于是有：

這是一個(gè)遞推關(guān)系式，它可以通過(guò)轉(zhuǎn)換成如下和式來(lái)計(jì)算：

T(n)=2+T(n-1)=2+2+T(n-2)

=2×3+T(n-3)

…

=2×n+T(0)

=2×n+2

雖然從表面看來(lái)，程序RSum所需的程序步為2n+2，少于程序Sum的程序步2n+3，但這并不意味著前者比后者快，這是因?yàn)閮烧呤褂玫某绦虿绞遣煌摹＿f歸調(diào)用引起的循環(huán)計(jì)算和使用for語(yǔ)句的循環(huán)計(jì)算所需的開(kāi)銷(xiāo)是不同的，遞歸需要耗費(fèi)更多的時(shí)間和空間資源。有關(guān)遞歸算法及其分析方法將在本章稍后及以后章節(jié)中做進(jìn)一步討論。

【程序2-2】 求數(shù)組元素累加之和的遞歸程序

float RSum(float list[], const int n)
{
  count ++; //針對(duì) if 條件
  if (n){
    count++; //針對(duì) RSum 調(diào)用和return語(yǔ)句
    return RSum(list, n-1)+list[n-1];
  }
  count++; //針對(duì)return語(yǔ)句
  return 0;
}

2.1.5 算法的空間復(fù)雜度

一個(gè)算法的空間復(fù)雜度（space complexity）是指算法運(yùn)行所需的存儲(chǔ)空間。程序運(yùn)行所需的存儲(chǔ)空間包括以下兩部分。

（1）固定空間需求（fixed space requirement）：這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無(wú)關(guān)，也就是說(shuō)，與問(wèn)題實(shí)例的特征無(wú)關(guān)，主要包括程序代碼、常量、簡(jiǎn)單變量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。

（2）可變空間需求（variable space requirement）：這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。例如，分別包含100個(gè)元素的兩個(gè)數(shù)組相加，與分別包含10個(gè)元素的兩個(gè)數(shù)組相加，所需的存儲(chǔ)空間顯然是不同的。這部分存儲(chǔ)空間包括數(shù)據(jù)元素所占的空間，以及算法執(zhí)行所需的額外空間，例如，運(yùn)行遞歸算法所需的系統(tǒng)棧空間。

對(duì)算法空間復(fù)雜度的討論類(lèi)似于時(shí)間復(fù)雜度，并且一般來(lái)說(shuō)，空間復(fù)雜度的計(jì)算比起時(shí)間復(fù)雜度的計(jì)算容易。此外，應(yīng)當(dāng)注意的是，空間復(fù)雜度一般按最壞情況來(lái)分析。

2.2 漸近表示法

引入程序步的目的在于簡(jiǎn)化算法的事前分析。正如前面已經(jīng)討論過(guò)的，不同的程序步在計(jì)算機(jī)上的實(shí)際執(zhí)行時(shí)間通常是不同的，程序步數(shù)并不能確切反映程序運(yùn)行的實(shí)際時(shí)間。而且事實(shí)上，一個(gè)程序在一次執(zhí)行中的總程序步的精確計(jì)算往往也是困難的。那么，引入程序步的意義何在？本節(jié)中定義的漸近時(shí)間復(fù)雜度，使得有望使用程序步在數(shù)量級(jí)上估計(jì)一個(gè)算法的執(zhí)行時(shí)間，從而實(shí)現(xiàn)算法的事前分析。

2.2.1 大O記號(hào)

定義2-1 設(shè)函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≤cg(n)，則記做f(n)=O(g(n))，稱(chēng)為大O記號(hào)（big Oh notation）。

大O記號(hào)可以看成n的函數(shù)的集合。O(g(n))表示所有增長(zhǎng)階數(shù)不超過(guò)g(n)的函數(shù)的集合，它用以表達(dá)一個(gè)算法運(yùn)行時(shí)間的上界。稱(chēng)一個(gè)算法具有O(g(n))的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，該算法在計(jì)算機(jī)上的實(shí)際運(yùn)行時(shí)間不會(huì)超過(guò)g(n)的某個(gè)常數(shù)倍，g(n)是它的一個(gè)上界。

例2-1 f(n)=2n+3=O(n)

當(dāng)n≥3時(shí)，2n+3≤3n，所以，可選c=3，n0=3。對(duì)于n≥n0，f(n)=2n+3≤3n，所以，f(n)=O(n)，即2n+3∈O(n)。這意味著，當(dāng)n≥3時(shí)，程序2-1的程序步不會(huì)超過(guò)3n，2n+3=O(n)。

例2-2 f(n)=10n2+4n+2=O(n2)

對(duì)于n≥2時(shí)，有10n2+4n+2≤10n2+5n，并且當(dāng)n≥5時(shí)，5n≤n2，因此，可選c=11, n0=5；對(duì)于n≥n0，f(n)=10n2+4n+2≤11n2，所以f(n)=O(n2)。

例2-3 f(n)=n！=O(nn)

對(duì)于n≥1，有n(n-1)(n-2) … 1≤nn，因此，可選c=1，n0=1。對(duì)于n≥n0，f(n)= n！≤nn，所以，f(n)=O(nn)。

例2-4 10n2+9≠O(n)

使用反證法，假定存在c和n0，使得對(duì)于n≥n0，10n2+9≤cn始終成立，那么有10n+9/n≤c，即n≤c/10-9/(10n)總成立。但此不等式不可能總成立，取n=c/10+1時(shí)，該不等式便不再成立。

上面的例子也表明這樣的事實(shí)，即對(duì)于給定的f，可有無(wú)數(shù)個(gè)g與之對(duì)應(yīng)。例如，f(n)=2n+3，g可以是：n，n2，n3，…。在算法分析中，應(yīng)當(dāng)選擇最小的函數(shù)g作為f的上界。

定理2-1 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=O(nm)。

證明：取n0=1，當(dāng)n≥n0時(shí)，有

可取c=|am|+|am-1|+…+|a1|+|a0|，定理得證。

假定一個(gè)程序的實(shí)際執(zhí)行時(shí)間T(n)=3.6n3+2.5n2+2.8，以上定理表明T(n)=O(n3)。這就是說(shuō)，如果只能知道一個(gè)算法的時(shí)間是T(n)=O(n3)，雖然并不能得到T(n)=3.6n3+2.5n2+2.8這一精確計(jì)算公式，但從算法事前分析的角度，可以認(rèn)為已經(jīng)有了對(duì)算法時(shí)間復(fù)雜度上界的滿(mǎn)意的估計(jì)值。

使用大O記號(hào)及下面定義的幾種漸近表示法表示的算法時(shí)間復(fù)雜度，稱(chēng)為算法的漸近時(shí)間復(fù)雜度（asymptotic complexity）。漸近時(shí)間復(fù)雜度也常簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。記號(hào)O(1)用于表示常數(shù)計(jì)算時(shí)間，它代表算法只需執(zhí)行有限個(gè)程序步。

在很多情況下，可以通過(guò)考察一個(gè)程序中關(guān)鍵操作（key operation）的執(zhí)行次數(shù)，來(lái)估算算法的漸近時(shí)間復(fù)雜度。有時(shí)也需要同時(shí)考慮幾個(gè)關(guān)鍵操作，以反映算法的執(zhí)行時(shí)間。例如，程序2-1中，語(yǔ)句tempsum+=list[i];可被認(rèn)為是關(guān)鍵操作，它的執(zhí)行次數(shù)為n，與總的程序步2n+3有相同的漸近時(shí)間復(fù)雜度O(n)。

只要適當(dāng)選擇關(guān)鍵操作，算法的漸近時(shí)間復(fù)雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來(lái)計(jì)算。一般，關(guān)鍵操作的執(zhí)行次數(shù)與問(wèn)題的規(guī)模有關(guān)，是n的函數(shù)。在很多情況下，它是算法中執(zhí)行次數(shù)最多的操作（程序步）。關(guān)鍵操作通常是位于算法最內(nèi)層循環(huán)的程序步（或語(yǔ)句）。

程序2-3是實(shí)現(xiàn)兩個(gè)n×n矩陣相乘的程序段，每行最右邊注明該行語(yǔ)句執(zhí)行的次數(shù)，即作為程序步看待。對(duì)于循環(huán)語(yǔ)句for (i=0; i<n; i++) {y;}，可以認(rèn)為循環(huán)體y執(zhí)行n次，而for自身執(zhí)行n+1次比較運(yùn)算（i＜n）。因此，程序中所有語(yǔ)句的執(zhí)行次數(shù)為T(n)=2n3+3n2+2n+1。由定理2-1可知，程序2-3的漸近時(shí)間復(fù)雜度為O(n3)。如果將語(yǔ)句c[i][j]+=a[i][k]*b[k][j];看成關(guān)鍵操作，它的執(zhí)行次數(shù)是n3，從它同樣可以得到O(n3)。

【程序2-3】 矩陣乘法

for（i=0; i<n; i++） //n+1
   for（j=0; j<n; j++）{ //n(n+1)
     c[i][j]=0; //n2
     for（k=0; k<n; k++） //n2(n+1)
          c[i][j]+=a[i][k]*b[k][j]; //n3
     }

有時(shí)，算法的時(shí)間計(jì)算并非直截了當(dāng)。例如，程序1-2求最大公約數(shù)遞歸算法的運(yùn)行時(shí)間是多少？雖然看起來(lái)余數(shù)的值在減小，卻并不是按常數(shù)因子遞減的。定理2-2表明，兩次迭代以后，余數(shù)最多是原始值的一半。這就證明了迭代次數(shù)最多為2logm=O(logm)，所以歐幾里得算法的時(shí)間復(fù)雜度為O(logn+logm)。

定理2-2 如果n＞m，則n mod m＜n/2。

證明：如果m≤n/2，則由于余數(shù)小于m，故定理在這種情形下成立。當(dāng)m＞n/2時(shí)，n-m＜n/2，定理得證。

2.2.2 W記號(hào)

定義2-2 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù) c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≥c g(n)，則記做f(n)=Ω(g(n))，稱(chēng)為Ω記號(hào)（omega notation）。

Ω記號(hào)可以看成n的函數(shù)的集合。Ω(g(n))表示所有增長(zhǎng)階數(shù)不低于g(n)的函數(shù)的集合，它用于表示一個(gè)算法運(yùn)行時(shí)間的下界。稱(chēng)一個(gè)算法具有Ω(g(n))的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，該算法在計(jì)算機(jī)上運(yùn)行，至少需要g(n)的某個(gè)常數(shù)倍大小的時(shí)間量。

例2-5 f(n)=2n+3=Ω(n)

對(duì)所有n，2n+3≥2n，可選c=2，n0=0。對(duì)于n≥n0，f(n)=2n+3≥2n，所以，f(n)=Ω(n)，即2n+3∈Ω(n)。

例2-6 f(n)=10n2+4n+2=Ω(n2)

對(duì)所有n，10n2+4n+2≥10n2，可選c=10，n0=0。對(duì)于n≥n0，f(n)=10n2+4n+2≥10n2，所以，f(n)=Ω(n2)。

與大O記號(hào)類(lèi)似，對(duì)于給定f，可有無(wú)數(shù)個(gè)g與之對(duì)應(yīng)。例如，f=10n2+4n+2，g可以是n2，n1，n1/2，…。應(yīng)當(dāng)選擇最接近的函數(shù)g，即f的最大下界。

定理2-3 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=Ω( nm)。

證明留做練習(xí)。

本章一開(kāi)始提到了在n個(gè)元素的集合中求最大元素的問(wèn)題。直觀地考慮，我們可以設(shè)計(jì)一個(gè)算法，通過(guò)對(duì)集合中的元素進(jìn)行比較，最終確定最大元素。元素間的比較運(yùn)算顯然是這一算法的關(guān)鍵操作。能夠初步斷定，對(duì)于求解這一問(wèn)題的任意正確算法，至少需做n-1次比較，才能求得最大元素。因?yàn)榧偃绫容^次數(shù)不足n-1次，那么很顯然，至少有一個(gè)元素未和其他元素做過(guò)比較，這樣的算法不可能是正確的。因此，f(n)≥n-1=Ω(n)。這里，十分有意義的是，Ω(n)不僅是具體某一個(gè)求最大元素算法的時(shí)間下界，它也是求最大元素問(wèn)題的時(shí)間下界。這就是算法的最優(yōu)性問(wèn)題。

2.2.3 Θ記號(hào)

定義2-3 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當(dāng)n≥n0時(shí)，有c1g(n)≤f(n)≤c2 g(n)，則記做f(n)=Θ(g(n))，稱(chēng)為Θ記號(hào)（Theta notation）。

Θ記號(hào)可以看成n的函數(shù)的集合。Θ(g(n))表示所有增長(zhǎng)階數(shù)與g(n)相同的函數(shù)的集合，它用于表示一個(gè)算法運(yùn)行時(shí)間具有與g(n)相同的階。稱(chēng)一個(gè)算法具有Θ(g(n))的運(yùn)行時(shí)間，是指當(dāng)n足夠大時(shí)，該算法在計(jì)算機(jī)上的實(shí)際運(yùn)行時(shí)間大約為g(n)某個(gè)常數(shù)倍大小的時(shí)間量。從上兩節(jié)討論可知，下面例2-7和例2-8的結(jié)論成立。

例2-7 f(n)=2n+3=Θ(n)，即2n+3∈Θ(n)。

例2-8 f(n)=10n2+4n+2=Θ(n2)。

定理2-4 如果f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=Θ(nm)。

證明留做練習(xí)。

2.2.4 小o記號(hào)

定義2-4 f(n)=o(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)≠Ω(g(n))

小o記號(hào)（little Oh notation）可以看成n的函數(shù)的集合。o(g(n))表示所有增長(zhǎng)階數(shù)小于g(n)的所有函數(shù)的集合，它用于表示一個(gè)算法運(yùn)行時(shí)間f(n)的階比g(n)低。從上面的討論可知，例2-9的結(jié)論成立。

例2-9 f(n)=2n+3=o(n2)，即2n+3∈o(n2)。

2.2.5 算法按時(shí)間復(fù)雜度分類(lèi)

算法可以按計(jì)算時(shí)間分成兩類(lèi)：凡漸近時(shí)間復(fù)雜度為多項(xiàng)式時(shí)間限界的算法稱(chēng)做多項(xiàng)式時(shí)間算法（polynomial time algorithm），而漸近時(shí)間復(fù)雜度為指數(shù)函數(shù)限界的算法稱(chēng)做指數(shù)時(shí)間算法（exponential time algorithm）。

最常見(jiàn)的多項(xiàng)式時(shí)間算法的漸近時(shí)間復(fù)雜度之間的關(guān)系為：

O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n2)＜O(n3)

最常見(jiàn)的指數(shù)時(shí)間算法的漸近時(shí)間復(fù)雜度之間的關(guān)系為：

O(2n)＜O(n！)＜O(nn)

隨著n的增大，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需的時(shí)間上非常懸殊。表2-1和圖2-1顯示了幾種典型的時(shí)間函數(shù)隨問(wèn)題規(guī)模增長(zhǎng)的情況。

表2-1 時(shí)間復(fù)雜度函數(shù)增長(zhǎng)情況

從圖2-1中可以看到，O(log n)、O(n)和O(nlog n)的增長(zhǎng)比較平穩(wěn)，指數(shù)函數(shù)2n的曲線(xiàn)非常陡。實(shí)際情況是，對(duì)大的n值，在目前一般計(jì)算機(jī)上，運(yùn)行一個(gè)復(fù)雜度高于O(nlog n)的算法已經(jīng)很困難了。對(duì)于指數(shù)時(shí)間算法，只有當(dāng)n很小時(shí)才有實(shí)用價(jià)值。

假定計(jì)算機(jī)執(zhí)行每條語(yǔ)句的時(shí)間是相等的，都是1毫秒，那么1小時(shí)可以執(zhí)行3.6×106條語(yǔ)句。如果要求算法的執(zhí)行時(shí)間不超過(guò)1小時(shí)，那么，對(duì)于一個(gè)時(shí)間復(fù)雜度為nlogn的算法，所能處理的問(wèn)題的規(guī)模約可達(dá)2.0×105；而對(duì)于時(shí)間復(fù)雜度為2n的算法，情況就糟得多，在1小時(shí)內(nèi)算法只能處理n不超過(guò)21的小問(wèn)題。如果將計(jì)算機(jī)速度提高1萬(wàn)倍，那么，對(duì)于時(shí)間復(fù)雜度是nlogn的算法，能處理的問(wèn)題規(guī)模可以從n大約提高到9000n；但對(duì)于有指數(shù)時(shí)間2n的算法，所能處理的問(wèn)題規(guī)模只能增加到n+13.3左右。這就是說(shuō)，提高計(jì)算機(jī)速度，可以較大幅度地增加具有線(xiàn)性或nlogn時(shí)間算法所能處理的問(wèn)題的能力，但對(duì)指數(shù)時(shí)間算法的收效甚微。

對(duì)算法進(jìn)行時(shí)間分析，是為了盡可能降低算法時(shí)間復(fù)雜度的數(shù)量級(jí)。上述討論表明，為了提高程序運(yùn)行速度，選擇一種更快的算法比換一臺(tái)更快的機(jī)器奏效。

2.3 遞推關(guān)系

2.3.1 遞推方程

遞推關(guān)系經(jīng)常用來(lái)分析遞歸算法的時(shí)間和空間代價(jià)。分析一個(gè)遞歸算法的時(shí)間一般需要列出關(guān)于時(shí)間復(fù)雜度函數(shù)的遞推關(guān)系式。

遞推方程（recurrence equation）是自然數(shù)上一個(gè)函數(shù)T(n)，它使用一個(gè)或多個(gè)小于n時(shí)的值的等式或不等式來(lái)描述。遞推方程也稱(chēng)為遞推關(guān)系或遞推式。第2.1.4節(jié)中的式（2-5）就是對(duì)于程序2-2的時(shí)間分析的遞推方程。

遞推方程必須有一個(gè)初始條件（也稱(chēng)邊界條件），式（2-5）中的T(0)=2就是該遞推方程的初始條件。有時(shí)需要給定的初始條件不一定是當(dāng)n=0時(shí)的值，也可以使用n=1或n=2等其他小的n值作為遞推方程的初始值。

例2-10 程序1-5的時(shí)間分析

設(shè)n=d1d2…dk是k位數(shù)，當(dāng)k=1時(shí)，只執(zhí)行cout語(yǔ)句和if判定語(yǔ)句；當(dāng)n至少是2位數(shù)（k＞1）時(shí)，除了執(zhí)行這兩個(gè)操作外，還需執(zhí)行遞歸函數(shù)調(diào)用PrintDigit(n/10)，是k-1位數(shù)，于是得到式（2-6）的遞推式：

可以采用與式（2-5）相同的方法，將其轉(zhuǎn)換成和式來(lái)計(jì)算。這種方法稱(chēng)為迭代方法。從式（2-5）可知式（2-6）的計(jì)算結(jié)果是：

T(k)=2k+2=Θ(k)

計(jì)算遞推式通常有三種方法：迭代方法（iterating）、替換方法（substitution）和主方法（master method）。

迭代方法通過(guò)擴(kuò)展遞推，把遞推式先轉(zhuǎn)換成一個(gè)和式，然后使用求和技術(shù)進(jìn)行計(jì)算。替換方法需要先猜測(cè)遞推式的解（漸近復(fù)雜度的上、下界），然后使用歸納法證明該上、下界，還可能需要進(jìn)一步做收縮，得到最接近的上、下界。主方法是對(duì)算法分析中一類(lèi)典型的遞推式T(n)= aT(n/b)+f(n)，利用已經(jīng)證明的主定理直接得到漸近復(fù)雜度的方法。

一般來(lái)說(shuō)，問(wèn)題的規(guī)模是非負(fù)整數(shù)，而且對(duì)足夠小的問(wèn)題，算法的運(yùn)行時(shí)間可視為常量，所以，在以后討論中，當(dāng)描述遞推式時(shí)，如果沒(méi)有明確指明，則都假定n是非負(fù)整數(shù)，并假定對(duì)足夠小的n值，T(n)是常量。

2.3.2 替換方法

替換方法要求首先猜測(cè)遞推式的解，然后用歸納法證明。下面使用替換方法計(jì)算漢諾塔問(wèn)題的遞推式。

例2-11 使用替換方法分析程序1-6

分析漢諾塔問(wèn)題，得到遞推式：T(1)=1, T(n)=2T(n-1)+1。可以先對(duì)以下這些小的示例進(jìn)行計(jì)算：

T(3)=7=23-1；T(4)=15=24-1；T(5)=31=25-1；T(6)=63=26-1

看起來(lái)，似乎T(n)=2n-1，n≥1，下面再用歸納法證明這一結(jié)論。

證明：（歸納法證明）

當(dāng)n=1時(shí)，T(1)=1，結(jié)論成立。歸納法假設(shè)：當(dāng)k＜n時(shí)，有T(k)=2k-1，那么，當(dāng)k=n時(shí)，T(n)=2T(n-1)+1=2(2n-1-1)+1=2n-1。因此，對(duì)所有n≥1，T(n)=2n-1=Θ(2n)。

2.3.3 迭代方法

迭代方法的思想是擴(kuò)展遞推式，將遞推式先轉(zhuǎn)換成一個(gè)和式，然后計(jì)算該和式，得到漸近復(fù)雜度。它需要較多的數(shù)學(xué)運(yùn)算。

例2-12 使用迭代方法分析程序1-6

函數(shù)Hanoi中兩次調(diào)用自身，函數(shù)調(diào)用使用的實(shí)在參數(shù)均為n-1，函數(shù)Move所需時(shí)間具有常數(shù)界Θ(1)，可以將其視為一個(gè)程序步，于是有：

擴(kuò)展并計(jì)算此遞推式：

T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=22T(n-2)+2+1

=23T(n-3)+22+2+1

…

=2n-1T(1)+…+22+2+1=2n-1+…+22+2+1=2n-1

漢諾塔問(wèn)題也稱(chēng)梵天塔問(wèn)題（tower of Brahma）。相傳印度教的天神梵天在創(chuàng)造地球時(shí)，建了一座神廟，神廟中有三根柱子，第一根柱子上從小到大套著64個(gè)金盤(pán)，形成所謂的梵天塔。天神讓僧侶們按照前面介紹的規(guī)則，將64個(gè)金盤(pán)從第一根柱子，借助第二根柱子移到第三根柱子。天神斷言，移完的那一天就是世界末日。從上面的計(jì)算可知，當(dāng)n=64時(shí)，要完成梵天塔搬遷需要移動(dòng)盤(pán)子的次數(shù)為：264-1=18446744073709551615。如果每秒移一次，需要500億年以上。這也使我們看到，指數(shù)時(shí)間算法僅對(duì)規(guī)模很小的問(wèn)題是可用的。

使用遞歸樹(shù)（recursion tree）可以形象地看到遞推式的迭代過(guò)程。下面舉例說(shuō)明對(duì)給定的遞推方程，通過(guò)構(gòu)造遞歸樹(shù)來(lái)求解的方法。

例2-13 T(n)=2T(n/2)+n的遞歸樹(shù)

為方便起見(jiàn)，假定n是2的整數(shù)冪。圖2-2顯示該遞推方程的遞歸樹(shù)的導(dǎo)出過(guò)程。遞歸樹(shù)上每個(gè)結(jié)點(diǎn)有兩個(gè)域：遞歸式T(n)和非遞歸的代價(jià)，n是問(wèn)題規(guī)模。本例中，根結(jié)點(diǎn)時(shí)的規(guī)模為n，本例的非遞歸代價(jià)恰好也是n。根結(jié)點(diǎn)擴(kuò)展兩棵子樹(shù)，因此，第二層有兩個(gè)結(jié)點(diǎn)，規(guī)模為n/2，非遞歸代價(jià)各為n/2。繼續(xù)這一擴(kuò)展過(guò)程，直到達(dá)到初始條件（邊界條件）。圖2-2的遞歸樹(shù)高度（層數(shù)）為logn+1，每一層的非遞歸代價(jià)之和均為n。現(xiàn)將樹(shù)中所有層的代價(jià)加起來(lái)便得到遞推方程的解為Θ(nlogn)。

例2-14 T(n)=T(n/3)+T(2n/3)+n的遞歸樹(shù)

例2-14給出了另一個(gè)更復(fù)雜的例子，圖2-3是其對(duì)應(yīng)的遞歸樹(shù)。從根到葉的最長(zhǎng)的一條路徑是n→(2/3)n→(2/3)2n→…→1。因?yàn)?2/3)kn=1，k=log3/2n，該樹(shù)的高度（層數(shù)）為log3/2n+1。因而，此遞推方程的解至多是n(log3/2n+1)=O(nlogn)。

2.3.4 主方法

在遞歸算法分析中，常需要求解如下形式的遞推式：

T(n)=aT(n/b)+f(n) （2-8）

式中，a≥1和b＞1是常數(shù)，f(n)是一個(gè)漸近正函數(shù)，n/b指或。

求解這類(lèi)遞推式的方法稱(chēng)為主方法。主方法依賴(lài)于下面的主定理，使用主定理可直接得到遞推式的解。關(guān)于主定理的證明見(jiàn)文獻(xiàn)[2]。

定理2-5 （主定理）設(shè)a≥1和b＞1為常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由下面的遞推式定義

T(n)=aT(n/b)+f(n)

式中，n/b指或，則T(n)有如下的漸近界：

（1）若對(duì)某常數(shù)＞0，有f(n)=O()，則T(n)=Θ()；

（2）若f(n)=Θ()，則T(n)=Θ(logn)；

（3）若對(duì)某常數(shù)＞0，有f(n)=Ω()，且對(duì)某個(gè)常數(shù)c＜1和所有足夠大的n，有af(n/b)≤cf(n)，則T(n)=Θ(f(n))。

需要注意的是，主定理的三種情況并沒(méi)有覆蓋所有的f(n)，存在某些f(n)不滿(mǎn)足以上任何一種情況的條件，則此時(shí)就不能用主方法求解遞推式。下面通過(guò)幾個(gè)例子介紹主定理的應(yīng)用。

例2-15 T(n)=16T(n/4)+n

因?yàn)?span id="hl19mp8" class="italic">a=16, b=4,=n2, f(n)=n=O()=O)，其中，=1與主定理的情況（1）相符合，T(n)=Θ()=Θ(n2)。

例2-16 T(n)=T(3n/7)+1

因?yàn)?span id="sijroxv" class="italic">a=1, b=7/3,==n0=1, f(n)=1=Θ()，所以，符合主定理情況（2），T(n)=Θ(logn)=Θ(logn)。

例2-17 T(n)=3T(n/4)+n logn

因?yàn)?span id="jytgrne" class="italic">a=3, b=4,，其中，≈0.2。由于對(duì)足夠大的n，3(n/4)log(n/4)≤(3/4)nlogn，這里c=3/4，符合主定理情況（3）。T(n)=Θ(f(n))=Θ(nlogn)。

并非所有遞推式都可用主定理求解，主定理對(duì)例2-18的遞推式并不適用。

例2-18 T(n)=2T(n/2)+nlogn

由于a=2, b=2, f(n)=nlogn和=n。看起來(lái)似乎屬于主定理情況（3），但事實(shí)上不是。因?yàn)?span id="96ipezv" class="italic">f(n)只是漸近大于n，但并不是多項(xiàng)式大于n。f(n)與的比值是log n，對(duì)于任何正數(shù)，log n漸近小于，所以，此例不能運(yùn)用主定理。

2.4 分?jǐn)偡治?/h3>

在很多情況下，對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)的操作往往不是單獨(dú)執(zhí)行一次運(yùn)算，而是重復(fù)多次執(zhí)行多個(gè)運(yùn)算，形成一個(gè)運(yùn)算執(zhí)行序列。如果執(zhí)行n個(gè)運(yùn)算的總時(shí)間為T(n)，則每個(gè)運(yùn)算的平均代價(jià)（average cost）為T(n)/n，分?jǐn)偡治龅哪康氖乔笃骄鷥r(jià)。

分?jǐn)偡治?/span>（amortized analysis）是對(duì)一個(gè)長(zhǎng)的運(yùn)算序列所需的最壞情況時(shí)間求平均值。設(shè)在最壞情況下，對(duì)所有n，執(zhí)行一個(gè)長(zhǎng)度為n的運(yùn)算序列所需的最壞情況時(shí)間為T(n)，那么，每個(gè)運(yùn)算平均代價(jià)為T(n)/n。

分?jǐn)偡治龊推骄闆r分析的不同之處在于它不需要假定每個(gè)運(yùn)算的概率，因而不涉及概率。分?jǐn)偡治霰ＷC在最壞情況下一個(gè)運(yùn)算序列中每個(gè)運(yùn)算的平均性能。

分?jǐn)偡治鲆话阌腥N方法：聚集方法、會(huì)計(jì)方法和勢(shì)能方法。

2.4.1 聚集方法

聚集方法（aggregate analysis）中需要對(duì)所有n，計(jì)算由n個(gè)運(yùn)算構(gòu)成的運(yùn)算序列在最壞情況下總的執(zhí)行時(shí)間T(n)，則每個(gè)運(yùn)算的平均代價(jià)為T(n)/n。請(qǐng)注意，序列中允許包含不同種類(lèi)的運(yùn)算，但每個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)是相同的。

例2-19 設(shè)堆棧上定義了兩個(gè)運(yùn)算：void Push(T x)和T Pop()，T是元素類(lèi)型，前者將對(duì)象x進(jìn)棧，后者從棧中彈出并返回棧頂元素。已知這兩種運(yùn)算的時(shí)間都是O(1)，不妨假定每個(gè)運(yùn)算的程序步數(shù)（即代價(jià)）是1。這樣，執(zhí)行一個(gè)包含n次運(yùn)算的序列的總代價(jià)為n，其運(yùn)行時(shí)間為Θ(n)，因此，每個(gè)運(yùn)算的平均代價(jià)為T(n)/n=Θ(n)/n=Θ(1)。計(jì)算中沒(méi)有用到概率。

例2-20 設(shè)在上例的棧數(shù)據(jù)結(jié)構(gòu)上定義一個(gè)新運(yùn)算void MultiPop(int k)，該運(yùn)算從棧中連續(xù)彈出k個(gè)元素。

現(xiàn)在來(lái)分析從空棧開(kāi)始，執(zhí)行一個(gè)包括n個(gè)Push、Pop和MultiPop構(gòu)成的運(yùn)算序列的最壞情況時(shí)間。很顯然，MultiPop運(yùn)算的最壞情況時(shí)間是O(n)，因?yàn)樵趫?zhí)行n次棧運(yùn)算中，棧的大小最多為n。那么，能否因此認(rèn)為一個(gè)包含n次棧運(yùn)算的序列，在最壞情況下的總時(shí)間是O(n2)，從而得到每個(gè)棧運(yùn)算在最壞情況下的平均時(shí)間為O(n)呢？雖然這樣分析是正確的，但不夠精確。下面的聚集分析將獲得一個(gè)更精確的上界。

事實(shí)上，從初始空棧開(kāi)始，任意一個(gè)包含n個(gè)Push、Pop和MultiPop運(yùn)算的執(zhí)行序列總的程序步至多是n步。這是很顯然的，因?yàn)槊繅喝胍粋€(gè)元素，至多可彈出一個(gè)元素。在一個(gè)非空棧上執(zhí)行Pop和MultiPop時(shí)，被彈出的元素總數(shù)不超過(guò)Push的執(zhí)行次數(shù)。因此，對(duì)任意n，一個(gè)包含n個(gè)棧運(yùn)算的序列的總執(zhí)行時(shí)間為O(n)，因而每個(gè)運(yùn)算的平均代價(jià)為O(n)/n=O(1)。

2.4.2 會(huì)計(jì)方法

對(duì)于給定的數(shù)據(jù)結(jié)構(gòu)，會(huì)計(jì)方法（accounting method）對(duì)每個(gè)運(yùn)算預(yù)先賦予不同的費(fèi)值（charge）。其中，某些運(yùn)算的費(fèi)值可能超過(guò)它們的實(shí)際代價(jià)（actual cost），而另一些運(yùn)算的費(fèi)值會(huì)低于實(shí)際代價(jià)。對(duì)每個(gè)運(yùn)算所記的費(fèi)值稱(chēng)為分?jǐn)偞鷥r(jià)（amortized cost）。其超出部分如同存款（credit）一樣保存起來(lái)，用于補(bǔ)償以后代價(jià)不足的運(yùn)算。與聚集分析不同的是，會(huì)計(jì)方法的分?jǐn)偞鷥r(jià)可以不同，而聚集分析中每個(gè)運(yùn)算有相同的分?jǐn)偞鷥r(jià)。

使用會(huì)計(jì)方法，首先按預(yù)先分配給每個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)，計(jì)算一個(gè)運(yùn)算序列的總的分?jǐn)偞鷥r(jià)。如果能夠保證對(duì)所有n，任意一個(gè)運(yùn)算序列的總分?jǐn)偞鷥r(jià)不會(huì)低于該運(yùn)算序列的實(shí)際代價(jià)T(n)，即運(yùn)算序列的總的分?jǐn)偞鷥r(jià)是總的實(shí)際代價(jià)的上界，設(shè)總分?jǐn)偞鷥r(jià)為O(g(n))，則T(n)=O(g(n))。

這就要求在一個(gè)運(yùn)算序列執(zhí)行的任何時(shí)刻，總分?jǐn)偞鷥r(jià)始終不低于該時(shí)刻的實(shí)際代價(jià)。如果在一個(gè)運(yùn)算序列的執(zhí)行中，隨時(shí)記錄下迄今為止的累計(jì)分?jǐn)偞鷥r(jià)減去實(shí)際代價(jià)的余額，則這一累計(jì)余額始終應(yīng)當(dāng)是非負(fù)的。如果在執(zhí)行某個(gè)運(yùn)算后，代價(jià)余額出現(xiàn)負(fù)值，則說(shuō)明迄今為止的分?jǐn)偞鷥r(jià)低于當(dāng)時(shí)消費(fèi)的實(shí)際代價(jià)，這種情形表示這樣計(jì)算的總分?jǐn)偞鷥r(jià)將不能作為總的實(shí)際代價(jià)的上界來(lái)計(jì)算每個(gè)運(yùn)算的平均代價(jià)。請(qǐng)注意區(qū)分分?jǐn)偞鷥r(jià)和平均代價(jià)。

例2-21 使用會(huì)計(jì)方法分析例2-20的棧運(yùn)算

會(huì)計(jì)分析首先需要精心分配每個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)，代價(jià)用程序步度量。表2-2列出各個(gè)棧運(yùn)算的實(shí)際代價(jià)和分?jǐn)偞鷥r(jià)，其中，Min(k, m)中的k是運(yùn)算MultiPop的參數(shù)，m是執(zhí)行此運(yùn)算時(shí)，棧中元素的個(gè)數(shù)。

表2-2 棧運(yùn)算的實(shí)際代價(jià)和分?jǐn)偞鷥r(jià)

在表2-2中，對(duì)Push預(yù)分配的分?jǐn)偞鷥r(jià)為2，顯然超過(guò)了此運(yùn)算的實(shí)際代價(jià)，而對(duì)Pop和MultiPop分配的分?jǐn)偞鷥r(jià)都為0，低于實(shí)際代價(jià)，但事實(shí)上，MultiPop的實(shí)際代價(jià)是隨參數(shù)k變化的。通過(guò)仔細(xì)分析可知，表2-2的分?jǐn)偞鷥r(jià)分配方式是可行的，因?yàn)樗梢员ＷC在執(zhí)行一個(gè)運(yùn)算序列的任何時(shí)刻，其代價(jià)余額不會(huì)為負(fù)值。理由是：每執(zhí)行一次Push有一個(gè)程序步的節(jié)余，可用于支付一次Pop運(yùn)算或MultiPop運(yùn)算的一步（彈出一個(gè)元素）。由于必須執(zhí)行一次Push，才有可能執(zhí)行一次Pop或MultiPop的一步，因此，關(guān)于堆棧操作的總代價(jià)余額不會(huì)為負(fù)值。這樣，總分?jǐn)偞鷥r(jià)O(n)必定是總實(shí)際代價(jià)的上界，T(n)=O(n)，每個(gè)運(yùn)算的平均代價(jià)為T(n)/n=O(1)。

對(duì)于給定的初始數(shù)據(jù)結(jié)構(gòu)，任意一個(gè)關(guān)于該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算序列，會(huì)計(jì)方法記錄運(yùn)算序列中每個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)與實(shí)際代價(jià)之差的總和，這個(gè)量任何時(shí)刻都不能為負(fù)值。會(huì)計(jì)方法將分?jǐn)偞鷥r(jià)超過(guò)實(shí)際代價(jià)的余額用于填補(bǔ)分?jǐn)偞鷥r(jià)小于實(shí)際代價(jià)的運(yùn)算，但總的累計(jì)余額始終不能為負(fù)值。

2.4.3 勢(shì)能方法

給定一個(gè)初始數(shù)據(jù)結(jié)構(gòu)，執(zhí)行該數(shù)據(jù)結(jié)構(gòu)上的一個(gè)運(yùn)算將使該數(shù)據(jù)結(jié)構(gòu)改變狀態(tài)。勢(shì)能方法（potential method）為數(shù)據(jù)結(jié)構(gòu)的每個(gè)狀態(tài)定義一個(gè)被稱(chēng)為勢(shì)能的量。設(shè)數(shù)據(jù)結(jié)構(gòu)的初始狀態(tài)為D0。對(duì)D0執(zhí)行一個(gè)n次運(yùn)算的序列，ci是第i個(gè)運(yùn)算的實(shí)際代價(jià)，Di為在數(shù)據(jù)結(jié)構(gòu)的狀態(tài)Di-1時(shí)執(zhí)行第i個(gè)運(yùn)算后得到的數(shù)據(jù)結(jié)構(gòu)的新?tīng)顟B(tài)。勢(shì)能函數(shù)Φ將數(shù)據(jù)結(jié)構(gòu)的每個(gè)狀態(tài)映射為一個(gè)實(shí)數(shù)Φ(Di)，稱(chēng)為數(shù)據(jù)結(jié)構(gòu)在該狀態(tài)下的勢(shì)能。第i個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)定義為：

從上式可知，每個(gè)運(yùn)算的分?jǐn)偞鷥r(jià)是其實(shí)際代價(jià)ci加上執(zhí)行該運(yùn)算引起的數(shù)據(jù)結(jié)構(gòu)勢(shì)能的增量Φ(Di)-Φ(Di-1)。那么，n個(gè)運(yùn)算的總分?jǐn)偞鷥r(jià)是：

如果能夠定義一個(gè)勢(shì)能函數(shù)Φ，使得Φ(Dn)≥Φ(D0)，則可知總的分?jǐn)偞鷥r(jià)是總實(shí)際代價(jià)的上界。

式（2-10）定義的分?jǐn)偞鷥r(jià)依賴(lài)于勢(shì)能函數(shù)，不同的勢(shì)能函數(shù)可能會(huì)產(chǎn)生不同的分?jǐn)偞鷥r(jià)，并使得運(yùn)算序列的總的分?jǐn)偞鷥r(jià)不同，但它們都是總實(shí)際代價(jià)的上界。

例2-22 使用勢(shì)能方法分析例2-20的棧運(yùn)算

可將棧數(shù)據(jù)結(jié)構(gòu)的勢(shì)能定義為棧中元素個(gè)數(shù)。初始時(shí)，棧為空棧D0，且Φ(D0)=0。由于棧中元素個(gè)數(shù)始終是非負(fù)的，故在第i個(gè)運(yùn)算執(zhí)行后，Di總有非負(fù)的勢(shì)能，即Φ(Di)≥0。

現(xiàn)在來(lái)計(jì)算各棧運(yùn)算的分?jǐn)偞鷥r(jià)。

（1）對(duì)于Push運(yùn)算，棧中元素個(gè)數(shù)加1，即數(shù)據(jù)結(jié)構(gòu)的勢(shì)能加1，其分?jǐn)偞鷥r(jià)為：

（2）對(duì)于MultiPop(s, k)運(yùn)算，該運(yùn)算將彈出k'=min(k, m)個(gè)元素，m是當(dāng)前棧中元素的個(gè)數(shù)，勢(shì)能差Φ(Di)-Φ(Di-1)=-k'。由于實(shí)際彈出k'個(gè)元素，故該運(yùn)算的實(shí)際代價(jià)也是k'，于是，MultiPop運(yùn)算的分?jǐn)偞鷥r(jià)為：

（3）對(duì)于Pop運(yùn)算，其勢(shì)能差為-1，分?jǐn)偞鷥r(jià)為：

由此可見(jiàn)，三個(gè)棧運(yùn)算的分?jǐn)偞鷥r(jià)均為O(1)，n個(gè)運(yùn)算的總分?jǐn)偞鷥r(jià)就是O(n)。并且因?yàn)棣?Dn)≥Φ(D0)=0，因此總的分?jǐn)偞鷥r(jià)是實(shí)際代價(jià)的上界，n個(gè)棧運(yùn)算的最壞情況分?jǐn)偞鷥r(jià)為T(n)=O(n)，每個(gè)棧運(yùn)算的平均時(shí)間為T(n)/n=O(1)。

本章小結(jié)

本章重點(diǎn)介紹算法分析的基本方法。算法的時(shí)間和空間效率是衡量一個(gè)算法性能的重要標(biāo)準(zhǔn)，對(duì)于算法的性能分析可以采用事前分析和事后測(cè)量形式進(jìn)行。算法分析通常是指使用漸近表示法對(duì)一個(gè)算法的時(shí)間和空間需求做事前分析。算法復(fù)雜度的漸近表示法用于在數(shù)量級(jí)上估算一個(gè)算法的時(shí)空資源耗費(fèi)。算法的運(yùn)行時(shí)間可使用程序步來(lái)衡量。一個(gè)算法可以討論其最好、平均和最壞情況時(shí)間復(fù)雜度，其中，最壞情況分析最有實(shí)際價(jià)值。算法的空間復(fù)雜度一般只做最壞情況分析。

遞歸算法是一類(lèi)重要的算法結(jié)構(gòu)，也是較難掌握的一種算法技術(shù)。在第1章基礎(chǔ)上，本章討論使用遞推關(guān)系分析遞歸算法的方法及求解遞推式的3種途徑。最后討論算法時(shí)間分析的分?jǐn)偡椒ā?/p>

習(xí)題2

2-1 簡(jiǎn)述衡量一個(gè)算法的主要性能標(biāo)準(zhǔn)。說(shuō)明算法的正確性和健壯性的關(guān)系。

2-2 什么是算法的最優(yōu)性？

2-3 簡(jiǎn)述影響一個(gè)程序運(yùn)行時(shí)間的因素。

2-4 什么是算法的時(shí)間復(fù)雜度和空間復(fù)雜度？什么是最好、平均和最壞情況時(shí)間復(fù)雜度？

2-5 什么是算法的事前分析，什么是事后測(cè)試？

2-6 什么是程序步？引入程序步概念對(duì)算法的時(shí)間分析有何意義？

2-7 什么是多項(xiàng)式時(shí)間算法？什么是指數(shù)時(shí)間算法？

2-8 確定下列各程序段的程序步，確定畫(huà)線(xiàn)語(yǔ)句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。

（1）i=1; x=0;

do{
x++; i=2*i;
} while i<n;

（2）for(int i=1; i<=n; i++)

       for(int j=1; j<=i; j++)
          for (int k=1; k<=j; k++) x++;

（3）x=n; y=0;

     while(x>=(y+1)*(y+1)) y++;

（4）m=0;

     for（int i=0; i<n; i++）
        for(int j=2*i; j<=n; j++) m++;

2-9 矩陣轉(zhuǎn)置

（1）設(shè)計(jì)一個(gè)C/C++程序?qū)崿F(xiàn)一個(gè)n×m的矩陣轉(zhuǎn)置。原矩陣及其轉(zhuǎn)置矩陣保存在二維數(shù)組中。

（2）使用全局變量count（類(lèi)似程序2-1的做法），改寫(xiě)矩陣轉(zhuǎn)置程序，并運(yùn)行修改后的程序以確定此程序所需的程序步。

（3）計(jì)算此程序的漸近時(shí)間復(fù)雜度。

2-10 試用定義證明下列等式的正確性。

（1）5n2-8n+2=O(n2)

（2）5n2-8n+2=Ω(n2)

（3）5n2-8n+2=Θ(n2)

2-11 設(shè)有f(n)和g(n)如下所示，分析f(n)為O(g(n))、Ω(g(n))還是Θ(g(n))。

（1）f(n)=20n+logn，g(n)=n+log3n

（2）f(n)=n2/logn，g(n)=nlog2n

（3）f(n)=(logn)logn，g(n)=n/logn

（4）f(n)=，g(n)=log5n

（5）f(n)=n2n，g(n)=3n

2-12 將下列時(shí)間函數(shù)按增長(zhǎng)率的非遞減次序排列：

(3/2)n，，log2n，nlogn，n！，log(logn), 2n，n1/logn，n2

2-13 設(shè)f1(n)=O(g1(n))，f2(n)=O(g2(n))，證明下列結(jié)論成立。

（1）f1(n)+f2(n)=O(max{g1(n)，g2(n)})

（2）f1(n)+f2(n)=O(g1(n)-g2(n))

2-14 證明：若f(n)=amnm+am-1nm-1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=Ω(nm)。

2-15 證明：若p(n)是n的多項(xiàng)式，則O(log(p(n))=O(logn)。

2-16 使用遞推關(guān)系式計(jì)算求n！的遞歸函數(shù)的時(shí)間，要求使用替換和迭代兩種方法分別計(jì)算之。

2-17 設(shè)T(n)由如下遞推式定義，證明T(n)=O(nlog2(n))。

2-18 假定n是2的冪，T(n)由如下遞推式定義，計(jì)算T(n)的漸近上界。

2-19 利用遞歸樹(shù)計(jì)算遞推方程T(n)=2T(n/2)+n2，T(1)=2。

2-20 使用下列數(shù)據(jù)計(jì)算主定理的遞推式：

（1）a=1, b=2, f(n)=cn

（2）a=5, b=4, f(n)=cn2

（3）a=28, b=3, f(n)=cn3

2-21 運(yùn)用主定理計(jì)算T(n)=2T(n/4) +, T(1)=3的漸近界。

2-22 設(shè)對(duì)某一數(shù)據(jù)結(jié)構(gòu)執(zhí)行包括n個(gè)運(yùn)算的運(yùn)算序列。若i是2的整數(shù)冪，則第i次運(yùn)算的代價(jià)為i，否則為1。請(qǐng)使用聚集方法確定每次運(yùn)算的代價(jià)。

2-23 利用會(huì)計(jì)方法重做上一題。

2-24 設(shè)有一個(gè)大小為k的棧，每執(zhí)行k次運(yùn)算后總要執(zhí)行一次復(fù)制運(yùn)算，將整個(gè)棧的內(nèi)容復(fù)制保存。證明：對(duì)每種棧運(yùn)算賦予適當(dāng)?shù)姆謹(jǐn)偞鷥r(jià)后，n個(gè)棧運(yùn)算（含復(fù)制棧運(yùn)算）的代價(jià)為O(n)。

2-25 用勢(shì)能方法重做習(xí)題2-22。

2-26 假設(shè)一個(gè)棧在執(zhí)行n次棧運(yùn)算Push、Pop和MultiPop之前有s0個(gè)元素，執(zhí)行運(yùn)算序列后有sn個(gè)元素，則n個(gè)棧運(yùn)算的總代價(jià)是多少？

2-27 說(shuō)明如何用一個(gè)普通棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，使得每個(gè)Append（入隊(duì)列）和Serve（出隊(duì)列）運(yùn)算的分?jǐn)偞鷥r(jià)均為O(1)。