1.3 算法的復雜性分析

一個問題如果采用了合適的算法，其解決問題的速度將會大大提高。那么評價一個算法的好壞，主要看執行算法時需要花費的計算機CPU時間的多少和需要占用的計算機存儲空間的大小。因此，算法的分析就是對其時間效率和空間效率兩個方面進行比較。

這里討論衡量算法效率的時間復雜度和空間復雜度。

1.3.1 算法評價的基本原則

算法的優劣是經過分析后得出的結果，而為判斷算法的效率對其進行的分析即算法分析。但是效率分析并不是算法分析的唯一目的，雖然算法追求的目標是速度，但算法必須首先正確才有存在的意義。

不過，正確性和時間分析并不是算法分析的唯一任務，如果兩個算法的時間效率是一樣的，就要對算法實現的空間進行比較，空間使用較少的為優。在某些情況下，兩個算法的時間、空間效率都有可能相同或相似，這時就要分析算法的其他屬性，如穩定性、健壯性、實現難度等，并以此來判斷到底應該選擇哪一個算法。通常一個好的算法應該考慮達到以下目標。

1. 正確性

一個好的算法的前提就是算法的正確性（Correctness）。不正確的算法沒有任何意義。

在給定有效輸入后，算法經過有限時間的計算，執行結果滿足預先規定的功能和性能要求，答案正確，就稱算法是正確的。算法應當滿足具體問題的需求，否則，算法的正確與否的衡量準則就不存在了。

“正確”一詞的含義在通常用法上有很大差別，大體可分為四層。

（1）程序不含語法錯誤。

（2）程序對幾組輸入數據能夠得出滿足規格說明要求的結果。

（3）程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據能夠得出滿足規格說明要求的結果。

（4）程序對于一切合法的輸入數據都能產生滿足規格說明要求的結果。

達到第4層意義上的正確是極為困難的，所有不同輸入數據的數據量大得驚人，逐一驗證是不現實的，在實際上，通常以第3層意義下的正確作為一個程序是否合格的標準。

對于大型程序，可以將它分解為小的相互獨立的模塊，分別進行驗證。而小模塊程序則可以使用數學歸納法、軟件形式方法等加以驗證。

2. 可讀性（Readability）

算法主要是為了方便用戶的閱讀與交流，其次才是機器的執行。因此，算法應該易于理解、調試和修改，可讀性好則有助于用戶對算法的理解。

3. 健壯性和可靠性

健壯性（Robustness）是指當輸入數據非法時，算法也能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。即當程序遇到意外時，能按某種預定方式做出適當處理。例如，求一個凸多邊形面積的算法，是采用求各三角形面積之和的策略來解決問題的。當輸入的坐標集合表示的是一個凹多邊形時，不應繼續計算，而應報告輸入錯誤，并且返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。

正確性和健壯性是相互補充的。

程序的可靠性指一個程序在正常情況下能正確地工作，而在異常情況下也能做出適當處理。

4. 效率

效率（Efficiency）包括運行程序所花費的時間以及運行這個程序所占用的存儲空間。算法應該有效使用存儲空間，并具有高的時間效率。

通俗地說，效率是指算法的執行時間，對于同一個問題，如果有多個算法可以解決，執行時間短的效率高，存儲量需求指算法執行過程中所需要的最大存儲空間，效率與低存儲量需求這兩者都與問題的規模有關，求100個人的平均分與求10000個人的平均分所花的執行時間或運行空間顯然有一定差別。

對于規模較大的程序，算法的效率問題是算法設計必須面對的一個關鍵問題，目標是設計復雜性盡可能低的算法。

5. 簡明性

簡明性是指算法應該思路清晰、層次分明、容易理解、利于編碼和調試，即算法簡單、程序結構簡單。

簡單的算法效率不一定高，要在保證一定效率的前提下力求得到簡單的算法。簡明性（Simplicity）是算法設計人員努力爭取的一個重要特性。

6. 最優性（Optimality）

最優性指求解某類問題中效率最高的算法，即算法的執行時間已達到求解該類問題所需時間的下界。最優性與所求問題自身的復雜程度有關。

例1.3　在n個不同的數中找最大數的算法Find max(L, n)。

輸入：數組L，項數n。

輸出：L中的最大項max。

max=L[1];  i=2;
while( i<=n )
{   if (max<L[i] )  max=L[i];
    i=i+1;
}

因為max是唯一的，其他的n-1個數必須在比較后被淘汰。一次比較至多可淘汰1個數，所以至少需要n-1次比較。即在有n個數的數組中找數值最大的數，并以比較作為基本運算的算法至少要做n-1次比較。Find max算法是最優算法。

一般來說，正確性和可讀性都比效率重要，一個在某些情況下會得出錯誤結果的算法，即使效率再高，也是沒有意義的。當然在基本保證正確的前提下，效率也是非常重要的。

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

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

1. 程序所依賴的算法

求解同一個問題的不同算法，其程序運行時間一般不同。一個好的算法運行時間較少。算法自身的好壞對運行時間的影響是根本的和起作用的。

2. 問題的規模和輸入數據

程序的一次運行是針對所求解問題的某一特定實例而言的。因此分析算法性能需要考慮的一個基本問題是所求解問題實例的規模，即輸入數據量，必要時也考慮輸出的數據量。此外問題的規模必須考慮數據的數值大??；再有需要說明的是即使是在同一計算機系統運行同一個程序，問題實例的規模也相同，由于輸入數據的狀態（如排列次序）不同，所需的時間和開銷也會不同。

3. 計算機系統的性能

算法運行所需要的時間還依賴于計算機的硬件系統和軟件系統。

1.3.3 算法復雜度

算法的復雜性是算法效率的度量，是評價算法優劣的重要依據。一個算法的復雜程度體現在運行該算法所需要的計算機資源的量上。這個量應該只依賴于算法要解的問題的規模、算法的輸入和算法本身的函數。而計算機的資源最重要的是時間資源和空間（存儲器）資源，需要時間資源的量稱為時間復雜性，需要空間資源的量稱為空間復雜性。

算法的復雜度主要包括時間復雜度和空間復雜度。

1. 算法的時間復雜度

算法的時間復雜度指算法運行所需時間，也指執行算法所需要的計算工作量。

（1）度量算法的工作量

一個算法是由基本運算和控制結構（順序、選擇、循環）構成的，則算法執行時間取決于兩者的綜合效果。為了便于比較同一個問題的不同算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本的運算，以該基本運算重復執行的次數作為算法的工作量。例如：在考慮兩個矩陣相乘時，可以將兩個實數之間的乘法運算作為基本運算，而對于所用的加法（或減法）運算可以忽略不計。

算法所執行的基本運算次數還與問題的規模有關。例如，兩個20階矩陣相乘與兩個3階矩陣相乘所需要的基本運算（即兩個實數的乘法）次數顯然是不同的。前者需要更多的運算次數，因此，在分析算法的工作量時，還必須對問題的規模進行度量。

綜上所述，算法的工作量用算法所執行的基本運算次數來度量，而算法所執行的基本運算次數是問題規模的函數。即算法的工作量=f (n)，n是問題的規模。

例如，兩個n階矩陣相乘所需要的基本運算（即兩個實數的乘法）次數為n3，即計算工作量為n3，也就是時間復雜度為n3。

（2）算法的執行時間絕大部分花在循環和遞歸上

對于循環語句的時間代價一般用以下三條原則分析：

① 對于一個循環，循環次數乘以每次執行簡單語句的數目即為其時間代價。

② 對于多個并列循環，可先計算每個循環的時間代價，然后按加法規則計算總代價。

③ 對于多層嵌套循環，一般可按乘法規則計算。但如果嵌套是有條件的，為精確計算其時間代價，要仔細累加循環中簡單語句的實際執行數目，以確定其時間代價。

對于遞歸算法，一般可把時間代價表示為一個遞歸方程。解這種遞歸方程最常用的方法是進行遞歸擴展，通過層層遞歸，直到遞歸出口，然后再進行化簡。

下面給出一類遞歸方程的求解方法。設遞歸方程為

遞歸擴展過程如下：

（3）時間復雜度（Time Complexity）

為了避免考慮計算機系統的性能對算法分析的影響，假定算法（程序）在一臺抽象的計算機模型上運行。

設抽象機提供m個基本運算（也可稱為語句）組成的運算集O={O1,O2,…,Om}，每個運算都是基本的，他們的執行時間是有限常量。同時，設執行第i個運算Oi所需的時間是αi，1≤i≤m。因此一個算法對于給定輸入在抽象機上的一次運行過程，表現為執行一個基本運算的序列。

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

（4）最好、最壞和平均時間復雜度

在具體分析一個算法的工作量時，還會存在這樣的問題：對于一個固定的規模算法所執行的基本運算次數是否相同呢？下面我們舉例進行說明。

例1.4　在長度為n的一維數組中查找值為x的元素。

若采用順序搜索法，即從數組的第一個元素開始，逐個與被查值x進行比較，顯然，如果第一個元素恰為x，則只需要比較1次，但如果x為數組的最后一個元素，或者x不在數組中，則需要比較n次才能得到結果。因此，在這個問題的算法中，其基本運算（比較）的次數與具體被查值x有關。

因此，在算法規模n相同，但輸入的數據I不同，算法所需的時間開銷也會不同。如果算法執行所需的基本運算的次數取決于某一特定輸入，這樣就存在最好B(n)、最壞W(n)和平均A(n)情況。

最壞情況指在規模為n時，算法所執行的基本運算的最大次數。平均情況指用各種特定輸入下的基本運算次數的數學期望值來度量算法的工作量。

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

這三種時間復雜度從不同角度反映算法的效率，但各有局限性。在很多情況下，各種輸入數據集出現的概率很難確定，算法的平均復雜度也就難以確定，其中比較容易分析和計算，且也最具有實際價值的是最壞情況時間復雜度。W(n)的計算比A(n)方便得多，由于W(n)實際上是給出了算法工作量的上界，因此它比A(n)更具有實用價值。因此本書算法分析的重點集中在最壞情況時間復雜度的分析和計算上。

下面通過一個例子來說明算法復雜度的平均情況分析和最壞情況分析。

例1.5　在例1.4中采用順序搜索法，在長度為n的一維數組中查找值為x的元素，即從數組的第一個元素開始，逐個與被查值x進行比較，基本運算為x與數組元素比較。

首先考慮平均性態分析，設被查項x在數組中出現的概率為q，則ti=i（1≤i≤n，當x為數組中第i個元素時，則需要比較i次），或ti=n（i=n+1，當x不在數組中時，需要和數組中所有元素比較）。

如果假設x出現在數組中每個位置的可能性是一樣的，則x出現在每一個位置的概率為q/n，而x不在數組中的概率為1-q。則pi=q/n（當1≤i≤n時），或pi=1-q（當i=n+1時）。

如果x一定在數組中q=1，A(n)=(n+1)/2，這就是說，順序搜索法查找時，平均情況下需檢查數組的一半元素。

再考慮最壞情況分析，最壞情況就是x在數組的最后一個元素或x不在數組中的時候。

W(n)=max{ti|1≤i≤n+1}=n

還有一種類型的時間效率稱為分攤效率，它并不針對算法的單次運行，而是計算算法在同一數據結構上執行一系列運算的平均時間。

2. 算法的空間復雜度（Space Complexity）

算法的空間復雜度是指算法運行所需的存儲空間。

一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的空間以及算法執行過程中所需要的額外空間，分為以下兩部分。

（1）固定空間需求（Fixed Space Requirement）

固定空間與所處理數據的大小和個數無關。即與問題實例的特征無關，主要包括程序代碼、常量、簡單變量、定長成分的結構變量所占的空間。

（2）可變空間需求（Variable Space Requirement）

可變空間與算法在某次運行中所處理的特定數據的規模有關。這部分存儲空間包括數據元素所占的空間，以及算法執行所需的額外空間。

若輸入數據所占空間只取決于問題本身和算法無關，則只需要分析除輸入和程序之外的額外空間，否則應同時考慮輸入本身所需空間。若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。

根據算法執行過程中對存儲空間的使用方式，我們又把對算法空間代價的分析分成兩種情形：靜態分析和動態分析。

① 靜態分析

一個算法靜態使用的存儲空間，是指在算法執行前，可以通過對程序靜態的分析確定的使用空間，稱為靜態空間。

在靜態空間分析中，值得注意的是數組（靜態數組），它占用了大部分靜態空間。

② 動態分析

一個算法在執行過程中以動態方式使用的存儲空間是指在算法執行過程中動態分配的存儲空間，它們從程序的表面形式上不能完全確定，我們把在算法執行過程中才能確定的空間稱為動態空間。動態空間的確定主要由兩種情況構成：一是函數的遞歸；二是調用動態分配（Malloc）和回收（Free）函數。

應當注意的是，空間復雜度一般按最壞情況來分析。在許多實際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術，以便盡量減少不必要的額外空間。

1.3.4 使用程序步分析算法

1. 度量一個程序的執行時間通常有兩種方法

（1）事后統計的方法

因為很多計算機內部都有計時功能，有的甚至可精確到毫秒級，不同算法的程序可通過運行程序時測試該程序在所選擇的輸入數據下實際運行所用的時間，以分辨不同算法的優劣。

通過一個算法在給定輸入下所執行的總的語句條數來計算算法的時間復雜度，有兩個缺陷：一是必須先運行依據算法編制的程序；二是所得時間的統計量依賴于計算機的硬件、軟件等環境因素，有時容易掩蓋算法本身的優劣，因此人們常采用另一種事前分析估算的方法。

（2）事前分析估算的方法

一個用高級語言編寫的程序在計算機上運行時所消耗的時間取決于以下幾個因素。

① 選用了怎樣的算法。

② 問題的規模。例如，求100以內還是10000以內的素數。

③ 書寫程序的語言。對于同一個算法實現語言的級別越高，執行效率就越低。

④ 編譯程序所產生的機器代碼的質量。

⑤ 機器執行指令的速度。

顯然，同一個算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行時效率均不同。這表明使用絕對的時間單位衡量算法的效率是不合適的。

在不考慮計算機系統因素的影響下，對算法自身的特性進行事前分析，即在算法實際運行前分析算法的效率，這種分析結果顯然不可能是程序運行時間的具體值，而是運行時間的一種事前估計。

2. 使用程序步分析算法

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

程序步的概念可以進一步簡化算法的分析，它并不是直接計算總的語句執行條數，而是將若干條語句合并成一個程序步來計算。

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

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;
}

程序步為：2n+3

引入程序步的目的是為了簡化算法的事前分析，不同的程序步在計算機上的實際執行時間通常是不同的，程序步并不能確切反映程序運行的實際時間。而且一個程序在一次運行中的總程序步的精確計算往往也是困難的。

1.3.5 漸近表示法

在分析解決同一個問題的兩個算法中，如果一個算法比另外一個算法多一個步驟，我們會認為這兩個算法的效率沒有什么不同，如果多10個、100個步驟，這兩個算法的效率是否有區別？問題的核心就是我們需要有一個衡量標準，在此標準內的算法的效率被認為是差不多的，而超過這個范圍，效率就有很大的不同，所以我們需要討論對數量級的表述。

考慮算法在輸入規模趨向無窮時的效率分析就是所謂的漸近分析。在忽略具體機器、編程或編譯器的影響下，只考察輸入規模n趨向無窮時算法效率的表現，即我們關注的是趨勢。

一般來說，當N單調增加且趨于∞時，T(N)也將單調增趨于∞。對于T(N)，如果存在函數T′(N)，使得當N→∞時有(T(N)-T′(N))/T(N)→0，那么我們就說T′(N)是T(N)當N→∞時的漸近性態。在數學上，T′(N)是T(N)當N→∞時的漸進表達式。例如，3N2+4Nlog2N+7與3N2。

漸近表示大大降低了分析算法的難度，免除精確計數的負擔，從而是算法分析的任務變得可以控制。下面引入各種具體的漸近表示，使得有望使用程序步在數量級上估計一個算法的執行時間，從而實現算法的事前分析。

1. 運行時間的上界（大O記號）

設函數f(n)和g(n)是定義在非負整數集合上的正函數，如果存在正整數n0和正常數c，使得當n≥n0時，有f(n)≤cg(n)，就稱f(n)的階至多是O(g(n))，記作f(n) = O(g(n))，稱為大O記號（Big Oh Notation），如圖1-3所示。

這個定義的意義是：當n充分大時有上界，且g(n)是它的一個上界，即f(n)的增長至多像g(n)那樣快。它用以表示一個算法運行時間的上界。對于給定的f可有無數個g與之對應，在算法分析中，應當選擇最小的函數g作為f的上界。

例1.6　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時，程序1-4的不會超過3n，2n+3=O(n)。

例1.7　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)。

例1.8　f(n) = 2n2+3，g(n)=n2。

當n≥3時，2n2+3≤3n2，所以，可選c=3，n0 = 3。對于n≥n0，f(n)= 2n2+3≤3n2，所以f(n) = O(n2)，即2n2+3=O(n2)。

例1.9　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)。

例1.10　10n2 + 9≠O(n)。

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

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

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

f(n)= amnm+ am-1nm-1+ … + a1n + a0≤|am|nm + |am-1|nm-1 + … + |a1|n + |a0|≤(|am| + |am-1|/n + … + |a1|/nm-1 + |a0|/nm) nm≤(|am| + |am-1| + … + |a1| + |a0|) nm

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

使用大O記號及下面定義的幾種漸近表示法表示的算法時間復雜度，稱為算法的漸近時間復雜度（Asymptotic Complexity），簡稱時間復雜度。

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

【程序1-5】矩陣乘法

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
    }

2. 運行時間的下界（Ω記號）

設有函數f(n)和g(n)是定義在非負整數集合上的正函數，如果存在正整數n0和正常數c，使得當n≥n0時，有f(n)≥cg(n)，就稱f(n)的階至少是的Ω(g(n))，記作f(n) =Ω(g(n))，稱為Ω稱記號（Omega Notation），如圖1-4所示。

這個定義的意義是：當n充分大時有下界，且g(n)是它的一個下界，f(n)的增長至少像g(n)那樣快。它用以表示一個算法運行時間的下界。

例1.11　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)。

例1.12　f(n)=2n2+3，g(n)=n2。

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

例1.13　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)。

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

3. 運行時間的準確界（Θ記號）

設有函數f(n)和g(n)是定義在非負整數集合上的正函數，如果存在正整數n0和正常數c1和c2（c1≤c2），使得當n≥n0時，有c1g(n)≤f(n)≤c2g(n)，就稱f(n)的階是Θ(g(n))，則記作f(n)=Θ(g(n))，稱為Θ記號（Theta Notation），如圖1-5所示。

即f(n)=Θ(g(n))當且僅當f(n)=O(g(n))且f(n)=Ω(g(n))，此時稱f(n)與g(n)同階。這個定義的意義是：f(n)的增長像g(n)一樣快。

例1.14　f(n) = 2n+3 = Θ(n)，即2n + 3= Θ(n)。

例1.15　f(n) = 2n2+3，g(n)=n2。則可以取n0 =3，c1 =1，c2 =3。

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

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

4. 算法按時間復雜度分類

算法按計算時間可分為兩類，凡漸近時間復雜度有多項式時間限界的算法稱作多項式時間算法（Polynomial Time Algorithm），而漸近時間復雜度為指數函數限界的算法稱作指數時間算法（Exponential Time Algorithm）。

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

O(1)<O(log2 n)<O(n)<O(nlog2 n)<O(n2)<O(n3)

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

O(2n)<O(n!)<O(nn)

隨著n的增大，算法在所需時間上非常懸殊，如圖1-6所示。