第2章遞歸與分治策略

1、第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 對這k個子問題分別求解。如果子

2、問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。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) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來

3、問題的解。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)第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。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、4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分而治之。凡治眾如治寡，分?jǐn)?shù)是也。凡治眾如治寡，分?jǐn)?shù)是也。-孫子兵法孫子兵法第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍2.1 直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技

5、術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。下面來看幾個實例。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍2.1 例例1 1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。第第2章章 遞歸與分治

6、策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件邊界條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個Fibonacci數(shù)可遞歸地計算如下：public static int fibonacci(int n) if (n 1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 第第2章章 遞歸與分治策略遞歸與分治

7、策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍2.1 例例5 5 整數(shù)劃分問題整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。正整數(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。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍(2) q(n,m)=q(n,n),mn;最

8、大加數(shù)n1實際上不能大于n。因此，q(1,m)=1。(1) q(n,1)=1,n1;當(dāng)最大加數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式，即nn111 (4) q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。2.1 例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個

9、自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq2.1 例例5 5 整數(shù)劃分問題整數(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)系。正

10、整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍2.1 例例6 Hanoi6 Hanoi塔問題塔問題設(shè)a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則1：每次只能移動1個圓盤；規(guī)則2：任何時刻都不允許將較大的圓盤壓在較

11、小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍在問題規(guī)模較大時，較難找到一般的方法，因此我們嘗試用遞歸技術(shù)來解決這個問題。當(dāng)n=1時，問題比較簡單。此時，只要將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時，需要利用塔座c作為輔助塔座。此時若能設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤依照移動規(guī)則從塔座c移至塔座b。由此可見，n個圓盤的移動問題可分為2次n

12、-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。2.1 例例6 Hanoi6 Hanoi塔問題塔問題 public static void hanoi(int n, int a, int b, int c) if (n 1) hanoi(n-1, a, c, b); move(n,a,c); hanoi(n-1, b, a, c); else move(n,a,c); 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納結(jié)構(gòu)清晰，可讀性強(qiáng)，

13、而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。試程序帶來很大方便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計算時間還是占用的存儲空間都比非遞歸算法要多。算時間還是占用的存儲空間都比非遞歸算法要多。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍解決方法：解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法?；癁榉沁f歸算法。1.1.采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用采用一個用戶

14、定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。效果不明顯。2.2.用遞推來實現(xiàn)遞歸函數(shù)。用遞推來實現(xiàn)遞歸函數(shù)。3.3.通過通過CooperCooper變換、變換、反演變換能反演變換能將一些遞歸轉(zhuǎn)化將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時空復(fù)雜度上均有較大改善，后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工

15、學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題，即該該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問題分解出的子問題的解可以合并為該問題的利用該問題分解出的子問題的解可以合并為該問題的解；解； 該問題所分解出的各個子問題是相互獨(dú)立的，即子問該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。題之間不包含公共的子問題。 因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個

16、特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法貪心算法或動態(tài)規(guī)劃動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃動態(tài)規(guī)劃較好。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題

17、 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡平衡(balancing)子問題子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。第第2章章 遞歸與分治策略遞歸與分治策略 四川

18、理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有：11)()/() 1 ()(nnnfmnkTOnT通過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)

19、的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時，T(mi)T(n)T(mi+1)。 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個

20、適用條件。 分析：很顯然此問題分解出的子問題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析： 該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題該問題可以分解為若干個規(guī)模較小的相同問題; 分解出的子問題的解可以合并為原問題的解；分解出的子問題的解可以合并為原問題的解； 分解出的各個子問題是相互獨(dú)立的。分解出的各個子問題是相互獨(dú)立的

21、。 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x時返回其在數(shù)組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left amiddle

22、) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法復(fù)雜度分析：算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn) 。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 請設(shè)計一個有效的算法，可以進(jìn)行兩個請設(shè)計一個有效的算法，可以進(jìn)行兩個n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算u小學(xué)的

23、方法：O(n2) 效率太低u分治法: abcd復(fù)雜度分析復(fù)雜度分析T(n)=O(n2) 沒有改進(jìn)沒有改進(jìn)11)()2/(4) 1 ()(nnnOnTOnTX = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 請設(shè)計一個有效的算法，可以進(jìn)行兩個請設(shè)計一個有效的算法，可以進(jìn)行兩個n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算u小學(xué)的方法：O(n2) 效率太低u分治法: XY = ac 2n + (ad+bc) 2

24、n/2 + bd 為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd1. XY = ac 2n + (a+b)(d+c)-ac-bd) 2n/2 + bd復(fù)雜度分析復(fù)雜度分析T(n)=O(nlog3) =O(n1.59) 較大的改進(jìn)較大的改進(jìn)11)()2/(3) 1 ()(nnnOnTOnT細(xì)節(jié)問題細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案

25、 楊維劍 請設(shè)計一個有效的算法，可以進(jìn)行兩個請設(shè)計一個有效的算法，可以進(jìn)行兩個n n位大整數(shù)的乘法運(yùn)算位大整數(shù)的乘法運(yùn)算u小學(xué)的方法：O(n2) 效率太低u分治法: O(n1.59) 較大的改進(jìn)u更快的方法?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導(dǎo)致了快速傅利葉變換快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內(nèi)解決。是否能找到線性時間的算法？目前為止還沒有結(jié)果。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍

26、楊維劍算法分析與設(shè)計教案 楊維劍A和B的乘積矩陣C中的元素Ci,j定義為: nkjkBkiAjiC1若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個元素所需的計算時間為O(n3)u傳統(tǒng)方法：O(n3)第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：u傳統(tǒng)方法：O(n3)u分治法:222112112221121122211211BBBBAAAACCCC由此可得：211

27、2111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC復(fù)雜度分析復(fù)雜度分析T(n)=O(n3) 沒有改進(jìn)沒有改進(jìn)22)()2/(7) 1 ()(2nnnOnTOnT第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍u傳統(tǒng)方法：O(n3)u分治法:為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115

28、BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC復(fù)雜度分析復(fù)雜度分析T(n)=O(nlog7) =O(n2.81) 較大的改進(jìn)較大的改進(jìn)22)()2/(8) 1 ()(2nnnOnTOnT第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍u傳統(tǒng)方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcroft和Kerr已經(jīng)證明(1971)，計算2個矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算

29、22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是 O(n2.376)是否能找到O(n2)的算法？目前為止還沒有結(jié)果。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍在一個2k2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。第第2章章 遞歸與分治策略遞歸與分治

30、策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍當(dāng)k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。 第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍 public void chessBoard(int tr, int tc, int d

31、r, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號 s = size/2; / 分割棋盤 / 覆蓋左上角子棋盤 if (dr tr + s & dc tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤 if (dr

32、 = tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號L型骨牌覆蓋左下角 boardtr + s - 1tc + s = t; / 覆蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆蓋左下角子棋盤 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號L型骨牌覆蓋左上角 bo

33、ardtr + stc + s = t; / 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 復(fù)雜度分析復(fù)雜度分析T(n)=O(4k) 漸進(jìn)意義下的最優(yōu)算法00) 1 () 1(4) 1 ()(kkOkTOkT第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍基本思想：基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 public static void mergeSort(Comparable a, int lef

34、t, int right) if (leftright) /至少有2個元素 int i=(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ù)制回數(shù)組a 復(fù)雜度分析復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法11)()2/(2) 1 ()(nnnOnTOnT第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍算法me

35、rgeSort的遞歸過程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍&最壞時間復(fù)雜度：最壞時間復(fù)雜度：O(nlogn)&平均時間復(fù)雜度：平均時間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)&穩(wěn)定性：穩(wěn)定穩(wěn)定性：穩(wěn)定思考題：思考題：給定給定有序表有序表A1:n，修，修改合并排序算法，求出該有序表改合并

36、排序算法，求出該有序表的逆序?qū)?shù)。的逆序?qū)?shù)。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。private static void qSort(int p, int r) if (p= x的元素交換到左邊區(qū)域 / 將= x的元素交換到右邊區(qū)域 while (true) while (a+pareTo(x) 0); if (i = j) break; My

37、Math.swap(a, i, j); ap = aj; aj = x; return j; 初始序列6, 7, 5, 2, 5, 8j-;ji5, 7, 5, 2, 6, 8i+;ji5, 6, 5, 2, 7, 8j-;ji5, 2, 5, 6, 7, 8i+;ji完成快速排序具有不穩(wěn)定性不穩(wěn)定性。6, 7, 5, 2, 5, 85, 2, 5 6 7, 8第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍private static int randomizedPartition (int p, int r) int i = ran

38、dom(p,r); MyMath.swap(a, i, p); return partition (p, r); 快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可以在ap:r中隨機(jī)選出一個元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。&最壞時間復(fù)雜度：最壞時間復(fù)雜度：O(n2)&平均時間復(fù)雜度：平均時間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)或或O(logn)&穩(wěn)定性：不穩(wěn)定穩(wěn)定性：不穩(wěn)定第第2章章 遞

39、歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=randomizedpartition(p,r), j=i-p+1; if (k=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); 在最壞情況下，算法ra

40、ndomizedSelect需要O(n2)計算時間但可以證明，算法randomizedSelect可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的倍(01是某個正常數(shù))，那么就可以在最壞情況下在最壞情況下用O(n)時間完成選擇任務(wù)。例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n

41、) 。由此可得T(n)=O(n)。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍l將n個輸入元素劃分成n/5個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個。l遞歸調(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)

42、x也至少比3(n-5)/10個元素小。而當(dāng)n75時，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍private static Comparable select (int p, int r, int k) if (r-p5) /用某個簡單排序算法對數(shù)組ap:r排序; bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素 /與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5 fo

43、r ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4; for (int j=0;j3;j+) bubble(s,t-j); MyMath.swap(a, p+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); 復(fù)雜度分析復(fù)雜度分析T(n)=O(n)7575)4/3()5/()(21nnnT

44、nTnCCnT上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍給定平面上n個點(diǎn)的集合S，找其中的一對點(diǎn)，使得在n個點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。 u為了使問題易于理解和分析，先來考慮一維一維的情形。此時，S中的n個點(diǎn)退化為x軸上的n個實數(shù) x1,x2,xn。最接近點(diǎn)對即為這n個實數(shù)中相差最小的2個實數(shù)。

45、假設(shè)我們用x軸上某個點(diǎn)m將S劃分為2個子集S1和S2 ，基于平衡子問題平衡子問題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點(diǎn)對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍u如果S的最接近點(diǎn)對是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過d，即p3(m-d,m，q3(

46、m,m+d。u由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個點(diǎn)。由圖可以看出，如果如果(m-d,m中有中有S中的點(diǎn)，則此點(diǎn)就是中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。中最大點(diǎn)。u因此，我們用線性時間就能找到區(qū)間(m-d,m和(m,m+d中所有點(diǎn)，即p3和q3。從而我們用線性時間就可以將從而我們用線性時間就可以將S1的解和的解和S2的解合并成為的解合并成為S的解的解。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍u下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點(diǎn)對或者是d，或者是某個p,q，其中pP1且qP2。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p,q？第第2章章 遞歸與分治策略遞歸與分治策略 四川理工學(xué)院四川理工學(xué)院 楊維劍楊維劍算法分析與設(shè)計教案 楊維劍u考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對的候選者，則必有distance(p，q)d。滿足這個