算法設(shè)計(jì)與分析課件

算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析課程目的對算法設(shè)計(jì)與分析進(jìn)行一個(gè)較為全面的介紹，使大家具有進(jìn)行簡單的算法設(shè)計(jì)與分析的基本能力先修課程程序設(shè)計(jì)語言數(shù)據(jù)結(jié)構(gòu)高等數(shù)學(xué)離散數(shù)學(xué)概率論2課程目的對算法設(shè)計(jì)與分析進(jìn)行一個(gè)較為全面的介紹，使大家具有進(jìn)主要內(nèi)容介紹第1章 算法引論第2章 遞歸與分治策略第3章 動(dòng)態(tài)規(guī)劃第4章 貪心算法第5章 回溯法第6章 分支限界法第7章 概率算法第8章 NP完全性理論3主要內(nèi)容介紹第1章 算法引論3教學(xué)用書王曉東算法設(shè)計(jì)與分析清華大學(xué)出版社4教學(xué)用書王曉東4T.Cormen,C.Leiserson,R.Rivest,andC.Stein

IntroductiontoAlgorithms,2ndEd.MITPressandMcGraw-HillBookCompany,2001教學(xué)參考書5T.Cormen,C.Leiserson,R.RiD.E.KnuthTheArtofComputerProgramming,Vol.1and3,ThirdEdition,AddisonWesley,1997.6D.E.Knuth6第1章算法引論程序=算法+數(shù)據(jù)結(jié)構(gòu)1.1算法與程序一.算法在計(jì)算機(jī)科學(xué)中的重要地位7第1章算法引論程序=算法+數(shù)據(jù)結(jié)構(gòu)1.1算法與程序一.二. 算法的基本概念一個(gè)有窮規(guī)則的有序集合稱為一個(gè)算法。1.定義.2.算法的特征.輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限?？尚行裕簣?zhí)行每條指令的時(shí)間也有限。8二. 算法的基本概念一個(gè)有窮規(guī)則的有序集合稱為一個(gè)算法。1.例.求正整數(shù)m、n的最大公因數(shù)。解一.（1）求余數(shù)：用m除以n，得余數(shù)r(0≤r﹤n)。（2）判斷余數(shù)：若余數(shù)r=0，輸出n，結(jié)束。否則，轉(zhuǎn)（3）。（3）更新被除數(shù)和除數(shù)：m←n，n←r，轉(zhuǎn)(1)。9例.求正整數(shù)m、n的最大公因數(shù)。解一.（1）求余數(shù)：用m解二.開始輸入m、nr=m%nr=0?m←n，n←r輸出n是否10解二.開始輸入m、nr=m%nr=0?m←n，n←r輸解三.Euclid(intm,intn){intr;while(n!=0){r=m%n;

m=n;

n=r;

}printf(“%d”,m)}11解三.Euclid(intm,intn)113.算法的描述方法.（1）自然語言（2）流程圖（3）程序設(shè)計(jì)語言123.算法的描述方法.（1）自然語言（2）流程圖（3）程序設(shè)計(jì)三. 算法設(shè)計(jì)與分析的步驟1.問題的描述.2.模型的選擇.3.算法設(shè)計(jì)和正確性證明.4.算法的分析.5.算法的實(shí)現(xiàn).13三. 算法設(shè)計(jì)與分析的步驟1.問題的描述.2.模型的選擇.31.2算法復(fù)雜性分析

算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用n、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(n,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，則有：T=T(n,I)和S=S(n,I)

。 （通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）

141.2算法復(fù)雜性分析算法復(fù)雜性是算法運(yùn)最壞情況下的時(shí)間復(fù)雜度：漸近時(shí)間復(fù)雜度：平均情況下的時(shí)間復(fù)雜性：設(shè)Dn是規(guī)模為n的合法輸入的集合；I*是Dn中使T(n,I*)達(dá)到Tmax(n)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。則：n→∞時(shí)，T(n)的主要部分算法共有k種基本步驟，第i種步驟所需時(shí)間ti，出現(xiàn)次數(shù)ei.用問題體積n表示的運(yùn)行時(shí)間T(n)稱為時(shí)間復(fù)雜度15最壞情況下的時(shí)間復(fù)雜度：漸近時(shí)間復(fù)雜度：平均情況下的時(shí)間復(fù)雜算法復(fù)雜度的重要性假設(shè)計(jì)算機(jī)每秒可作1000次基本運(yùn)算16算法復(fù)雜度的重要性假設(shè)計(jì)算機(jī)每秒可作1000次基本運(yùn)算16有效算法最佳算法計(jì)算問題的分類1.無法寫出算法的問題.2.有多項(xiàng)式算法的問題.3.介于上述兩問題之間的問題.17有效算法最佳算法計(jì)算問題的分類1.無法寫出算法的問題.2.有例解用最直觀的方法用Horner算法

Horner(inta[n+1],realx){intp=a[n];

for(i=1;i<=n;i++)p=p*x+a[n-i];returnp;}18例解用最直觀的方法用Horner算法Horner(int表示算法漸近復(fù)雜度的數(shù)學(xué)符號：漸近意義下的記號：O、Ω、θ、o

設(shè)f(n)和g(n)是定義在正數(shù)集上的正函數(shù)。

O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)n

N0時(shí)有f(n)Cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時(shí)上有界，且g(n)是它的一個(gè)上界，記為f(n)=O(g(n))。即f(n)的階不高于g(n)的階。根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：(1)O(f)+O(g)=O(max(f,g))；(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)；(4)如果g=O(f)，則O(f)+O(g)=O(f)；(5)O(Cf)=O(f)，其中C是一個(gè)正的常數(shù)；(6)f=O(f)。

19表示算法漸近復(fù)雜度的數(shù)學(xué)符號：漸近意義下的記號：O、Ω、θ、

Ω的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)n

N0時(shí)有f(n)Cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個(gè)下界，記為f(n)=Ω(g(n))。即f(n)的階不低于g(n)的階。

θ的定義：定義f(n)=θ(g(n))當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)=Ω(g(n))。此時(shí)稱f(n)與g(n)同階。

o的定義：對于任意給定的ε＞0，都存在正整數(shù)N0，使得當(dāng)n

N0時(shí)有f(n)/g(n)

ε,則稱函數(shù)f(n)當(dāng)n充分大時(shí)的階比g(n)低，記為f(n)=o(g(n))。例如，4nlogn+7=o(3n2+4nlogn+7)。

20Ω的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)n第2章遞歸與分治策略

凡治眾如治寡，分?jǐn)?shù)是也。

----孫子兵法21第2章遞歸與分治策略 凡治眾如治寡，分?jǐn)?shù)是也。212.1遞歸的概念直接或間接地調(diào)用自身的較小模式的算法稱為遞歸算法。用函數(shù)自身的較小模式給出其定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，子問題的復(fù)雜度也原問題復(fù)雜度的較小模式，這就為使用遞歸技術(shù)進(jìn)行算法分析提供了方便。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。222.1遞歸的概念直接或間接地調(diào)用自身的較小模式的算法稱為遞例1階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。下面來看幾個(gè)實(shí)例:

factorial(intn){if(n=0)return1;

else

return

factorial(n-1);}T(n)=T(n-1)+1,T(n)=O(n)23例1階乘函數(shù)邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的階乘函數(shù)可以找到相應(yīng)的非遞歸方式定義：

factorial(intn){inti,p=1;

for(i=1;i<=n;i++)p=p*i;returnp;}

循環(huán)n次，故T(n)=n24階乘函數(shù)可以找到相應(yīng)的非遞歸方式定義：factorial例2Fibonacci數(shù)列25例2Fibonacci數(shù)列25Fibonacci數(shù)列的前10項(xiàng)為1，1，2，3，5，8，13，21，34，55，…，它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：

fibonacci(intn){

if(n<=1)return1;

else

return

fibonacci(n-1)+fibonacci(n-2);}T(n)=T(n-1)+T(n-2),T(n)=?26Fibonacci數(shù)列的前10項(xiàng)為1，1，2，3，5，8，1生成函數(shù)法！Fibonacci函數(shù)也可以找到相應(yīng)的非遞歸方式定義：27生成函數(shù)法！Fibonacci函數(shù)也可以找到相應(yīng)的非遞歸方式例3Ackerman函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：Ackerman函數(shù)無法找到非遞歸的定義。28例3Ackerman函數(shù)Ackerman函數(shù)無法找到非遞歸Ackerman函數(shù)A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)：m=0時(shí)，A(n,0)=n+2m=1時(shí)，由A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n>1)，和A(1,1)=2，得A(n,1)=2*nm=2時(shí)，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=。m=3時(shí)，類似的可以推出m=4時(shí)，A(n,4)的增長速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。29Ackerman函數(shù)29定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(n，n)。定義其擬逆函數(shù)α(n)為：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在復(fù)雜度分析中常遇到。對于通常所見到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。3030例4排列的生成問題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R\{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴ri得到的排列。R的全排列可歸納定義如下：

當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素；當(dāng)n>1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構(gòu)成。

31例4排列的生成問題設(shè)R={r1,r2,…,rn}是要進(jìn)行排perm(list[],intk,intm)

{//產(chǎn)生前綴是list[0:k-1],后綴是list[k:m]的所有排列//perm(list,0,n-1)產(chǎn)生list[0:n-1]的去全排列

if(k==m)

{//單元素排列

for(inti=0;i<=m;i++)

cout<<list[i];

cout<<endl;

}

else

{//多元素序列，遞歸產(chǎn)生排列

for(inti=k;i<=m;i++)

{swap(list[k],list[i]);

perm(list,k+1,m);

swap(list[k],list[i]);

}

}

}32perm(list[],intk,intm)

{/例.產(chǎn)生123的所有排列層次棧狀態(tài)(i,k,m)數(shù)組輸出10，0，232121，1，20，0，23213，2，21，1，20，0，232132122，1，20，0，22313，2，22，1，20，0，223123122，1，20，0，232111，0，231221，1，21，0，23123，2，21，1，21，0，231231222，1，21，0，21323，2，22，1，21，0，213213222，1，21，0，231212，0，231221，1，22，0，2213層次棧狀態(tài)(i,k,m)數(shù)組輸出33例.產(chǎn)生123的所有排列層次棧狀態(tài)(i,k,m)數(shù)組輸22，1，22，0，212322，1，22，0，22133，2，21，1，22，0，2213213層次棧狀態(tài)(i,k,m)數(shù)組輸出3，2，22，1，22，0，212312312，0，21230棧空1233422，1，212322，1，22133，2，221321例5整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。例如正整數(shù)6有如下11種不同的劃分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。35例5整數(shù)劃分問題35設(shè)q(n,m)為n的最大加數(shù)n1不大于m的劃分個(gè)數(shù)。則：(1)q(n,1)=1，n≥1;(2)q(n,m)=q(n,n),n≤m;(4)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。(5)q(n,m)=q(n-m,m)+q(n,m-1),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1的劃分組成。(3)q(1,m)=1,m≥1;36設(shè)q(n,m)為n的最大加數(shù)n1不大于m的劃分個(gè)數(shù)。則：(1顯然，正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。

q(intn,intm){if(m=1|n=1)return1;elseif(n<m)returnq(n,n);elseif(n=m)return1+q(n,n-1);elsereturnq(n,m-1)+q(n-m,m);}37顯然，正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。q(int例6Hanoi塔問題設(shè)a,b,c是3個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。38例6Hanoi塔問題38hanoi(intn,inta,intb,intc){//將塔座a上的盤子移到塔座b上，塔座c為輔助塔座

if(n>0){

hanoi(n-1,a,c,b);

move(a,b);

hanoi(n-1,c,b,a);}}39hanoi(intn,inta,intb,int例.描述n=3時(shí),hanoi(n,a,b,c)的運(yùn)行過程。層次棧狀態(tài)塔狀態(tài)13,a,b,ccba32122,a,c,b3,a,b,ccba13231,a,b,c2,a,c,b3,a,b,c層次棧狀態(tài)塔狀態(tài)cba21322,a,c,b3,a,b,ccba23131,c,a,b2,a,c,b3,a,b,c2,a,c,b3,a,b,c240例.描述n=3時(shí),hanoi(n,a,b,c)的運(yùn)層次棧狀態(tài)塔狀態(tài)層次棧狀態(tài)塔狀態(tài)13,a,b,ccba22,b,a,c3,a,b,c321cba23131,b,c,a2,b,a,c3,a,b,ccba31222,b,a,c3,a,b,ccba32131,a,b,c2,b,a,c3,a,b,c41層次棧狀態(tài)塔狀態(tài)層次棧狀態(tài)塔狀態(tài)13,a,b,ccba22,cba32122,b,a,c3,a,b,c層次棧狀態(tài)塔狀態(tài)cba3213,a,b,c1層次棧狀態(tài)塔狀態(tài)cba321?？?42cba32122,b,a,c層次棧狀態(tài)塔狀態(tài)cba3211層遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。43遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明遞歸小結(jié)解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1.采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2.用遞推來實(shí)現(xiàn)遞歸函數(shù)。3.通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。44遞歸小結(jié)解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=將問題分為a個(gè)子問題，對這a個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠小，則每個(gè)子問題再劃分為a個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。2.2分治法的基本思想45nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。分治算法的程序具有遞歸的特點(diǎn)nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)46將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向分治法的適用條件分治法所能解決的問題一般具有以下幾個(gè)特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。47分治法的適用條件分治法所能解決的問題一般具有以下幾個(gè)特征：因分治法的基本步驟divide-and-conquer(P){

if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題

dividePintosmallersubinstancesP1,P2,...,Pa；//分解問題

for(i=1,i<=a,i++)yi=divide-and-conquer(Pi);//遞歸的解各子問題

returnmerge(y1,...,ya);//將各子問題的解合并為原問題的解}人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。即將一個(gè)問題分成大小相等的a個(gè)子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。48分治法的基本步驟divide-and-conquer(P)4分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問題分成a個(gè)規(guī)模為n/b的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為a個(gè)規(guī)模為b的子問題以及用merge將這a個(gè)子問題的解合并為原問題的解需用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于b的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于b的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)bi≤n<bi+1時(shí)，T(bi)≤T(n)<T(bi+1)。49分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問題分成a個(gè)規(guī)模為n5050ifT(n)=aT(n/b)+f(n)thenTheMasterTheorem51ifT(n)=aT(n/b)+f(n)then5252535354542.3二分搜索技術(shù)分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素a[mid]，若x=a[mid]，則x在L中的位置就是mid；如果x<a[mid]，由于a是遞增排序的，因此假如x在a中的話，x必然排在a[mid]的前面，所以我們只要在a[mid]的前面查找x即可；如果x>a[i]，同理我們只要在a[mid]的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。

分析：很顯然此問題分解出的子問題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個(gè)適用條件。給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個(gè)子問題是相互獨(dú)立的。552.3二分搜索技術(shù)分析：如果n=1即只有一個(gè)元素，則只要給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：

BinarySearch(inta[],intx,intn){//在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x時(shí)返回其在數(shù)組中的位置，否則返回-1intleft=0;intright=n-1;

while(left<=right){intmiddle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])left=middle+1;

elseright=middle-1;}

return-1;//未找到x}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(log2n)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(log2n)。例.在中查找6.8765432156給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元2.4大整數(shù)的乘法請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:abcdX=Y=X=a2n/2+bY=c2n/2+d

XY=ac2n+(ad+bc)2n/2+bd

復(fù)雜度分析T(n)=O(n2)

沒有改進(jìn)572.4大整數(shù)的乘法請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n由：XY=ac2n+(ad+bc)2n/2+bd

得：XY=ac2n+((a-b)(d-c)+ac+bd)2n/2+bd或：XY=ac2n+((a+b)(c+d)-ac-bd)2n/2+bd復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)

較大的改進(jìn)細(xì)節(jié)問題：兩個(gè)XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。58由：XY=ac2n+(ad+bc)2n/2+請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)

效率太低分治法:O(n1.59)

較大的改進(jìn)更快的方法??如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時(shí)間內(nèi)解決。是否能找到線性時(shí)間的算法？？？目前為止還沒有結(jié)果。59請?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)2.5Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個(gè)元素所需的計(jì)算時(shí)間為O(n3)傳統(tǒng)方法602.5Strassen矩陣乘法A和B的乘積矩陣C中的元素C使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫為：分治法由此可得：復(fù)雜度分析T(n)=O(n3)

沒有改進(jìn)61使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。對變形復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)

較大的改進(jìn)62為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。對變形復(fù)雜度分析62傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是O(n2.376)是否能找到O(n2)的算法？？？目前為止還沒有結(jié)果。63傳統(tǒng)方法：O(n3)Hopcroft和Kerr已經(jīng)證明(192.6棋盤覆蓋在一個(gè)2k×2k

個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。642.6棋盤覆蓋在一個(gè)2k×2k個(gè)方格組成的棋盤中，恰有一算法當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1

子棋盤(a)所示。特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無特殊方格。為了將這3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤大小為1×1。65算法當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1程序代碼

ChessBoard(inttr,inttc,intdr,intdc,intsize){//tr、tc：棋盤左上角方格的行號、列號//dr、dc：特殊方格的行號、列號

if(size==1)return;intt=tile++;//L型骨牌號，tile初值為1

ints=size/2;//分割棋盤

//用L型骨牌號覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc,dr,dc,s);

else{//特殊方格不在此棋盤中

//用t號L型骨牌覆蓋右下角

board[tr+s-1][tc+s-1]=t;//覆蓋本子棋盤中的其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//用L型骨牌號覆蓋右上角子棋盤

if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc+s,dr,dc,s);

else{//特殊方格不在此棋盤中

//用t號L型骨牌覆蓋左下角

board[tr+s-1][tc+s]=t;//覆蓋本子棋盤中的其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}

//用L型骨牌號覆蓋左下角子棋盤

if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc,dr,dc,s);

else{//用t號L型骨牌覆蓋右上角

board[tr+s][tc+s-1]=t;//覆蓋本子棋盤中的其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//用L型骨牌號覆蓋右下角子棋盤

if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc+s,dr,dc,s);

else{//用t號L型骨牌覆蓋左上角

board[tr+s][tc+s]=t;//覆蓋本子棋盤中的其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}復(fù)雜度分析T(n)=O(4k)漸進(jìn)意義下的最優(yōu)算法66程序代碼ChessBoard(inttr,inttc222chessBoard(0,0,0,1,2)chessBoard(0,0,0,1,1)chessBoard(0,0,0,1,2)1chessBoard(0,0,0,1,1)333chessBoard(0,0,0,1,2)1chessBoard(0,0,0,1,1)444chessBoard(0,0,0,1,2)1chessBoard(0,0,0,1,1)555例chessBoard(0,0,0,1,4)67222chessBoard(0,0,0,1,2)ch2.7合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。MergeSort(inta[],intleft,intright){

if(left<right){//至少有2個(gè)元素

inti=(left+right)/2;//取中點(diǎn)

mergeSort(a,left,i);

mergeSort(a,i+1,right);

merge(a,b,left,i,right);//合并到數(shù)組b

copy(a,b,left,right);//復(fù)制回?cái)?shù)組a}}復(fù)雜度分析T(n)=O(nlogn)漸進(jìn)意義下的最優(yōu)算法682.7合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)A=<5,7,6,1,4,8,3,2>;<5,7,6,1>;<4,8,3,2>;<5,7>;<6,1>;<4,8>;<3,2>;<5>,<6>,<4>,<3>,<5,7>;<1,6>;<4,8>;<2,3>;<1,5,6,7>;<2,3,4,8>;<1,2,3,4,5,6,7,8>;ShowMerge_Sort()runningonthearrayExample<7>;<1>;<8>;<2>;69A=<5,7,6,1,4,8,3,2>;<復(fù)雜度最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)穩(wěn)定性：穩(wěn)定思考題：給定有序表A[1:n]，修改合并排序算法，求出該有序表的逆序?qū)?shù)。70復(fù)雜度最壞時(shí)間復(fù)雜度：O(nlogn)思考題：給定有序表A[2.8快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。qSort(intp,intr){

if(p<r){intq=partition(p,r);//以a[p]為基準(zhǔn)元素將a[p:r]劃分成3段a[p:q-1],a[q]和a[q+1:r]，使得a[p:q-1]中任何元素小于等于a[q]，a[q+1:r]中任何元素大于a[q]。下標(biāo)q在劃分過程中確定。

qSort(p,q-1);//對左半段排序

qSort(q+1,r);//對右半段排序

}}快速排序是對氣泡排序的一種改進(jìn)方法它是由C.A.R.Hoare于1962年提出的712.8快速排序在快速排序中，記錄的比較和交換是從兩端向中間快速排序具有不穩(wěn)定性。函數(shù)partition的代碼{2,5,5,6,7,8}完成partition(intp,intr){inti=p;intj=r+1;intx=a[p];//將<=x的元素交換到左邊區(qū)域

//將>x的元素交換到右邊區(qū)域

while(true){

while(a[++i]<=x);

while(a[--j]>x);

if(i>=j)break;swap(a,i,j);}a[p]=a[j];a[j]=x;

returnj;}{6,7,5,2,5,8}i++j--;初始序列{6,7,5,2,5,8}{6,7,5,2,5,8}j--;{6,5,5,2,7,8}交換i++;i++;i++;j--;{6,5,5,2,7,8}例

用快速排序法將6,7,5,2,5,8排序72快速排序具有不穩(wěn)定性。函數(shù)partition的代碼{2,5randomizedPartition(intp,intr){inti=random(p,r);

swap(a,i,p);

return

partition(p,r);}快速排序的復(fù)雜度快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)穩(wěn)定性：不穩(wěn)定73randomizedPartition(intp,in快速排序時(shí)間復(fù)雜度的分析最壞情況?分割總是最不平衡最好情況?每次將數(shù)組對半分割最可能情況?介于上述兩者之間T(1)=(1)T(n)=T(n-2)+(n)

T(n)=(n2)T(n)=2T(n/2)+(n)T(n)=(nlogn)T(n)=2T(n/b)+(n),b<2T(n)=(nlogn)74快速排序時(shí)間復(fù)雜度的分析最壞情況?T(1)=(1)T(快速排序的平均復(fù)雜度為簡單起見,假定:輸入數(shù)據(jù)互不相等各種分割(0:n-1,1:n-2,2:n-3,…,n-1:0)出現(xiàn)的概率相等(1/n)設(shè)平均復(fù)雜度為T(n)

，則：75快速排序的平均復(fù)雜度為簡單起見,假定:設(shè)平均復(fù)雜度為T(n第二歸納法76第二歸納法76ThusT(n)=O(nlgn)稍后證明77ThusT(n)=O(nlgn)稍后證明77下面證明78下面證明787979各種排序算法的特點(diǎn)歸并排序使用分治思想時(shí)間復(fù)雜度O(nlgn)

非就地排序快速排序采用分治思想平均復(fù)雜度為O(nlgn)

不穩(wěn)定80各種排序算法的特點(diǎn)歸并排序快速排序80排序算法的下界多大?目前為止討論過的排序算法均屬比較排序序信息來源于數(shù)據(jù)的逐對比較定理任何比較排序算法的時(shí)間復(fù)雜度為(nlgn)決策樹81排序算法的下界多大?目前為止討論過的排序算法均屬比較排序81a~ba~ca~cb~cb~ca>ba<bb>cb<ca>ca<ca<ca>cb>cb<coutputc,b,aoutputb,c,aoutputb,a,coutputc,a,boutputa,c,boutputa,b,cExample82a~ba~ca~cb~cb~ca>ba<bb>cb<ca>c設(shè)樹的高度為h，則：

n!

2hlog(n!)

h由Stirling公式:從而:定理具有n！個(gè)葉結(jié)點(diǎn)的決策樹的高度為(nlogn)83設(shè)樹的高度為h，則：

n!2h從而:定理2.9順序統(tǒng)計(jì)給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，要求找出這n個(gè)元素中第k小的元素randomizedSelect(intp,intr,intk){

if(p==r)returna[p];inti=randomizedpartition(p,r);j=i-p+1;//基準(zhǔn)元素a[i]的序數(shù)

if(k<=j)return

randomizedSelect(p,i,k);

else

return

randomizedSelect(i+1,r,k-j);}下面證明:在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間,但在平均情況下，算法randomizedSelect可以在O(n)時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。842.9順序統(tǒng)計(jì)給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤RandomizedSelect()的時(shí)間復(fù)雜度最壞情形:數(shù)組總被分為1:n-1T(n)=T(n-1)+O(n)

=???

=O(n2)

比先排序還差!最好情形:數(shù)組總被分為9:1T(n)=T(9n/10)+O(n)

=???

=O(n) (MasterTheorem)優(yōu)于排序!數(shù)組總被分為99:1會(huì)怎樣?85RandomizedSelect()的時(shí)間復(fù)雜度85平均時(shí)間復(fù)雜度假定要找的元素總落在較大的子數(shù)組中:下面用歸納法證明T(n)=O(n)

86平均時(shí)間復(fù)雜度下面用歸納法證明T(n)=O(n)86設(shè)存在數(shù)c，使得對k<n有：T(k)

ck，則：

87設(shè)存在數(shù)c，使得對k<n有：T(k)ck，則：87如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長度都至少為原數(shù)組長度的ε倍(0<ε<1是某個(gè)正常數(shù))，那么就可以在最壞情況下用O(n)時(shí)間完成選擇任務(wù)。例如，若ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此Master定理可得T(n)=O(n)。尋找基準(zhǔn)元素88如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來找出這n/5

個(gè)元素的中位數(shù)(如果

n/5

是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè))。以這個(gè)元素作為劃分基準(zhǔn)。設(shè)所有元素互不相同。在這種情況下，

n/5個(gè)中位數(shù)中有

≥

(n-5)/10

個(gè)數(shù)大于基準(zhǔn)x。因此，n個(gè)數(shù)中至少有3

(n-5)/10

個(gè)數(shù)大于基準(zhǔn)x。同理，至少有3

(n-5)/10

個(gè)元素小于基準(zhǔn)x。而當(dāng)n≥75時(shí)，

3(n-5)/10

≥n/4。所以，按基準(zhǔn)x劃分所得的2個(gè)子數(shù)組的長度都至少縮短1/4。89將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一select(intp,intr,intk){

if(r-p<75){//用某個(gè)簡單排序算法對數(shù)組a[p:r]排序;

bubbleSort(p,r);

return

a[p+k-1];}//將a[p+5*i]至a[p+5*i+4]的第3小元素

//與a[p+i]交換位置;//找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5

for(inti=0;i<=(r-p-4)/5;i++){ints=p+5*i;t=s+4;

for(intj=0;j<3;j++)bubble(s,t-j);//冒泡3次即可找到第3小元素

swap(a,p+i,s+2);}x=select(p,p+(r-p-4)/5,(r-p+6)/10);//(r-p+6)/10=[p+p+(r-p-4)/5]/2+1,T(n/5)inti=partition(p,r,x),j=i-p+1;

if(k<=j)return

select(p,i,k);//T(3n/4)

elsereturnselect(i+1,r,k-j);}復(fù)雜度分析T(n)≦20Cn=O(n)上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這兩點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/5+3n/4=19n/20=εn，0<ε<1。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。90select(intp,intr,intk)復(fù)雜度第3章動(dòng)態(tài)規(guī)劃Thosewhocannotrememberthepastaredoomedtorepeatit.-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)91第3章動(dòng)態(tài)規(guī)劃Thosewhocannotremem算法總體思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，而問題的解可用子問題的解表示，即要解決的問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=92算法總體思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。在用分治法求解時(shí)，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。如果能夠保存已解決的子問題的答案，而在需要時(shí)直接使用已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)算法總體思想93但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。在用分治法求解時(shí)，動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。94動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。94矩陣連乘問題給定n個(gè)矩陣，其中與是可乘的，。考察這n個(gè)矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少?16000,10500,36000,87500,34500設(shè)有四個(gè)矩陣它們的維數(shù)分別是：總共有五中完全加括號的方式:95矩陣連乘問題給定n個(gè)矩陣，其中窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。

算法復(fù)雜度分析：對于n個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號方式都可以分解為兩個(gè)子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：生成函數(shù)法！矩陣連乘問題的解96窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)動(dòng)態(tài)規(guī)劃方法將矩陣連乘積簡記為A[i:j]，這里i≤j

考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j

，則其相應(yīng)完全加括號方式為計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量，再加上A[i:k]和A[k+1:j]相乘的計(jì)算量97動(dòng)態(tài)規(guī)劃方法將矩陣連乘積簡記為分析最優(yōu)解的結(jié)構(gòu)特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。98分析最優(yōu)解的結(jié)構(gòu)特征：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當(dāng)i=j時(shí)，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i<j時(shí)，故可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能99建立遞歸關(guān)系設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少計(jì)算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有由此可見，在遞歸計(jì)算時(shí)，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法100計(jì)算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不matrixChain(intn,intp[n+1],intm[n+1][n+1],ints[n+1][n+1]){

for(inti=1;i<=n;i++)m[i][i]=0;//填主對角線d1

for(intr=2;r<=n;r++)//填次對角線dr(r=2~n)

for(inti=1;i<=n-r+1;i++){//填次對角線的各個(gè)元素intj=i+r-1;//計(jì)算次對角線dr上第i行的元素的列標(biāo)m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//用計(jì)算Ai(Ai+1…Aj)的次數(shù)作為m[i][j]的初始值s[i][j]=i;//保存分界點(diǎn)

for(intk=i+1;k<j;k++){//用m[i][k]和m[k+1][j]計(jì)算m[i][j]的新值intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}

}}算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計(jì)算時(shí)間上界為O(n3)。算法所占用的空間顯然為O(n2)。用動(dòng)態(tài)規(guī)劃法求最優(yōu)解的程序101matrixChain(intn,intp[n+1],m[1,5]m[1,4]m[1,3]m[1,2]m[1,1]m[2,5]m[2,4]m[2,3]m[2,2]m[4,5]m[4,4]m[5,5]m[3,3]m[3,3]m[3,3]01200168240024864024003486203202000例p0=5,p1=10,p2=4,p3=6,p4=10,p5=2102012001682400248640240034862032recurMatrixChain(inti,intj){

if(i==j)return0;

intu=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];//用計(jì)算Ai(Ai+1…Aj)的次數(shù)作為m[i][j]的初始值s[i][j]=i;//保存分界點(diǎn)

for(intk=i+1;k<j;k++){//用m[i][k]和m[k+1][j]計(jì)算m[i][j]的新值intt=recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];

if(t<u){u=t;s[i][j]=k;}

}

returnu;}計(jì)算A[1:4]的遞歸樹動(dòng)態(tài)規(guī)劃算法與直接遞歸的比較103recurMatrixChain(inti,intj)備忘錄方法memorizedMatrixChain(intn){for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)m[i][j]=0;returnlookupChain(inti,intj);}lookupChain(inti,intj){

if(m[i][j]>0)returnm[i][j];

if(i==j)return0;intu=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;

for(intk=i+1;k<j;k++){intt=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];

if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;

returnu;}備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過的子問題建立了備忘錄以備需要時(shí)查看，避免了相同子問題的重復(fù)求解。104備忘錄方法memorizedMatrixChain(int最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的一個(gè)子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

105最長公共子序列若給定序列X={x1,x2,…,xm}，則另一最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。(2)若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。106最長公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y=子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。