清華大學(xué)算法課13課件

算法與數(shù)據(jù)結(jié)構(gòu)

AlgorithmsandDataStructures

第十三章算法分析與設(shè)計(jì)技術(shù)

AlgorithmAnalysisandDesignTechniques

13.1遞歸算法的分析13.2遞歸式求解13.3大遞歸式的一般解13.4分而治之法13.5動態(tài)規(guī)劃法13.6貪心法13.7搜索算法13.1遞歸算法的分析考慮一個歸并排序算法：Listmergesort(List

L,intn){if(n==1)returnL;breakLinto2halves,L1andL2,eachoflengthn/2;returnmerge(mergesort(l1,n/2),mergesort(l2,n/2));}//設(shè)T(n)是最壞情況下的時間復(fù)雜度。顯然：

T(n)=1ifn=1;T(n)<=2T(n/2)+cnifn>1我們前面已做過很多遞歸算法的分析，給出了相應(yīng)的遞歸式；例如：Hanoi塔：T(0)=0T(n)=2T(n-1)+1折半查找：T(0)=0;T(1)=1;T(n)=T(n/2)+1;最復(fù)雜的是快速排序。13.2遞歸式求解有三種方法：(1).猜一個解f(n)，代入遞歸式，對n歸納證明T(n)<=f(n)，同時確定F(n)中的不定系數(shù)，使對所有的n有T(n)<=f(n)。(2).展開遞歸式，直到式子的右邊的T(m)均為初試遞歸式（如T(0),T(1)）.(3).一般求法。1猜解：

T(n)=1ifn=1;T(n)<=2T(n/2)+cnifn>1設(shè)T(n)=a.n.logn+b

歸納基礎(chǔ)：當(dāng)n=1時b>=1設(shè)對所有的k<n有a.k.logk+b>=T(k)當(dāng)k=n時：T(n)<=2T(n/2)+cn2.展開遞歸式13.3大遞歸式的一般解考慮遞歸算法：T(1)=1把大小為n的問題，分解為a個大小為n/b的子問題，劃分問題和合并子問題的解所做工作量是d(n).則：T(1)=1T(n)=aT(n/b)+d(n)d(n)成為驅(qū)動函數(shù)對上一個遞歸式，a=b=2,d(n)=cn展開遞歸式：特解ParticularSolution通解HomogeneousSolution下面考慮特解：如果d(n)是積的形式，如(xy)k=xkyk

則特解所以考慮3種情況下的特解：若：a>d(b)2.若：a<d(b),3若：a=d(b)，特別當(dāng)例1：

T(1)=1T(n)=4T(n/2)+nT(n)=4T(n/2)+n2T(n)=4T(n/4)+n3由于三個式中：a=4,b=2,它們的通解都是n2;d(n)=n,所以d(b)=2,因a=4>d(b)(2)d(n)=n2,所以d(b)=4,因a=4=d(b)(3)T(n)=4T(n/4)+n3d(n)=n3,所以d(b)=8,因a=4<d(b)

特解是：O(d(n))=n3以上討論的是d(n)是n的積的形式，下面考慮非積形式。例2：

T(1)=1T(n)=3T(n/2)+2n1.5

2n1.5不是n的積的形式，但n1.5是，令U(n)=T(n)/2U(1)=1/2U(n)=3U(n/2)+n1.5如果U（1）=1，則通解是：nlog3=n1.59因U(1)=1/2，所以通解是：n1.59/2a=3,b=2,d(n)=n1.5

，d(b)=21.5=2.82,a>d(b)所以特解是：n1.59所以T(n)=O(n1.59)例3：

T(1)=1T(n)=2T(n/2)+nlogn顯然通解是n。a=b=2,d(n)=nlogn

不是n的積。特解：13.4分而治之法分而治之就是將大的問題分解小的子問題分別解決，最常用的辦法是遞歸算法。在前面我們已設(shè)計(jì)了許多遞歸算法，諸如：Hanoi塔，快速排序，歸并排序，二叉樹遍歷，dfs，等等。下面在看幾個例子，它們比較特殊例4：兩個n位正整數(shù)相乘，這兩個數(shù)很大，大到計(jì)算機(jī)內(nèi)部無法表示。為簡化問題，設(shè)n是2的冪。X=ABY=CDX=A10n/2+BY=C10n/2+DXY=AC10n+(AD+BC)10n/2+BD算法分析：位乘次數(shù)T(1)=1T(n)=4T(n/2)+cnT(n)=O(n2)改進(jìn)：XY=AC10n+[(A-B)(D-C)+AC+BD)]10n/2+BDT(1)=1T(n)=3T(n/2)+cnT(n)=O(n1.59)

以上公式已說明了遞歸算法的三要素。算法Voidmult-Big-Num(&c[],x[],y[],n){bytem1[],m2[],m3[];byteA[n/2],B[n/2],C[n/2],D[n/2];c[]=newbyte[2*n];if(n==1)if(x!=0&&y!=0)c[]=multy(x,y,1);elsec[]=0;else{

A=leftn/2digitsofx[];B=rightn/2digitsofx[];C=leftn/2digitsofy[];D=rightn/2digitsofy[];mult-big-num(&m1,A,C,n/2);mult-big-num(&m2,A-B,D-C,n/2);mult-big-num(&m3,B,D,n/2);c=m1;c=left-shift(c,n/2);c+=m1+m2+m3;c=left-shift(c,n/2);c+=m3;

//m1*10n+(m1+m2+m3)*10n/2+m3}}

例5：網(wǎng)球循環(huán)賽的安排，每個選手每天只能參賽一場，如有n個選手，需要進(jìn)n-1天。為簡單起見，設(shè)n是2的冪。（1）最簡問題及其解：n=2,（2）問題的劃分：將n個分成兩組，每組n/2人，進(jìn)行循環(huán)比賽。（3）解的合成：21121天

21121天23414341232112341232143+212213443加第1行：12第2行：第1行左循環(huán)位移23414341232167858785676556786785785685671234234134124123加第1行：1234第2行：第1行左循環(huán)位移第3行：第2行左循環(huán)位移第4行：第3行左循環(huán)位移+413.5動態(tài)規(guī)劃法(DynamicProgramming)在本節(jié)中我們通過一些列子說明什么是動態(tài)規(guī)劃法。例6：斐波拿契數(shù)列：

f(0)=0,f(1)=1f(n)=f(n-1)+f(n-2);510211010433221問題分解解的合成遞歸子問題圖遞歸求解如圖：其中f(3)重復(fù)計(jì)2次，f(2)重復(fù)計(jì)算3次當(dāng)n增大時，這樣的重復(fù)計(jì)算會按指數(shù)級增長。如果我們把子問題的解記錄下來，當(dāng)需要時，直接引用，就可避免重復(fù)計(jì)算。當(dāng)求一個子問題P的解時,它可能用到子問題P1，P2，…，Pk的解，在遞歸算法中P1，P2，…，

Pk的解是遞歸調(diào)用算法計(jì)算出來的，我們現(xiàn)在希望能從表中找到他們的解，而不是再計(jì)算。這樣就需要搞清楚所有子問題間的依賴關(guān)系。我們用一個有向圖表示這種關(guān)系。稱此圖為子問題圖（Subproblem

Garph）012345從最簡單問題開始，我們由底向上逐層把子問題的解添在一個表中，在合成解時，從表中查找所需要的下層的子問題的解即可。這樣的方法是最基本的動態(tài)規(guī)劃法。規(guī)劃的另一個含義是在多個候選者中選擇最好的。Fibonacci數(shù)列問題的子問題圖：012345求子問題解的順序是按逆拓?fù)湫蜻M(jìn)行的。例7：我們已熟悉的一個問題：求組合數(shù)：4,23,23,12,22,12,12,01,11,01,11,0遞歸求解過程遞歸算法的動態(tài)規(guī)劃版遞歸算法:Int

comb(int

m,intn){if(m==0||m==n)return1;return(comb(m-1,n-1)+comb(m,n-1));}//ADTDictionaryis

//設(shè)一個ADTDictionary

Data:Setofsubproblem’sresults;

Operations:

store(sbp,rslt);//存儲子問題sbp的解rslt

member(sbp);//檢查sbp的解是否已在字典中

retrieve(sbp);//取出sbp的解ENDADTDictionary動態(tài)規(guī)劃算法:dic是ADTDictionaryInt

comb(int

m,intn){if(m==0||m==n)rslt=1;else{if(!dic.member((m-1,n-1)))rslt1=comb(m-1,n-1);elserslt1=dic.retrieve((m-1,n-1));if(!dic.member((m,n-1)))rslt2=comb(m,n-1);elserslt2=dic.retrieve((m,n-1));

rslt=rslt1+rslt2;}

dic.store((m,n),rslt);}//如果問題圖很清楚，可以直接按該圖的逆拓?fù)湫虮闅v求解各子問題。通常dic是一個數(shù)組（一維或二維）1,02,03,04,01,12,13,14,12,23,24,2子問題圖4,23,23,12,12,21,11,04,03,02,0拓?fù)湫蛄兄籲m1234564321011111111112345636101541020515For(j=1;j<=n;j++)c[0][j]=1;For(i=0;i<=m;i++)c[i][j]=1;For(i=1;i<=m;i++)For(j=i+1;j<=n;j++)c[i][j]=c[i][j-1]+c[i-1][j-1]算法分析：梯形計(jì)算mn012345543211111111111233464510試一試，只用一維數(shù)組如何計(jì)算105最優(yōu)二查查找樹二叉查找樹ringhasthingcabbagetalkofwalrusandsaidkingtimecomethepigwing平均查找長度：其中：pi

是查找第i個對象的概率，ci

是比較次數(shù)。

例：Key pi

比較ci piciAnd .150 4 .600Cabbage .025 3 .075Come .050 4 .200Has .025 2 .050King .050 4 .200Of .125 3 .375Pig .025 4 .100Ring .075 1 .075Said .075 4 .300Talk .050 3 .150Key pi

比較ci piciThe .150 4 .600Thing .075 2 .150Time .050 2 .100Walrus .025 3 .075Wing .050 4 .200平均查找長度：total=3.250顯然這不是一個最優(yōu)二叉查找樹。關(guān)鍵字集：k1,k2,k3,…..,kn,[ki<ki+1:i=1,2,…,n-1]查找概率：p1,p2,p3,…..,pn

[權(quán)]子問題（low,high）:

構(gòu)造klow,klow+1,...,khigh的最優(yōu)二叉查找樹。我們采用以下表示：1A(low,high,r)是以kr為根的子問題（low,high）的最小平均查找長度。2A(low,high)是子問題（low,high）的最小平均查找長度。3p(low,high)=plow+plow+1+…+phigh,被查找key在klow,klow+1,...,khigh的概率。A(l,h,r)=A(l,r-1)+A(r+1,h)+p(l,r)r=l,l+1,…,hA(l,h)=min{A(l,h,r)|l<=r<=h}根據(jù)這兩個式子我們可以設(shè)計(jì)一個遞歸算法計(jì)算A(1,n),但其中有許多的A(s,t)需要重復(fù)計(jì)算。KrKl,…,Kr-1Kr+1,…,Kh平均查找長度：A(l,r-1)=cost[l][r-1]平均查找長度：A(r1,h)=cost[r-1][h]lhA(l,r-1)A(r+1,h)0n+1(1,n)最終結(jié)果lowhigh下三角部分：l>h,對應(yīng)的子問題是空樹。只需要計(jì)算上三角。Cost[k][k]=pkCost[k][k-1]=000p10p20P30P40P50P60P70p80

0123456780123456789子問題的求解次序For(i=n-1;i>0;i--)For(j=i+1;j<=n;j++)CalculatesA(i,j)設(shè)cost[][]數(shù)組（存放A(l,h),(n+2)*(n+1)）和root[][]數(shù)組（記錄子問題(l,h)的根(n+2)*(n+1)）,prob[](n,存放pi)。動態(tài)規(guī)劃算法：VoidoptimalBST(prob,n,cost,root){for(low=n+1;low>=1;low--)for(high=low-1;high<=n;high++)

destChoice(prob,cost,root,low,high);}VoiddestChoice(prob,cost,root,low,high){if(low>high)

bestCost=0;bestRoot=-1;//空

elsebestCost=MAX;for(r=low;r<=high;r++){

rCost=p(low,high)+cost[low][r-1]+cost[r+1][high];if(rCost<bestCost){

bestCost=rCost;bestRoot=r;}}cost[low][high]=bestCost;root[low][high]=bestRoot;}算法分析：bestChoice():T(l,h)=h-l<noptimalBST

調(diào)用n*n次bestChoice()

所以T(n)=O(n3)根據(jù)root[][]，很容易構(gòu)造出最優(yōu)二叉查找樹（遞歸算法）。子問題（l,h）

1.若l>h:空樹；

2.問題劃分：構(gòu)造子樹（l,h），root[l][h]=k,=>

構(gòu)造子樹

(l,k-1)[LT]和子樹(k+1,h)[RT]3.解的合成：構(gòu)造根Kk

，LT做為左子樹，RT作為右子樹。

13.6貪心法(GreedyAlgorithms)

我們已經(jīng)接觸過的貪心算法有Dijkstra[單源最短路徑]算法和Kruscal算法[最小生成樹]。貪心法在當(dāng)前步驟，只考慮當(dāng)前的最優(yōu)解，而不考慮以后的情況。例8：找?guī)艈栴}：有硬幣1角，6分，1分3種，如何找出1角8分？硬幣數(shù)越少越好。貪心法：步驟1：1個1角，差8分步驟2：1個6分，差2分步驟3：2個1分，結(jié)束；共用4個硬幣。最優(yōu)解是：

3個6分。例9：用貪心算法解決構(gòu)造最優(yōu)二叉查找樹問題。對子問題（l,h），選取kl,kl+1,…kh,中權(quán)最大的kr(l<=r<=h)為根.遞歸算法：遞歸出口：l>h,空樹；問題劃分：在kl,kl+1,…kh,中找出權(quán)最大的kr

，分為子問題（l,r-1）和（r+1,h）;解的合成：kr做根，T(l,r-1)做左子樹，T(r+1,h)做右子樹；數(shù)組key[1…n],p[1…n](key的權(quán))算法：BTNode

bestBST(int

low,inthigh){if(low>high)returnNULL;r=low;for(i=low+1;i<=high;i++)//找最大權(quán)的位置

if(p[i]>p[r])r=i;root=newBTNode(key[r]);//新根

root.lchid=bestBST(low,r-1);

root.rchild=bestBST(r+1,high);returnroot;}例10：Key:ABCDEP2/155/154/151/153/15貪心算法構(gòu)造的二叉查找樹動態(tài)規(guī)劃算法構(gòu)造的BACEDA(n)=5/15+(2/15+4/15)*2+3/15*3+1/15*4=5/15+12/15+9/15+4/15=2CBEDAA(n)=4/15+(5/15+3/15)*2+(2/15+1/15)*3=4/15+16/15+9/15=1.93313.7搜索算法狀態(tài)（Status）:問題在某一時刻的狀態(tài)(屬性值集合)。列11：將A,B放在該網(wǎng)格中，有12種狀態(tài)。狀態(tài)空間（StatusSpace）:所有狀態(tài)的集合。狀態(tài)變遷（產(chǎn)生式）：有一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的規(guī)則。開始狀態(tài)（InitialStatus）：問題的初始狀態(tài)。終止?fàn)顟B(tài)(EndStatus)：問題的目標(biāo)狀態(tài)。例12：4皇后問題：ABABABABABBABABABABABAAB4*4網(wǎng)格狀態(tài)：狀態(tài)空間：16*15*14*12個狀態(tài)開始狀態(tài)：空網(wǎng)格。終止?fàn)顟B(tài)：狀態(tài)變遷：狀態(tài)可達(dá)樹：從初始狀態(tài)開始，按狀態(tài)變遷產(chǎn)生下層狀態(tài)，構(gòu)成的樹，葉結(jié)點(diǎn)是終止?fàn)顟B(tài)或祖先出現(xiàn)過的狀態(tài)。例13：

4皇后問題：問題的求解從根開始，在可達(dá)樹中搜索終止?fàn)顟B(tài)。深度優(yōu)先搜索算法思想：BooleandfsSearch(S){

if(SisinF)returntrue;//F:終止?fàn)顟B(tài)集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited){rslt=dfsSearch(S’);

if(rslt)break;}//去掉此句就是詳盡搜索

}returnrslt;}算法是一邊搜索一邊創(chuàng)建后繼狀態(tài)，而不是先創(chuàng)建狀態(tài)可達(dá)樹，然后再搜索。開始時只有一個初始狀態(tài)。廣度優(yōu)先搜索算法思想：BooleanbfsSearch(S0){

//S0是初始狀態(tài)

Q=newQ(n);Q.entre(S0);while(!Q.empty()){S=Q.out();

if(SisinF)returntrue;//F:終止?fàn)顟B(tài)集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited)Q.entre(S’);}//while

returnfalse;}有界深度優(yōu)先搜索算法思想：如果弧上有權(quán)（默認(rèn)為1），在搜索中從S0到當(dāng)前狀態(tài)S的路徑長度為length(S).給定一個len，搜索到S，其路徑長度大于len，就不再向前搜索，退回上一狀態(tài)。BooleandfsSearch(S，len){

if(SisinF)returntrue;//F:終止?fàn)顟B(tài)集

setStobeVisited;for(eachS’snextstatueS’){S’=generateNext(S);if(S’isnotVisited&&length(S’)<len)returndfsSearch(S’);}returnfalse;}例14：迷宮問題：已知從入口到出口至少有一條路徑的路徑長度不超過len。