算法的漸進(jìn)分析（asuymptotic algorithm analysis）
簡稱算法分析。算法分析直接與它所求解的問題的規(guī)模n有關(guān)，因此，通常將問題規(guī)模作為分析的參數(shù)，求算法的時間和空間開銷與問題規(guī)模n的關(guān)系。

漸進(jìn)的時間復(fù)雜度

計算程序執(zhí)行頻度的目的是相比較兩個或多個完成相同功能的程序的時間復(fù)雜度，并估計但問題規(guī)模變化時，程序的運行時間如何隨之變化。

要想確定一個程序的準(zhǔn)確的執(zhí)行頻度有時是非常困難的，而且也不是很必要。因為程序執(zhí)行頻度這個概念本身就不是一個精確的概念。如賦值語句x=a和x=a+b*(c-d)-e/f居然有相同的執(zhí)行頻度。

由于執(zhí)行頻度不能確切地反映運行時間，所以用精確的程序執(zhí)行頻度來比較兩個程序，其結(jié)果不一定有價值。

如程序1-20所示遞歸求和算法的執(zhí)行頻度為2n+2，如果把它改成非遞歸程序，其語句執(zhí)行頻度反而是2n+3，比遞歸程序的運行時間還要多，這是不合理的。

因此，只要給出算法的執(zhí)行頻度的數(shù)量級，從n增長過程中分析算法執(zhí)行次數(shù)增大的數(shù)量級，即可達(dá)到分析的目的。

大O表示

在多數(shù)情況下，只要得到一個估計值就足夠了。若沒有問題的規(guī)模為n，程序的時間復(fù)雜度為T(n),當(dāng)n增大時，T(n)也隨之變大。可是T(n)將如何精確地變化，需要分析程序內(nèi)部結(jié)構(gòu)，使用大O表示法描述該程序時間復(fù)雜度的估計值。

大O表示法的一般提法是：當(dāng)且僅當(dāng)存在正整數(shù)c和n0，使得T(n)≤cf(n)對所有n≥n0成立，則稱該算法的時間增長率在O(f(n))中，記為T(n)=O(f(n))。

就是說，隨著問題規(guī)模n逐步增大，算法的時間復(fù)雜度也在增加。從數(shù)量級大小考慮，算法的程序語句的執(zhí)行次數(shù)(是n的函數(shù))是最壞情況下存在一個增長的上限，即cf(n)，即算法的增長率的上限為O(f(n)。

[例 1-21] 考察f(n)=3n+2。當(dāng)n≥2時，3n+2≤3n+n=4n，所以f(n)=O(n)，f(n)是一個變化的函數(shù)。

[例 1-22] 考察f(n)=10n2+4n+2.當(dāng)n≥2時，有10n2+4n+2≤10n2+5n，當(dāng)n≥5時，有5n≤n2，因此，對于n≥5，f(n)≤10n2+n2=112，f(n)=O(n2)。

[例 1-23] 考察f(n)=6×2^n+n2。當(dāng)n≥4，有n2≤2 ^n，所以對于n≥4，有f(n)≤6×2 ^n+2 ^n=7×2 ^n，因此f(n)=O(2 ^n).

[例 1-24] 考察f(n)h=9。當(dāng)n0-0，c=9，即可得到f(n)=O(1)。

可以這樣理解：假設(shè)f(n)=2n3+2n2+2n+1，當(dāng)n充分大時，T(n)=O(n3)，這是因為當(dāng)n很大時，與n3相比，n2與n的數(shù)值常常不產(chǎn)生決定影響，可以忽略不計。因此，使用大O表示法時，對于多項式只保留最高次冪的項，常數(shù)系數(shù)和低階項可以不要。

為使用大O表示法對一個較復(fù)雜的算法的漸進(jìn)時間復(fù)雜度進(jìn)行度量，一個簡捷的方法是分析關(guān)鍵操作的語句執(zhí)行次數(shù)，找出其與n的函數(shù)關(guān)系f(n)，從而得到漸進(jìn)時間復(fù)雜度。

關(guān)鍵操作大多存在于循環(huán)和遞歸中。關(guān)于遞歸的討論，參照前面例1-20中遞歸求和程序語句頻度進(jìn)行遞推的過程，不再做進(jìn)一步的討論。下面僅針對循環(huán)進(jìn)行討論。

對于單個循環(huán)而言，在循環(huán)內(nèi)的簡單語句即為關(guān)鍵操作，該程序段的漸進(jìn)時間復(fù)雜度應(yīng)是此關(guān)鍵操作的執(zhí)行次數(shù)的大O表示；對于幾個并列的循環(huán)，先分析每個循環(huán)的漸進(jìn)時間復(fù)雜度，然后利用大O表示法的加法規(guī)則來計算其時間復(fù)雜度。

大O表示法的加法規(guī)則是指當(dāng)兩個并列的程序段的時間代價分別為T1(n)=O(f(n))和T2(m)=O(g(m))時，那么將兩個程序段連在一起后整個程序段的時間代價為：

T(n,m)=T1(n)+T2(m)=O(max{f(n),g(m)})

對于嵌套循環(huán)，關(guān)鍵操作應(yīng)在最內(nèi)層循環(huán)中。先自外向內(nèi)層層分析每層循環(huán)的漸進(jìn)時間復(fù)雜度，然后利用大O表示法的乘法規(guī)則來計算其漸進(jìn)時間復(fù)雜度。

大o表示法的乘法規(guī)則是指當(dāng)兩個嵌套的程序段的時間代價分別是T1=O(f(n))和T2(m)=O(g(m))時，整個程勛段的時間代價為

T(n,m)=T1(n)×T2(m)=O(f(n)×g(m))

[例 1-25] 有一個包含n個整數(shù)的數(shù)組A，設(shè)計一個算法，刪除多余的重復(fù)整數(shù)。算法的實現(xiàn)參看下面的程序1-23。為避免每檢測到一個重復(fù)整數(shù)，都要整體移動其后的所有整數(shù)，先對多余的重復(fù)整數(shù)做刪除標(biāo)記，待所有整數(shù)都加測完，再一次性地做數(shù)據(jù)移動，把做過的刪除標(biāo)記的整數(shù)全部移去。算法返回刪除后整數(shù)個數(shù)n。

[程序 1-23] 在數(shù)組A中刪除重復(fù)的整數(shù)。

#include <limits.h> //有32b最小整數(shù)常數(shù)_I32_MIN #define delTag_I32_MIN //定義刪除標(biāo)記 void remove Redundancy(int A[],int &n){ //刪除數(shù)組A中所有多余的重復(fù)整數(shù)。有重復(fù)事僅保留其最初出現(xiàn)的整數(shù)int i,j,k=0;for(i=0;i<n;i++) //檢測所有整數(shù)for(j=i+1;j<n;j++)if(A[i]==A[j])A[j]=delTag; //對重復(fù)數(shù)刪除標(biāo)記for(i=0;i<n;i++)if(A[i]!=delTag){if(i!=k)A[k]=A[i];k++;}n=k; }

算法中有兩個并列的循環(huán)結(jié)構(gòu)。第一個循環(huán)結(jié)構(gòu)是兩層嵌套循環(huán)，其關(guān)鍵操作是最內(nèi)層的if語句(程序第8行)。它的執(zhí)行頻度是

它服從函數(shù)f(n)=n(n-1)/2，使用大O表示法得到T1(n)=O(f(n))=O(n2)。第二個循環(huán)是單層循環(huán)，其關(guān)鍵操作是循環(huán)內(nèi)得if語句(程序第10行)，它的執(zhí)行頻度為n，使用大O表示法得到T2(n)=O(g(n))=O(n)。整個程序的漸進(jìn)時間復(fù)雜度按照加法規(guī)則為T(n)=O(max{f(n),g(n)})=O(n2)。

類似地，如果一個程序的循環(huán)中有一個包含有循環(huán)的函數(shù)調(diào)用語句，也可以在被調(diào)用的函數(shù)內(nèi)部尋找關(guān)鍵操作，使用這個規(guī)則來計算其漸進(jìn)時間復(fù)雜度。

在大O表示法的乘法規(guī)則里有一個特例，如果T1(n)=O?，c是一個與n無關(guān)的任意常數(shù)，T2(n)=O(f(n))，則有

T(n)=T1(n)T2(n)=O(cf(n))=O(f(n))

這也說明在大O表示法中，任何非0正常數(shù)都屬于同一數(shù)量級，記為O(1)。

事實上，要全面分析一個算法，需要考慮算法在最壞環(huán)境下的時間代價，在最好情況下的時間代價和在平均情況下的時間代價。而大O表示法時針對最壞情況而言的。

當(dāng)n充分大時，各種函數(shù)的增長有如下關(guān)系：

c < log2n < n < nlog2n < n2 < n3 < 2^n < 3^n < n!

其中，c是與n無關(guān)的任意正數(shù)。如果一個算法的時間復(fù)雜度取到c、log2n、n或nlog2n，那么他的時間效率比較高，如下表所示。如果取到2^n, 3 ^n或n！，那么當(dāng)n稍大一點，算法的時間代價就會變得很大，以至于不能計算了。

漸進(jìn)的空間復(fù)雜度

當(dāng)問題規(guī)模n充分大時，需要的存儲空間隨之變化的情況也可以像分析時間復(fù)雜度一樣用大O表示法來表示。設(shè)S(n)是算法的漸進(jìn)空間復(fù)雜度，在最壞的情況下它可以表示為問題規(guī)模n的某個函數(shù)f(n)的數(shù)量級，記為

S(n)=O(f(n))

同樣需要注意的是，存儲空間指的是為解決問題所需要的輔助存儲空間。例如在排序算法中為移動數(shù)據(jù)所需的歸時工作單元，在遞歸算法中所需的遞歸工作棧等。

通常，只有完成同一功能的幾個算法之間才具有可比性。例如，同樣是排序算法，待排序數(shù)據(jù)都是n個，作為輸入和存放這些數(shù)據(jù)的數(shù)組或鏈表結(jié)點也同樣都是n個，因此這些輸入數(shù)據(jù)所占用的存儲空間不用進(jìn)行比較，可比較的只有那些輔助的或附加的存儲空間。可以使用大O表示法來標(biāo)記這些空間，用以比較各算法的優(yōu)劣。

總結(jié)

以上是生活随笔為你收集整理的3.算法的渐进分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。