第2章算法分析

第2章算法分析基礎(chǔ)學(xué)習(xí)要點:

理解算法分析的任務(wù)和目的掌握漸近標(biāo)記法在算法分析中的應(yīng)用掌握算法分析的方法能夠分析算法的最好、最壞、平均時間復(fù)雜度

算法分析的任務(wù)：對設(shè)計出的每一個具體的算法，利用數(shù)學(xué)工具，討論其復(fù)雜度。對算法的評價有兩個大的方面：一是人對算法的維護的方便性。二是算法在實現(xiàn)運行時占有的機器資源的多少，即算法運行的時間和空間效率。

目的：設(shè)計和選擇出復(fù)雜性盡可能低的算法來解決問題。★2.1.1時間復(fù)雜性算法運行所需要時間資源的量，T=T(n,I,A)。其中，n表示算法要解的問題的規(guī)模；

I表示算法的輸入；

A表示算法本身。算法在一臺抽象計算機上運行的時間。

T(n,I)=其中，ti是計算機所提供的元運算執(zhí)行一次所需時間；ei是算法用到元運算Oi的次數(shù)。2.1

算法的復(fù)雜性三種情況下的時間復(fù)雜性最壞情況

Tmax(n)=max{T(I)|size(I)=n}最好情況

Tmin(n)=min{T(I)|size(I)=n}平均情況

Tavg(n)=其中，I是問題的規(guī)模為n的實例，p(I)是實例I出現(xiàn)的概率。2.1.2空間復(fù)雜性算法運行所需要空間資源的量，S=S(n,I,A)。其中，n表示算法要解的問題的規(guī)模；

I表示算法的輸入；

A表示算法本身。算法在一臺抽象計算機上運行時所占用的空間。分析起來比時間復(fù)雜性簡單，本課程以時間復(fù)雜性為討論主體。

2.1.3漸近復(fù)雜性對于T(n)，如果存在f(n)，使得當(dāng)n→∞時有(T(n)-f(n))/T(n)→0，那么，就說f(n)是T(n)當(dāng)n→∞時的漸近性態(tài)。又稱算法A的漸近復(fù)雜性。在數(shù)學(xué)上，f(n)是T(n)的漸近表達式，是T(n)略去低階項留下的主項。它比T(n)簡單。例如，T(n)＝3n2+4nlogn+7，則f(n)的一個答案是3n2，因為，此時有(T(n)-f(n))/T(n)=→0（當(dāng)n→∞）漸近復(fù)雜性分析只關(guān)心f(n)的階！2.2.1評價算法的準(zhǔn)則算法正確性算法結(jié)構(gòu)（健壯性）最佳性時間復(fù)雜性空間復(fù)雜性2.2算法分析的一般方法2.2.2評價算法時間復(fù)雜性的一般方法分析并確定：算法的哪些參數(shù)決定算法的“輸入規(guī)?！保?/p>

原因：問題實例的輸入規(guī)模較大的，算法得到輸出需要更多的時間開銷。明確：被分析算法的“關(guān)鍵操作”是什么？

關(guān)鍵操作：算法中重要的操作，或所關(guān)心的操作。“關(guān)鍵操作的數(shù)量”→“算法的時間復(fù)雜度”！

例：內(nèi)排：(“比較類”)待排序元素之間的“比較”次數(shù)；待排序元素的“移動”次數(shù)。

查找：待查找值x與數(shù)據(jù)元素之間的“比較”次數(shù)。

矩陣乘法：矩陣元之間的乘法/加法運算次數(shù)。算法分析的目標(biāo)：考察算法的“關(guān)鍵操作”數(shù)，隨“問題規(guī)?！倍兓囊?guī)律。提高計算速度對不同時間復(fù)雜性函數(shù)的影響對比T(n)微秒lognnnlognn2n3n52n3nn!n=103.310331001毫秒0.1秒1毫秒59毫秒3.6秒n=405.340213160064毫秒1.7分12.7天3855世紀(jì)103世紀(jì)n=605.9603543600216毫秒1.3分366世紀(jì)1.3×1013世紀(jì)1066世紀(jì)多項式函數(shù)指數(shù)函數(shù)時間復(fù)雜性函數(shù)用現(xiàn)在的計算機用快100倍的計算機用快1000倍的計算機nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29算法時間復(fù)雜度的漸近表示

算法的時間開銷隨問題規(guī)模增大的變化趨勢。例2-1：簡單選擇排序算法的“比較”次數(shù)

0123456…n-1a:(2,5,8,|12,9,20,15,…,66)

||↑↑

小大ij(K)voidSELECT_SORT(Typea[],intn){FOR(inti=0;i<=n-2;i++){intk=i;FOR(intj=i+1;j<=n-1;j++){IF(a[j]<a[k])k=j;};IF(k!=i)a[k]?a[i];};}

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

→t(n)注：n個元素存放在a[0]～a[n-1]之上！?多項式函數(shù)2.2.3算法漸近復(fù)雜性分析定義界函數(shù)設(shè)：f和g是兩個函數(shù)，f,g:N→R+。若存在正整數(shù)c和n0，使得對于所有n≥n0,都有：f(n)≤cg(n)，則稱g(n)是f(n)的上界，記為：

f(n)=O(g(n))理解：

ⅰ能夠滿足定義的g(n)，可以是一個函數(shù)集合

ⅱg(n)不小于f(n)，且g(n)是“簡潔”的函數(shù)。例如，當(dāng)n≥10時，有2n2+11n-10≤3n2，所以有2n2+11n-10=O(n2)O標(biāo)記的運算規(guī)則：⑴

O(f(n))+O(g(n))=

O(max{f(n),g(n)})⑵O(f(n))+O(g(n))=

O(f(n)+g(n))⑶O(f(n))*O(g(n))=

O(f(n)*g(n))⑷O(cf(n))=

O(f(n))⑸g(n)=O(f(n))O(f(n))+O(g(n))=

O(f(n))若存在正整數(shù)c和n0，使得對于所有n≥n0，都有：f(n)≥cg(n)，則稱g(n)是f(n)的下界，記為：

f(n)=Ω(g(n))若存在正整數(shù)c1、c2和n0，使得對于所有n≥n0，都有：c1g(n)≤f(n)≤c2g(n)，則稱g(n)是f(n)的精確界，記為：

f(n)=Θ(g(n))如果對于任意c＞0，都存在非負(fù)整數(shù)n0，使得當(dāng)n≥n0時，有f(n)＜

cg(n)，則稱g(n)是f(n)的非緊上界，記為：

f(n)=o(g(n))如果對于任意c>0，都存在正數(shù)n0>0，使得當(dāng)n≥n0時，有：f(n)＞

cg(n)，則稱g(n)是f(n)的非緊下界，記為：

f(n)=

(g(n))定理1：

(g(n))=O(g(n))

(g(n))常用函數(shù)單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)f(n)單調(diào)遞減：m

n

f(m)f(n)嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n)嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n)取整函數(shù)x：不大于x的最大整數(shù)

x：不小于x的最小整數(shù)多項式函數(shù)如果p(n)=a0+a1n+a2n2+…+adnd，ad>0；則

p(n)=(nd)

f(n)=O(nk)f(n)多項式有界；

f(n)=O(1)

f(n)

c;

kdp(n)=O(nk);kdp(n)=(nk);k>

dp(n)=o(nk);k<dp(n)=(nk)指數(shù)函數(shù)對于正整數(shù)m,n和實數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1an為單調(diào)遞增函數(shù);a>1nb=o(an)ex

1+x|x|11+xex

1+x+x2

∴

當(dāng)x0，有ex

=1+x+(x2)對數(shù)函數(shù)logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)kl;loglogn=log(logn);

如果a>0,b>0,c>0，則階乘函數(shù)Stirling’sapproximation(斯特林逼近公式)：其中，例2-2：分析“計算n階方陣A、B的乘積”算法。voidMatrixMulti(TypeA[],TypeB[],TypeC[],intn){FOR(inti=0;i<=n-1;i++){FOR(intj=0;j<=n-1;j++){C[i,j]=0;FOR(intk=0;k<=n-1;k++)C[i,j]=C[i,j]+A[i,k]*B[k,j];};};}

T(n)===

=n3=(n3)

算法的最壞情況下的復(fù)雜度設(shè)：I是問題規(guī)模為n的所有輸入的集合，i∈I是問題的一個輸入實例。ti(n)是輸入i下，算法A的“關(guān)鍵操作”數(shù)。則，算法A的最壞情況復(fù)雜度：WA(n)=max{ti(n)}

i∈I例2-3：“順序表查找”算法intSearch_line(Typea[],intn,Typex){a[n]=x;intj=0;WHILE(x!=a[j])j=j+1;IF(j==n)RETURN(0);失敗

ELSERETURN(1);}

失敗查找最壞特性：WAu(n)=n+1平均復(fù)雜度設(shè)：I是問題規(guī)模為n的所有輸入的集合，i∈I是問題的一個輸入實例。ti(n)是輸入i下，算法A的“關(guān)鍵操作”數(shù)。Pi(n)是輸入i出現(xiàn)在I中的概率。則，算法A的平均時間復(fù)雜度：AVA(n)=∑(Pi(n)ti(n))

i∈I例2-4：“順序表查找”算法的平均復(fù)雜度：設(shè)：“失敗”概率為q(0≤q≤1)。而且假設(shè)“成功”查找時，各種輸入“等概率”，即：成功查找的輸入概率為psi(n)=(1-q)/nAVA(n)=∑Pi(n)ti(n)=∑Psi(n)ti(n)+∑Pui(n)ti(n)=∑[(1-q)/n

·(j+1)]+q·(n+1)=(1-q)/n∑(j+1)+q(n+1)=(1+q)(1+n)/2i∈Isi∈I成功ui∈I失敗n-1j=0n-1j=0課后作業(yè)P28：1.2.2.4算法分析實例非遞歸算法分析僅依賴于“問題規(guī)?！钡臅r間復(fù)雜度例2-5：交換i和j的內(nèi)容。

Temp=i;i=j;j=Temp;

以上三條基本語句的執(zhí)行次數(shù)(語句頻度)均為1，該算法段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(shù)。算法的時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。結(jié)論：如果算法的執(zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句,其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是O(1)。例2-6：變量計數(shù)之一。

(1)x=0；y=0；

(2)for(k=1;k<=n;k++)(3)x++；

(4)for(i=1;i<=n;i++)(5)for(j=1;j<=n;j++)(6)y++；該算法段的時間復(fù)雜度為T(n)=O(n2)。結(jié)論：當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度f(n)決定的。T(n)=

=n+n2n＞1時，有T(n)≤2n2=t(n)(n0=1，c=2)Tx(n)+Ty(n)=例2-7：變量計數(shù)之二。

(1)x=1;(2)for(i=1;i<=n;i++)(3)for(j=1;j<=i;j++)(4)for(k=1;k<=j;k++)(5)x++;

該算法段的基本語句是(5)，從內(nèi)層循環(huán)向外層分析語句(5)的執(zhí)行次數(shù)：

===則，該算法的時間復(fù)雜度為：T(n)=O(n3/6+低次項)=O(n3)算法的時間復(fù)雜度與輸入實例的初始狀態(tài)有關(guān)例2-8：一個簡單k-選擇算法(偽碼)如下所示。算法思想：首先采用冒泡排序算法，按照從小到大次序，排出a數(shù)組的前k個元素，然后返回a數(shù)組的第k-1個元素。intK_SELECT(Typea[],intn,intk){p=1;//p控制“冒泡”的趟數(shù)

while(p<=k){j=n-1;while(j>=p)//進行“冒泡”，第p趟將第p小的元素交換到位

{if(a[j]<a[j-1])a[j]?a[j-1];j=j-1;};p=p+1;};RETURN(a[k-1]);}注：n個元素存放在a[0]～a[n-1]之上。問題規(guī)模：n，關(guān)鍵參數(shù)k解答以下問題：1.試分析算法的時間復(fù)雜度。即，求出數(shù)組a不同元素之間比較次數(shù)的關(guān)系表達式T(n,k)。解：顯然，T(n,k)不僅與n有關(guān)，而且與k有關(guān)。

T(n,k)===k(2n–k–1)/22.問：在什么情況下，算法有最壞時間復(fù)雜度和最好時間復(fù)雜度？分別計算最好、最壞情況下的時間復(fù)雜度。

解：當(dāng)k=n時，算法有最壞時間復(fù)雜度。此時，

T(n,k)=T(n,n)=n(n-1)/2

當(dāng)k=1時，算法有最好時間復(fù)雜度。此時，

T(n,k)=T(n,1)=n–13.如果k在1至n之間取值等概率，請計算該算法的平均時間復(fù)雜度，并寫出它的上界函數(shù)。解：∵對于一個確定的k值，算法具有時間復(fù)雜度：

T(n,k)=k(2n–k–1)/2∴算法的平均時間復(fù)雜度是對T(n,k)的“加”權(quán)平均值。故，算法的平均時間復(fù)雜度是：

A(n)=1/n

=(n2-1)/3=O(n2)→O(n2)→O(n)非遞歸算法分析的一般步驟：分析算法問題規(guī)模；明確關(guān)鍵操作；分析關(guān)鍵操作執(zhí)行次數(shù)是否只依賴于問題規(guī)模？是，就直接建立關(guān)鍵操作執(zhí)行次數(shù)的求和表達式，并求解；否則，分別對該算法的最好、最壞和平均情況的時間復(fù)雜度進行分析。用漸進符號表示。遞歸算法分析代入法（猜測法）先推測遞歸方程的顯式解，然后用數(shù)學(xué)歸納法來驗證該解是否合理。迭代法（擴展遞歸法）迭代地展開遞歸方程的右端，使之成為一個非遞歸的和式，然后通過對和式的估計來達到對方程左端即方程的解的估計。通用分治遞推式法這個方法針對形如“T(n)=aT(n/b)+f(n)”的遞歸方程。差分方程法可以將某些遞歸方程看成差分方程，通過解差分方程的方法來解遞歸方程，然后對解作出漸近階估計。□□迭代法（擴展遞歸法）例2-9：求N!分析：構(gòu)造算法中的兩個步驟：

⑴

0!=1,1!=1⑵N!=N*(N-1)!遞歸算法如下：fact(intn){if(n=0orn=1)return(1);elsereturn(n*fact(n-1));}

遞歸方程為：T(n)=T(n-1)+O(1)，其中O(1)為一次乘法操作的執(zhí)行時間。迭代求解過程如下：

T(n)=T(n-2)+O(1)+O(1)=T(n-3)+O(1)+O(1)+O(1)……=O(1)+……+O(1)+O(1)+O(1)=n*O(1)=O(n)例2-10：分析下面遞推式的時間復(fù)雜度。設(shè)，n=2k∴?íì>+==15)2(217)(2nnnTnnT222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×′+++=+++=++=+=--L)(10310)212(57257)(22212102nOnnnnnnnnTkkii=￡-=-+=???è?+=--=?通用分治遞推式法形如“T(n)=aT(n/b)+f(n)”的遞歸方程是分治法的時間復(fù)雜性所滿足的遞歸關(guān)系。即一個規(guī)模為n的問題被分解為a個規(guī)模為n/b大小的子問題，分別求這a個子問題的復(fù)雜性，再合并各子問題(f(n)就是其工作量)?íì>+==1)(1)(ncnbnaTncnTkf(n)假定n=bm，則：T(n)=aT(n/b)+cnk=a(aT(n/b2)+c(n/b)k)+cnk=amT(1)+am-1c(n/bm-1)k+...+ac(n/b)k+cnk

===∵am=

=,∴有三種情況,r=：⑴r<1,<,由于am=

,所以T(n)=O()⑵r=1,=m+1=logbn+1,由于am==nk

,所以

T(n)=O(nklogbn)⑶r>1,==O(rm),所以T(n)=O(amrm)=O(bkm)=O(nk)例2-11：已知：x、y是n位二進制數(shù)（n=2r，r:非負(fù)正數(shù)），a、b、c、d與x、y的關(guān)系如下所示。試設(shè)計算法，計算p=xy，并分析算法關(guān)于二進制數(shù)運算（乘法、加法、移位）的時間復(fù)雜度。x:y:abcd算法一：p=xy=(a2n/2+b)(c2n/2+d)=ac2n+(ad+bc)2n/2+bd1)計算ac，并將結(jié)果“左移”n位；2)分別計算ad、bc，并求它們的和，再對和數(shù)“左移”n/2位；3)計算bd；4)對1)、2)、3)的結(jié)果求和。時間復(fù)雜性的遞推式：其中，m為正數(shù)根據(jù)遞推公式⑴可知，a=4,b=2,k=1所以有，a=4>bk=2，則上述遞推式解為：

T(n)==O(n2)思考：該算法可否改進？?íì>+==1)(1)(nmn2n4TnmnTanOb)(log算法二：令：u=(a+b)(c+d),v=ac,w=bd有：p=xy=ac2n+(ad+bc)2n/2+bd=v2n+(u-v-w)2n/2+w建立遞推關(guān)系式：求解遞推關(guān)系式：T(n)=3T(n/2)+mn=3[3T(n/22)+m(n/2)]+mn=···=3r+1·m-2mn=3m–2mn≈3mn1.59–2mn=O(n1.59)?íì>+==1)(1)(nmn2n3TnmnTn32log2.2.5判定樹模型：適用于“比較”算法判定樹：是一棵滿足以下條件的二叉樹，每一個內(nèi)部結(jié)點對應(yīng)一個形如x≤y的比較，如果關(guān)系成立，則控制轉(zhuǎn)移到該結(jié)點的左子樹，否則，控制轉(zhuǎn)移到該結(jié)點的右子樹；每一個葉子結(jié)點表示問題的一個結(jié)果。要點:1)“內(nèi)部結(jié)點”表示一次“比較”；

2)“分支”表示一次“比較”后,算法的“走向”

3)“外部結(jié)點”表示一種可能的輸出。例2-6：用天平盡快找出27枚硬幣中，質(zhì)地較輕的一枚。a:bc1:c2c31:c32c33是“假幣”a=bc1=