第2章 算法分析基礎

一旦確信一個算法是正確的，下一個重要的步驟就是分析算法。算法分析是指對算法利用時間和空間這兩種資源的效率進行研究。本章討論衡量算法效率的時間復雜度和空間復雜度，算法的最好、平均和最壞情況時間復雜度，討論用于算法分析的漸近表示法，介紹如何使用遞推關系來分析遞歸算法的方法及分攤分析技術。

2.1 算法復雜度

同一個問題可以編寫多個算法來求解，這些算法所消耗的計算機資源（計算時間和存儲空間）多少不同。算法的復雜度是指運行一個算法所需的時間和空間資源的量。

2.1.1 什么是好的算法

人們總是希望算法具有許多良好的特性。一個好的算法應具有以下4個重要特性。

（1）正確性（correctness）：毫無疑問，算法的執行結果應當滿足預先規定的功能和性能要求。

（2）簡明性（simplicity）：算法應思路清晰、層次分明、容易理解、利于編碼和調試。

（3）效率（efficiency）：算法應有效使用存儲空間，并具有高的時間效率。

（4）最優性（optimality）：算法的執行時間已達到求解該類問題所需時間的下界。

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

注意，本書假定算法的輸入都是合法輸入，而不進行輸入檢測，但在算法的實際應用中，應當對輸入數據實施必要的檢測來保證程序的健壯性。

算法的簡明性要求算法的邏輯清晰，簡單明了，并且是結構化的，從而使算法易于閱讀和理解，并易于編碼和調試。算法的簡明性沒有嚴格定義的尺度可以度量，在很大程度上取決于審視者的眼光。但簡明性并不是可有可無的特性，它是算法設計者需努力爭取的一個重要特性，因為簡單的算法往往更容易理解和實現，相應的程序也會因此而減少錯誤（bug）。此外，一個簡單明了的算法就像一篇優美的說明文，令閱讀者賞心悅目。但遺憾的是，簡單的算法并不一定是高效的。

算法的效率是指執行一個算法所需的計算時間和存儲空間。當程序規模較大時，算法的效率問題是算法設計必須面對的一個關鍵問題。必須重視算法的效率分析。然而為了換取一定的效率，犧牲算法的可讀性，在現代程序設計中并不是明智之舉。因此，算法設計者往往需要在算法的簡明性和效率之間做出謹慎的選擇。折中和結論（tradeoffs and consequences）是計算機學科的重要概念之一。

算法的最優性與所求解的問題自身的復雜程度有關。例如，對于在n個元素的集合中尋找一個最大元素的問題，分析表明，任何通過元素之間比較的方式來求解此問題的正確算法，至少需要進行n-1次元素間的比較運算。如果某人編寫一個算法，聲稱他的算法對任意一個有n個元素的集合，僅需執行n-2次元素比較便可求得集合中的最大元素，那么，可以肯定，該算法不可能是正確的。如果一個實際的正確算法，在最壞情況下的確只需n-1次元素比較便可求得最大元素，那么它可稱為最優的。因為n-1次元素比較是求最大元問題所需時間的下界。本書將討論排序和查找問題的時間下界。然而遺憾的是，許多看似簡單的問題，至今仍無法知曉求解該問題所需的時間下界是多少，如：矩陣乘法。

2.1.2 影響程序運行時間的因素

一個程序的運行時間是程序運行從開始到結束所需的時間。影響程序運行時間的因素主要有：

（1）程序所依賴的算法；

（2）問題規模和輸入數據；

（3）計算機系統性能。

首先，很容易想到，對于同一程序和相同的輸入數據，如果在不同的計算機上運行該程序，所需的運行時間幾乎可以肯定是不同的。這是因為計算機的硬件性能可能不同，特別是處理器（CPU）速度可能相差很多。程序設計語言及其編譯器不同，生成的目標代碼的效率也會各異。操作系統也是影響計算機系統性能的因素之一。這就是說，算法運行所需的時間依賴于計算機軟、硬件系統。

如果排除計算機的因素，假定在完全相同的計算機環境下運行程序，情況又如何呢？

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

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

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

如果在同一個計算機系統上運行同一個程序，問題實例的規模也相同，則運行時間是否就一定相同呢？一個熟悉的例子是使用冒泡排序算法分別對100個已從小到大有序的整數排序，以及對隨機選擇的100個整數進行排序，它們所需的排序時間通常是不同的。這就是說，問題的規模相同，輸入數據的狀態（如排列次序）不同，所需的時間開銷也會不同。

2.1.3 算法的時間復雜度

1.抽象機模型

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

2.時間復雜度

一個算法的時間復雜度（time complexity）是指算法運行所需的時間。

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

這就是算法的時間復雜度。式中，輸入數據I代表問題的一個實例，n是問題的規模。

3.最好、最壞和平均時間復雜度

前面提到，對于許多算法，即使問題的規模相同，如果輸入數據I不同，算法所需的時間開銷也會不同。

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

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

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

還有一種類型的時間效率稱為分攤效率。它并不針對算法的單次運行，而是計算算法在同一數據結構上執行一系列運算的平均時間。也許單次運算的時間代價較高，但n次運算的總運行時間除以n的平均時間效率并不差，這就是分攤效率。關于分攤效率將在稍后做深入討論。

2.1.4 使用程序步分析算法

從上面討論可知，程序運行時間不僅與算法的優劣和輸入數據直接相關，還與運行程序的計算機軟、硬件環境有關。為了分析算法的效率，總希望略去計算機系統因素，對算法自身的特性進行事前分析（priori analysis），即在算法實際運行前分析算法的效率。這種分析結果顯然不可能是程序運行時間的具體值，而是運行時間的一種事前估計。算法的事后測試（posteriori testing）是通過運行程序，測試一個程序在所選擇的輸入數據下實際運行所需要的時間。

前面關于算法時間復雜度的概念是在抽象機模型上定義的。對于用程序設計語言書寫的算法，應如何分析其時間復雜度呢？可以設想，如果我們將程序設計語言中的循環語句的執行過程，視為其循環體（其中不嵌套循環）的重復執行過程，并對每次函數調用單獨計算它的時間。那么，就可將抽象機模型上定義的概念用于分析由具體程序設計語言描述的算法。對于用C/C++語言描述的算法，可將每種可執行語句（除循環語句外）看成一種基本運算；對于循環語句，需計算其循環體的執行次數。這就可以通過一個算法在給定輸入下所執行的總的語句條數來計算算法的時間復雜度。下面定義的程序步概念可進一步簡化算法分析。它并不直接計算總的語句執行條數，而是將若干條語句合并成一個程序步來計算。

一個程序步（program step）是指在語法上或語義上有意義的程序段，該程序段的執行時間必須與問題實例的規模無關。

現以程序2-1求數組元素之和為例來說明如何計算一個算法的程序步數。設n個元素存放在一維數組list中，count是全局變量，用來計算總的程序步數。在程序中，語句count++;與數組求和的算法無關，只是為了計算程序步數而添加的。忽略所有count++;語句，便是一個數組求和程序。可以看到，這里被計算的每一程序步的執行時間，均與問題實例的規模n（數組元素的個數）無關。該程序的總程序步數為2n+3。

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

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

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

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

這是一個遞推關系式，它可以通過轉換成如下和式來計算：

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

=2×3+T(n-3)

…

=2×n+T(0)

=2×n+2

雖然從表面看來，程序RSum所需的程序步為2n+2，少于程序Sum的程序步2n+3，但這并不意味著前者比后者快，這是因為兩者使用的程序步是不同的。遞歸調用引起的循環計算和使用for語句的循環計算所需的開銷是不同的，遞歸需要耗費更多的時間和空間資源。有關遞歸算法及其分析方法將在本章稍后及以后章節中做進一步討論。

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

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

2.1.5 算法的空間復雜度

一個算法的空間復雜度（space complexity）是指算法運行所需的存儲空間。程序運行所需的存儲空間包括以下兩部分。

（1）固定空間需求（fixed space requirement）：這部分空間與所處理數據的大小和個數無關，也就是說，與問題實例的特征無關，主要包括程序代碼、常量、簡單變量、定長成分的結構變量所占的空間。

（2）可變空間需求（variable space requirement）：這部分空間大小與算法在某次執行中處理的特定數據的規模有關。例如，分別包含100個元素的兩個數組相加，與分別包含10個元素的兩個數組相加，所需的存儲空間顯然是不同的。這部分存儲空間包括數據元素所占的空間，以及算法執行所需的額外空間，例如，運行遞歸算法所需的系統棧空間。

對算法空間復雜度的討論類似于時間復雜度，并且一般來說，空間復雜度的計算比起時間復雜度的計算容易。此外，應當注意的是，空間復雜度一般按最壞情況來分析。

2.2 漸近表示法

引入程序步的目的在于簡化算法的事前分析。正如前面已經討論過的，不同的程序步在計算機上的實際執行時間通常是不同的，程序步數并不能確切反映程序運行的實際時間。而且事實上，一個程序在一次執行中的總程序步的精確計算往往也是困難的。那么，引入程序步的意義何在？本節中定義的漸近時間復雜度，使得有望使用程序步在數量級上估計一個算法的執行時間，從而實現算法的事前分析。

2.2.1 大O記號

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

大O記號可以看成n的函數的集合。O(g(n))表示所有增長階數不超過g(n)的函數的集合，它用以表達一個算法運行時間的上界。稱一個算法具有O(g(n))的運行時間，是指當n足夠大時，該算法在計算機上的實際運行時間不會超過g(n)的某個常數倍，g(n)是它的一個上界。

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

當n≥3時，2n+3≤3n，所以，可選c=3，n0=3。對于n≥n0，f(n)=2n+3≤3n，所以，f(n)=O(n)，即2n+3∈O(n)。這意味著，當n≥3時，程序2-1的程序步不會超過3n，2n+3=O(n)。

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

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

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

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

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

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

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

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

證明：取n0=1，當n≥n0時，有

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

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

使用大O記號及下面定義的幾種漸近表示法表示的算法時間復雜度，稱為算法的漸近時間復雜度（asymptotic complexity）。漸近時間復雜度也常簡稱為時間復雜度。記號O(1)用于表示常數計算時間，它代表算法只需執行有限個程序步。

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

只要適當選擇關鍵操作，算法的漸近時間復雜度可以由關鍵操作的執行次數之和來計算。一般，關鍵操作的執行次數與問題的規模有關，是n的函數。在很多情況下，它是算法中執行次數最多的操作（程序步）。關鍵操作通常是位于算法最內層循環的程序步（或語句）。

程序2-3是實現兩個n×n矩陣相乘的程序段，每行最右邊注明該行語句執行的次數，即作為程序步看待。對于循環語句for (i=0; i<n; i++) {y;}，可以認為循環體y執行n次，而for自身執行n+1次比較運算（i＜n）。因此，程序中所有語句的執行次數為T(n)=2n3+3n2+2n+1。由定理2-1可知，程序2-3的漸近時間復雜度為O(n3)。如果將語句c[i][j]+=a[i][k]*b[k][j];看成關鍵操作，它的執行次數是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
     }

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

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

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

2.2.2 W記號

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

Ω記號可以看成n的函數的集合。Ω(g(n))表示所有增長階數不低于g(n)的函數的集合，它用于表示一個算法運行時間的下界。稱一個算法具有Ω(g(n))的運行時間，是指當n足夠大時，該算法在計算機上運行，至少需要g(n)的某個常數倍大小的時間量。

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

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

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

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

與大O記號類似，對于給定f，可有無數個g與之對應。例如，f=10n2+4n+2，g可以是n2，n1，n1/2，…。應當選擇最接近的函數g，即f的最大下界。

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

證明留做練習。

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

2.2.3 Θ記號

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

Θ記號可以看成n的函數的集合。Θ(g(n))表示所有增長階數與g(n)相同的函數的集合，它用于表示一個算法運行時間具有與g(n)相同的階。稱一個算法具有Θ(g(n))的運行時間，是指當n足夠大時，該算法在計算機上的實際運行時間大約為g(n)某個常數倍大小的時間量。從上兩節討論可知，下面例2-7和例2-8的結論成立。

例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次多項式，且am＞0，則f(n)=Θ(nm)。

證明留做練習。

2.2.4 小o記號

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

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

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

2.2.5 算法按時間復雜度分類

算法可以按計算時間分成兩類：凡漸近時間復雜度為多項式時間限界的算法稱做多項式時間算法（polynomial time algorithm），而漸近時間復雜度為指數函數限界的算法稱做指數時間算法（exponential time algorithm）。

最常見的多項式時間算法的漸近時間復雜度之間的關系為：

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

最常見的指數時間算法的漸近時間復雜度之間的關系為：

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

隨著n的增大，指數時間算法和多項式時間算法在所需的時間上非常懸殊。表2-1和圖2-1顯示了幾種典型的時間函數隨問題規模增長的情況。

表2-1 時間復雜度函數增長情況

從圖2-1中可以看到，O(log n)、O(n)和O(nlog n)的增長比較平穩，指數函數2n的曲線非常陡。實際情況是，對大的n值，在目前一般計算機上，運行一個復雜度高于O(nlog n)的算法已經很困難了。對于指數時間算法，只有當n很小時才有實用價值。

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

對算法進行時間分析，是為了盡可能降低算法時間復雜度的數量級。上述討論表明，為了提高程序運行速度，選擇一種更快的算法比換一臺更快的機器奏效。

2.3 遞推關系

2.3.1 遞推方程

遞推關系經常用來分析遞歸算法的時間和空間代價。分析一個遞歸算法的時間一般需要列出關于時間復雜度函數的遞推關系式。

遞推方程（recurrence equation）是自然數上一個函數T(n)，它使用一個或多個小于n時的值的等式或不等式來描述。遞推方程也稱為遞推關系或遞推式。第2.1.4節中的式（2-5）就是對于程序2-2的時間分析的遞推方程。

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

例2-10 程序1-5的時間分析

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

可以采用與式（2-5）相同的方法，將其轉換成和式來計算。這種方法稱為迭代方法。從式（2-5）可知式（2-6）的計算結果是：

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

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

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

一般來說，問題的規模是非負整數，而且對足夠小的問題，算法的運行時間可視為常量，所以，在以后討論中，當描述遞推式時，如果沒有明確指明，則都假定n是非負整數，并假定對足夠小的n值，T(n)是常量。

2.3.2 替換方法

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

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

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

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

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

證明：（歸納法證明）

當n=1時，T(1)=1，結論成立。歸納法假設：當k＜n時，有T(k)=2k-1，那么，當k=n時，T(n)=2T(n-1)+1=2(2n-1-1)+1=2n-1。因此，對所有n≥1，T(n)=2n-1=Θ(2n)。

2.3.3 迭代方法

迭代方法的思想是擴展遞推式，將遞推式先轉換成一個和式，然后計算該和式，得到漸近復雜度。它需要較多的數學運算。

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

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

擴展并計算此遞推式：

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

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

使用遞歸樹（recursion tree）可以形象地看到遞推式的迭代過程。下面舉例說明對給定的遞推方程，通過構造遞歸樹來求解的方法。

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

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

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

例2-14給出了另一個更復雜的例子，圖2-3是其對應的遞歸樹。從根到葉的最長的一條路徑是n→(2/3)n→(2/3)2n→…→1。因為(2/3)kn=1，k=log3/2n，該樹的高度（層數）為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是常數，f(n)是一個漸近正函數，n/b指或。

求解這類遞推式的方法稱為主方法。主方法依賴于下面的主定理，使用主定理可直接得到遞推式的解。關于主定理的證明見文獻[2]。

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

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

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

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

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

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

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

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

因為a=16, b=4,=n2, f(n)=n=O()=O)，其中，=1與主定理的情況（1）相符合，T(n)=Θ()=Θ(n2)。

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

因為a=1, b=7/3,==n0=1, f(n)=1=Θ()，所以，符合主定理情況（2），T(n)=Θ(logn)=Θ(logn)。

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

因為a=3, b=4,，其中，≈0.2。由于對足夠大的n，3(n/4)log(n/4)≤(3/4)nlogn，這里c=3/4，符合主定理情況（3）。T(n)=Θ(f(n))=Θ(nlogn)。

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

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

由于a=2, b=2, f(n)=nlogn和=n。看起來似乎屬于主定理情況（3），但事實上不是。因為f(n)只是漸近大于n，但并不是多項式大于n。f(n)與的比值是log n，對于任何正數，log n漸近小于，所以，此例不能運用主定理。

2.4 分攤分析

在很多情況下，對一個數據結構的操作往往不是單獨執行一次運算，而是重復多次執行多個運算，形成一個運算執行序列。如果執行n個運算的總時間為T(n)，則每個運算的平均代價（average cost）為T(n)/n，分攤分析的目的是求平均代價。

分攤分析（amortized analysis）是對一個長的運算序列所需的最壞情況時間求平均值。設在最壞情況下，對所有n，執行一個長度為n的運算序列所需的最壞情況時間為T(n)，那么，每個運算平均代價為T(n)/n。

分攤分析和平均情況分析的不同之處在于它不需要假定每個運算的概率，因而不涉及概率。分攤分析保證在最壞情況下一個運算序列中每個運算的平均性能。

分攤分析一般有三種方法：聚集方法、會計方法和勢能方法。

2.4.1 聚集方法

聚集方法（aggregate analysis）中需要對所有n，計算由n個運算構成的運算序列在最壞情況下總的執行時間T(n)，則每個運算的平均代價為T(n)/n。請注意，序列中允許包含不同種類的運算，但每個運算的分攤代價是相同的。

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

例2-20 設在上例的棧數據結構上定義一個新運算void MultiPop(int k)，該運算從棧中連續彈出k個元素。

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

事實上，從初始空棧開始，任意一個包含n個Push、Pop和MultiPop運算的執行序列總的程序步至多是n步。這是很顯然的，因為每壓入一個元素，至多可彈出一個元素。在一個非空棧上執行Pop和MultiPop時，被彈出的元素總數不超過Push的執行次數。因此，對任意n，一個包含n個棧運算的序列的總執行時間為O(n)，因而每個運算的平均代價為O(n)/n=O(1)。

2.4.2 會計方法

對于給定的數據結構，會計方法（accounting method）對每個運算預先賦予不同的費值（charge）。其中，某些運算的費值可能超過它們的實際代價（actual cost），而另一些運算的費值會低于實際代價。對每個運算所記的費值稱為分攤代價（amortized cost）。其超出部分如同存款（credit）一樣保存起來，用于補償以后代價不足的運算。與聚集分析不同的是，會計方法的分攤代價可以不同，而聚集分析中每個運算有相同的分攤代價。

使用會計方法，首先按預先分配給每個運算的分攤代價，計算一個運算序列的總的分攤代價。如果能夠保證對所有n，任意一個運算序列的總分攤代價不會低于該運算序列的實際代價T(n)，即運算序列的總的分攤代價是總的實際代價的上界，設總分攤代價為O(g(n))，則T(n)=O(g(n))。

這就要求在一個運算序列執行的任何時刻，總分攤代價始終不低于該時刻的實際代價。如果在一個運算序列的執行中，隨時記錄下迄今為止的累計分攤代價減去實際代價的余額，則這一累計余額始終應當是非負的。如果在執行某個運算后，代價余額出現負值，則說明迄今為止的分攤代價低于當時消費的實際代價，這種情形表示這樣計算的總分攤代價將不能作為總的實際代價的上界來計算每個運算的平均代價。請注意區分分攤代價和平均代價。

例2-21 使用會計方法分析例2-20的棧運算

會計分析首先需要精心分配每個運算的分攤代價，代價用程序步度量。表2-2列出各個棧運算的實際代價和分攤代價，其中，Min(k, m)中的k是運算MultiPop的參數，m是執行此運算時，棧中元素的個數。

表2-2 棧運算的實際代價和分攤代價

在表2-2中，對Push預分配的分攤代價為2，顯然超過了此運算的實際代價，而對Pop和MultiPop分配的分攤代價都為0，低于實際代價，但事實上，MultiPop的實際代價是隨參數k變化的。通過仔細分析可知，表2-2的分攤代價分配方式是可行的，因為它可以保證在執行一個運算序列的任何時刻，其代價余額不會為負值。理由是：每執行一次Push有一個程序步的節余，可用于支付一次Pop運算或MultiPop運算的一步（彈出一個元素）。由于必須執行一次Push，才有可能執行一次Pop或MultiPop的一步，因此，關于堆棧操作的總代價余額不會為負值。這樣，總分攤代價O(n)必定是總實際代價的上界，T(n)=O(n)，每個運算的平均代價為T(n)/n=O(1)。

對于給定的初始數據結構，任意一個關于該數據結構的運算序列，會計方法記錄運算序列中每個運算的分攤代價與實際代價之差的總和，這個量任何時刻都不能為負值。會計方法將分攤代價超過實際代價的余額用于填補分攤代價小于實際代價的運算，但總的累計余額始終不能為負值。

2.4.3 勢能方法

給定一個初始數據結構，執行該數據結構上的一個運算將使該數據結構改變狀態。勢能方法（potential method）為數據結構的每個狀態定義一個被稱為勢能的量。設數據結構的初始狀態為D0。對D0執行一個n次運算的序列，ci是第i個運算的實際代價，Di為在數據結構的狀態Di-1時執行第i個運算后得到的數據結構的新狀態。勢能函數Φ將數據結構的每個狀態映射為一個實數Φ(Di)，稱為數據結構在該狀態下的勢能。第i個運算的分攤代價定義為：

從上式可知，每個運算的分攤代價是其實際代價ci加上執行該運算引起的數據結構勢能的增量Φ(Di)-Φ(Di-1)。那么，n個運算的總分攤代價是：

如果能夠定義一個勢能函數Φ，使得Φ(Dn)≥Φ(D0)，則可知總的分攤代價是總實際代價的上界。

式（2-10）定義的分攤代價依賴于勢能函數，不同的勢能函數可能會產生不同的分攤代價，并使得運算序列的總的分攤代價不同，但它們都是總實際代價的上界。

例2-22 使用勢能方法分析例2-20的棧運算

可將棧數據結構的勢能定義為棧中元素個數。初始時，棧為空棧D0，且Φ(D0)=0。由于棧中元素個數始終是非負的，故在第i個運算執行后，Di總有非負的勢能，即Φ(Di)≥0。

現在來計算各棧運算的分攤代價。

（1）對于Push運算，棧中元素個數加1，即數據結構的勢能加1，其分攤代價為：

（2）對于MultiPop(s, k)運算，該運算將彈出k'=min(k, m)個元素，m是當前棧中元素的個數，勢能差Φ(Di)-Φ(Di-1)=-k'。由于實際彈出k'個元素，故該運算的實際代價也是k'，于是，MultiPop運算的分攤代價為：

（3）對于Pop運算，其勢能差為-1，分攤代價為：

由此可見，三個棧運算的分攤代價均為O(1)，n個運算的總分攤代價就是O(n)。并且因為Φ(Dn)≥Φ(D0)=0，因此總的分攤代價是實際代價的上界，n個棧運算的最壞情況分攤代價為T(n)=O(n)，每個棧運算的平均時間為T(n)/n=O(1)。

本章小結

本章重點介紹算法分析的基本方法。算法的時間和空間效率是衡量一個算法性能的重要標準，對于算法的性能分析可以采用事前分析和事后測量形式進行。算法分析通常是指使用漸近表示法對一個算法的時間和空間需求做事前分析。算法復雜度的漸近表示法用于在數量級上估算一個算法的時空資源耗費。算法的運行時間可使用程序步來衡量。一個算法可以討論其最好、平均和最壞情況時間復雜度，其中，最壞情況分析最有實際價值。算法的空間復雜度一般只做最壞情況分析。

遞歸算法是一類重要的算法結構，也是較難掌握的一種算法技術。在第1章基礎上，本章討論使用遞推關系分析遞歸算法的方法及求解遞推式的3種途徑。最后討論算法時間分析的分攤方法。

習題2

2-1 簡述衡量一個算法的主要性能標準。說明算法的正確性和健壯性的關系。

2-2 什么是算法的最優性？

2-3 簡述影響一個程序運行時間的因素。

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

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

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

2-7 什么是多項式時間算法？什么是指數時間算法？

2-8 確定下列各程序段的程序步，確定畫線語句的執行次數，計算它們的漸近時間復雜度。

（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 矩陣轉置

（1）設計一個C/C++程序實現一個n×m的矩陣轉置。原矩陣及其轉置矩陣保存在二維數組中。

（2）使用全局變量count（類似程序2-1的做法），改寫矩陣轉置程序，并運行修改后的程序以確定此程序所需的程序步。

（3）計算此程序的漸近時間復雜度。

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

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

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

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

2-11 設有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 將下列時間函數按增長率的非遞減次序排列：

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

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

（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次多項式，且am＞0，則f(n)=Ω(nm)。

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

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

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

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

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

2-20 使用下列數據計算主定理的遞推式：

（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 運用主定理計算T(n)=2T(n/4) +, T(1)=3的漸近界。

2-22 設對某一數據結構執行包括n個運算的運算序列。若i是2的整數冪，則第i次運算的代價為i，否則為1。請使用聚集方法確定每次運算的代價。

2-23 利用會計方法重做上一題。

2-24 設有一個大小為k的棧，每執行k次運算后總要執行一次復制運算，將整個棧的內容復制保存。證明：對每種棧運算賦予適當的分攤代價后，n個棧運算（含復制棧運算）的代價為O(n)。

2-25 用勢能方法重做習題2-22。

2-26 假設一個棧在執行n次棧運算Push、Pop和MultiPop之前有s0個元素，執行運算序列后有sn個元素，則n個棧運算的總代價是多少？

2-27 說明如何用一個普通棧來實現一個隊列，使得每個Append（入隊列）和Serve（出隊列）運算的分攤代價均為O(1)。