遞歸與分治策略課件

第九章:遞歸與分治策略

1

第九章:遞歸與分治策略

1

學(xué)習(xí)要點:理解遞歸的概念。掌握設(shè)計有效算法的分治策略。通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。二分搜索技術(shù)；大整數(shù)乘法；Strassen矩陣乘法；棋盤覆蓋；合并排序和快速排序；線性時間選擇；最接近點對問題；循環(huán)賽日程表。遞歸與分治策略2學(xué)習(xí)要點:遞歸與分治策略2將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。算法總體思想nT(n/4)T(n/4)T(n/4)T(n/4)T(n)=

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。3將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。算法總體算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。4算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠算法總體思想分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

5算法總體思想分治法的設(shè)計思想是，將一個難以直接解決的大問題，遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。6遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身遞歸的概念例1階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。7遞歸的概念例1階乘函數(shù)邊界條件遞歸方程邊界條件與遞歸方程遞歸的概念例2Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數(shù)可遞歸地計算如下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}8遞歸的概念例2Fibonacci數(shù)列邊界條件遞歸方程第n遞歸的概念例3Ackerman函數(shù)當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：9遞歸的概念例3Ackerman函數(shù)9遞歸的概念例3Ackerman函數(shù)前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義：本例中的Ackerman函數(shù)卻無法找到非遞歸的定義。10遞歸的概念例3Ackerman函數(shù)本例中的Ackerma遞歸的概念例3Ackerman函數(shù)A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)：M=0時，A(n,0)=n+2M=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時，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)=2^n。M=3時，類似的可以推出M=4時，A(n,4)的增長速度非常快，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。11遞歸的概念例3Ackerman函數(shù)11遞歸的概念例3Ackerman函數(shù)定義單變量的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的增加，它以難以想象的慢速度趨向正無窮大。12遞歸的概念例3Ackerman函數(shù)12遞歸的概念例4排列問題設(shè)計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：

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

13遞歸的概念例4排列問題設(shè)R={r1,r2,…,r遞歸的概念例5整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個數(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。14遞歸的概念例5整數(shù)劃分問題例如正整數(shù)6有如下11種不同的(2)q(n,m)=q(n,n),mn;最大加數(shù)n1實際上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤n-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。遞歸的概念例5整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。15(2)q(n,m)=q(n,n),mn;(1)q(n,遞歸的概念例5整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。

16遞歸的概念例5整數(shù)劃分問題正整數(shù)n的劃分?jǐn)?shù)p(n)=q(遞歸的概念例6Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。17遞歸的概念例6Hanoi塔問題17在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。遞歸的概念例6Hanoi塔問題

voidhanoi(intn,inta,intb,intc){

if(n>0){

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

move(a,b);

hanoi(n-1,c,b,a);}}18在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。19遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)20解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。遞分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。21分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：因divide-and-conquer(P){

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

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

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

returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解

}分治法的基本步驟人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。22divide-and-conquer(P)分治法的基本步驟人分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。

23分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較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ī)模縮小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。

分析：很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。24分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。25二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)

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

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

abcd復(fù)雜度分析T(n)=O(n2)沒有改進(jìn)26大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd

為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)較大的改進(jìn)細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。27大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)效率太低分治法:O(n1.59)較大的改進(jìn)更快的方法??如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法。28大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個元素所需的計算時間為O(n3)傳統(tǒng)方法：O(n3)29Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,jStrassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)30Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)較大的改進(jìn)31Strassen矩陣乘法傳統(tǒng)方法：O(n3)為了降低時間復(fù)雜Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是O(n2.376)是否能找到O(n2)的算法？32Strassen矩陣乘法傳統(tǒng)方法：O(n3)Hopcroft棋盤覆蓋在一個2k×2k

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

子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。

34棋盤覆蓋當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×棋盤覆蓋voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌號

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

//覆蓋左上角子棋盤

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);}//覆蓋右上角子棋盤

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);}//覆蓋左下角子棋盤

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);}//覆蓋右下角子棋盤

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)算法35棋盤覆蓋voidchessBoard(inttr,in合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。voidMergeSort(Typea[],intleft,intright){

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

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

mergeSort(a,left,i);

mergeSort(a,i+1,right);

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

copy(a,b,left,right);//復(fù)制回數(shù)組a}}復(fù)雜度分析T(n)=O(nlogn)漸進(jìn)意義下的最優(yōu)算法36合并排序基本思想：將待排序元素分成大小大致相同的2個子集合，合并排序算法mergeSort的遞歸過程可以消去。初始序列[49][38][65][97][76][13][27][3849][6597][1376][27]第一步第二步[38496597][132776]第三步[13273849657697]37合并排序算法mergeSort的遞歸過程可以消去。初始序列[合并排序最壞時間復(fù)雜度：O(nlogn)平均時間復(fù)雜度：O(nlogn)輔助空間：O(n)38合并排序最壞時間復(fù)雜度：O(nlogn)38快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。template<classType>voidQuickSort(Typea[],intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);//對左半段排序

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

}}39快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行快速排序template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//將<x的元素交換到左邊區(qū)域

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

while(true){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}初始序列{6,7,5,2,5,8}j--;{5,7,5,2,6,8}i++;{5,6,5,2,7,8}j--;{5,2,5,6,7,8}i++;完成{6,7,5,2,5,8}{5,2,5}6{7,8}40快速排序template<classType>初始序列{6template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}快速排序

快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可以在a[p:r]中隨機(jī)選出一個元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。最壞時間復(fù)雜度：O(n2)平均時間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)41template<classType>快速排序快速線性時間選擇給定線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r)returna[p];inti=RandomizedPartition(a,p,r),j=i-p+1;if(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}在最壞情況下，算法randomizedSelect需要O(n2)計算時間,但可以證明，算法randomizedSelect可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。42線性時間選擇給定線性序集中n個元素和一個整數(shù)k，1≤k≤線性時間選擇如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的ε倍(0<ε<1是某個正常數(shù))，那么就可以在最壞情況下用O(n)時間完成選擇任務(wù)。例如，若ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。43線性時間選擇如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個。遞歸調(diào)用select來找出這n/5個元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分基準(zhǔn)。線性時間選擇設(shè)所有元素互不相同。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個元素大，因為在每一組中有2個元素小于本組的中位數(shù)，而n/5個中位數(shù)中又有(n-5)/10個小于基準(zhǔn)x。同理，基準(zhǔn)x也至少比3(n-5)/10個元素小。而當(dāng)n≥75時，3(n-5)/10≥n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4。44將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一TypeSelect(Typea[],intp,intr,intk){if(r-p<75){

用某個簡單排序算法對數(shù)組a[p:r]排序;returna[p+k-1];};for(inti=0;i<=(r-p-4)/5;i++)

將a[p+5*i]至a[p+5*i+4]的第3小元素與a[p+i]交換位置;//找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}復(fù)雜度分析T(n)=O(n)上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點。這2點保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=εn，0<ε<1。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。線性時間選擇45TypeSelect(Typea[],intp,i最接近點對問題給定平面上n個點的集合S，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。為了使問題易于理解和分析，先來考慮一維的情形。此時，S中的n個點退化為x軸上的n個實數(shù)x1,x2,…,xn。最接近點對即為這n個實數(shù)中相差最小的2個實數(shù)。假設(shè)我們用x軸上某個點m將S劃分為2個子集S1和S2，基于平衡子問題的思想，用S中各點坐標(biāo)的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對{p1,p2}和{q1,q2}，并設(shè)d=min{|p1-p2|,|q1-q2|}，S中的最接近點對或者是{p1,p2}，或者是{q1,q2}，或者是某個{p3,q3}，其中p3∈S1且q3∈S2。能否在線性時間內(nèi)找到p3,q3？46最接近點對問題給定平面上n個點的集合S，找其中的一對點，使得最接近點對問題如果S的最接近點對是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于d），并且m是S1和S2的分割點，因此(m-d,m]中至多包含S中的一個點。由圖可以看出，如果(m-d,m]中有S中的點，則此點就是S1中最大點。因此，我們用線性時間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。能否在線性時間內(nèi)找到p3,q3？47最接近點對問題如果S的最接近點對是{p3,q3}，即|p最接近點對問題下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=min{d1,d2}，S中的最接近點對或者是d，或者是某個{p,q}，其中p∈P1且q∈P2。能否在線性時間內(nèi)找到p,q？48最接近點對問題下面來考慮二維的情形。選取一垂直線l:x=m來最接近點對問題考慮P1中任意一點p，它若與P2中的點q構(gòu)成最接近點對的候選者，則必有distance(p，q)＜d。滿足這個條件的P2中的點一定落在一個d×2d的矩形R中.由d的意義可知，P2中任何2個S中的點的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點。因此，在分治法的合并步驟中最多只需要檢查6×n/2=3n個候選者.能否在線性時間內(nèi)找到p3,q3？證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導(dǎo)出6個(d/2)×(2d/3)的矩形。若矩形R中有多于6個S中的點，則由鴿舍原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點。設(shè)u，v是位于同一小矩形中的2個點，則distance(u,v)<d。這與d的意義相矛盾。49最接近點對問題考慮P1中任意一點p，它若與P2中的點q構(gòu)為了確切地知道要檢查哪6個點，可以將p和P2中所有S2的點投影到垂直線l上。由于能與p點一起構(gòu)成最接近點對候選者的S2中點一定在矩形R中，所以它們在直線l上的投影點距p在l上投影點的距離小于d。由上面的分析可知，這種投影點最多只有6個。因此，若將P1和P2中所有S中點按其y坐標(biāo)排好序，則對P1中所有點，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者。對P1中每一點最多只要檢查P2中排好序的相繼6個點。最接近點對問題50為了確切地知道要檢查哪6個點，可以將p和P2中所有S2的點投最接近點對問題doublecpair2(S){n=|S|;

if(n<2)return;1、m=S中各點x間坐標(biāo)的中位數(shù);

構(gòu)造S1和S2；

//S1={p∈S|x(p)<=m},S2={p∈S|x(p)>m}2、d1=cpair2(S1);d2=cpair2(S2);3、dm=min(d1,d2);4、設(shè)P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點組成的集合；

P2是S2中距分割線l的距離在dm之內(nèi)所有點組成的集合；將P1和P2中點依其y坐標(biāo)值排序；并設(shè)X和Y是相應(yīng)的已排好序的點列；5、通過掃描X以及對于X中每個點檢查Y中與其距離在dm之內(nèi)的所有點(最多6個)可以完成合并；當(dāng)X中的掃描指針逐次向上移動時，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動；設(shè)dl是按這種掃描方式找到的點對間的最小距離；6、d=min(dm,dl);returnd;}復(fù)雜度分析T(n)=O(nlogn)51最接近點對問題doublecpair2(S)4、設(shè)P1是S循環(huán)賽日程表設(shè)計一個滿足以下要求的比賽日程表：(1)每個選手必須與其他n-1個選手各賽一次；(2)每個選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。按分治策略，將所有的選手分為兩半，n個選手的比賽日程表就可以通過為n/2個選手設(shè)計的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進(jìn)行比賽就可以了。123456782143658734127856432187655678123465872143785634128765432152循環(huán)賽日程表設(shè)計一個滿足以下要求的比賽日程表：按分治策略，將

第九章:遞歸與分治策略

53

第九章:遞歸與分治策略

1

學(xué)習(xí)要點:理解遞歸的概念。掌握設(shè)計有效算法的分治策略。通過下面的范例學(xué)習(xí)分治策略設(shè)計技巧。二分搜索技術(shù)；大整數(shù)乘法；Strassen矩陣乘法；棋盤覆蓋；合并排序和快速排序；線性時間選擇；最接近點對問題；循環(huán)賽日程表。遞歸與分治策略54學(xué)習(xí)要點:遞歸與分治策略2將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。算法總體思想nT(n/4)T(n/4)T(n/4)T(n/4)T(n)=

對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。55將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。算法總體算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。nT(n)=n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)n/4T(n/16)T(n/16)T(n/16)T(n/16)將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。56算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠算法總體思想分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

57算法總體思想分治法的設(shè)計思想是，將一個難以直接解決的大問題，遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。58遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身遞歸的概念例1階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。59遞歸的概念例1階乘函數(shù)邊界條件遞歸方程邊界條件與遞歸方程遞歸的概念例2Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，……，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個Fibonacci數(shù)可遞歸地計算如下：intfibonacci(intn){

if(n<=1)return1;

return

fibonacci(n-1)+fibonacci(n-2);}60遞歸的概念例2Fibonacci數(shù)列邊界條件遞歸方程第n遞歸的概念例3Ackerman函數(shù)當(dāng)一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：61遞歸的概念例3Ackerman函數(shù)9遞歸的概念例3Ackerman函數(shù)前2例中的函數(shù)都可以找到相應(yīng)的非遞歸方式定義：本例中的Ackerman函數(shù)卻無法找到非遞歸的定義。62遞歸的概念例3Ackerman函數(shù)本例中的Ackerma遞歸的概念例3Ackerman函數(shù)A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)：M=0時，A(n,0)=n+2M=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時，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)=2^n。M=3時，類似的可以推出M=4時，A(n,4)的增長速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。63遞歸的概念例3Ackerman函數(shù)11遞歸的概念例3Ackerman函數(shù)定義單變量的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的增加，它以難以想象的慢速度趨向正無窮大。64遞歸的概念例3Ackerman函數(shù)12遞歸的概念例4排列問題設(shè)計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個元素，Ri=R-{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：

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

65遞歸的概念例4排列問題設(shè)R={r1,r2,…,r遞歸的概念例5整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個數(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。66遞歸的概念例5整數(shù)劃分問題例如正整數(shù)6有如下11種不同的(2)q(n,m)=q(n,n),mn;最大加數(shù)n1實際上不能大于n。因此，q(1,m)=1。(1)q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即

(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤n-1的劃分組成。(3)q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1≤n-1的劃分組成。遞歸的概念例5整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。67(2)q(n,m)=q(n,n),mn;(1)q(n,遞歸的概念例5整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。

68遞歸的概念例5整數(shù)劃分問題正整數(shù)n的劃分?jǐn)?shù)p(n)=q(遞歸的概念例6Hanoi塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。69遞歸的概念例6Hanoi塔問題17在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n＞1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。遞歸的概念例6Hanoi塔問題

voidhanoi(intn,inta,intb,intc){

if(n>0){

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

move(a,b);

hanoi(n-1,c,b,a);}}70在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。71遞歸小結(jié)優(yōu)點：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)72解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。遞分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。73分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：因divide-and-conquer(P){

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

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

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

returnmerge(y1,...,yk);//將各子問題的解合并為原問題的解

}分治法的基本步驟人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。74divide-and-conquer(P)分治法的基本步驟人分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：通過迭代法求得方程的解：注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。

75分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為n分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較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小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。

分析：很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。分析：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是相互獨立的。76分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：template<classType>intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x<a[m])r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運算需要O(1)時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn)。77二分搜索技術(shù)給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)

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

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

abcd復(fù)雜度分析T(n)=O(n2)沒有改進(jìn)78大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)效率太低分治法:XY=ac2n+(ad+bc)2n/2+bd

為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bdXY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd復(fù)雜度分析T(n)=O(nlog3)=O(n1.59)較大的改進(jìn)細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。79大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)效率太低分治法:O(n1.59)較大的改進(jìn)更快的方法??如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法。80大整數(shù)的乘法請設(shè)計一個有效的算法，可以進(jìn)行兩個n位大整數(shù)的Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個元素所需的計算時間為O(n3)傳統(tǒng)方法：O(n3)81Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,jStrassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)82Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)較大的改進(jìn)83Strassen矩陣乘法傳統(tǒng)方法：O(n3)為了降低時間復(fù)雜Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是O(n2.376)是否能找到O(n2)的算法？84Strassen矩陣乘法傳統(tǒng)方法：O(n3)Hopcroft棋盤覆蓋在一個2k×2k

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

子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。

86棋盤覆蓋當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×棋盤覆蓋voidchessBoard(inttr,inttc,intdr,intdc,intsize){

if(size==1)return;intt=tile++,//L型骨牌號

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

//覆