第2章遞歸與分治策略

1、 將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。 對這k個子問題分別求解。如果子問題的規(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

2、)T(n/4) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。 將求出的小規(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)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(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(

3、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) 分治法的設(shè)計思想是，將一個難以直接解決的大問題，分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分而治之。凡治眾如治寡，分?jǐn)?shù)是也。凡治眾如治寡，分?jǐn)?shù)是也。-孫子兵法孫子兵法2.1 2.1 直接或間接地調(diào)用自身的算法稱為遞歸算法遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)遞歸函數(shù)。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，

4、反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。 分治與遞歸像一對孿生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。下面來看幾個實例。2.1 2.1 例例1 1 階乘函數(shù)階乘函數(shù)階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊界條件邊界條件遞歸方程遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。2.1 2.1 例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonac

5、ci數(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.1 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

6、，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) 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只有一種劃分形式，即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 2.1 例例5 5 整數(shù)

7、劃分問題整數(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)系。11, 1),() 1,() 1,(1),(1),(mnmnmnmnmmnqmnqnnqnnqmnq2.1 2.1 例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個自變量：將最大

8、加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 2.1 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：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。在問題規(guī)模較大時，較難找到一般的方

9、法，因此我們嘗試用遞歸技術(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-1個圓盤的移動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。2.1 2.1 例例6 Hanoi6 Hanoi塔問題塔問題 public static void hanoi(int n, i

10、nt a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 優(yōu)點：優(yōu)點：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。調(diào)試程序帶來很大方便。缺點：缺點：遞歸算法的運行效率較低，無論是耗費的遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法計算時間還是占用的存儲空間都比非遞歸算法要多。要多。 該問題的規(guī)模縮小到一定的程度就可以容易地解決；

11、該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題，即該該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問題分解出的子問題的解可以合并為該問題的利用該問題分解出的子問題的解可以合并為該問題的解；解； 該問題所分解出的各個子問題是相互獨立的，即子問該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。題之間不包含公共的子問題。 因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加，因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否

12、利用分治法完全取決于問題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法貪心算法或動態(tài)規(guī)劃動態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題，此時雖然也可用分治法，但一般用動態(tài)規(guī)劃動態(tài)規(guī)劃較好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞

13、歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 人們從大量實踐中發(fā)現(xiàn)，在用分治法設(shè)計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡平衡(balancing)子問題子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治

14、法解規(guī)模為|P|=n的問題所需的計算時間，則有：11)()/() 1 ()(nnnfmnkTOnT通過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT注意注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時，T(mi)T(n)1 解：T(n)=aT(n/b)+d(n) =aaT(n/b2)+d(n/b)+d(n) =a2T(n/b2)+ad(n/b)+d(n) =a2aT(n/b3)+d(n/b2)+ad(n/b)+d(n

15、) =a3T(n/b3)+a2d(n/b2)+ad(n/b)+d(n) = =ai T(n/bi )+10)(ijjjbnda 設(shè) n=bk T(n/bk)=T(1)=c 當(dāng)i=k時，上式變?yōu)椋?T(n)=cak+) 1 ()(10kjjkjbda 說明： b往往表示每次分的份數(shù)，如二分法，b=2。 a往往表示每一分層中所做的主要工作的次數(shù)。 k往往是分的層數(shù)（不是次數(shù)） ak 項最后?；癁閚的方冪的形式，代表所有子問題求解工作的總量。 (3) 將所有子問題的解合成最終解的工作量 10)(kjjkjbda重要結(jié)論重要結(jié)論分析：如果n=1即只有一個元素，則只要比較這個元素和x就可以確定x是否在表

16、中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析： 該問題的規(guī)?？s小到一定的

17、程度就可以容易地解決；該問題的規(guī)?？s小到一定的程度就可以容易地解決； 該問題可以分解為若干個規(guī)模較小的相同問題該問題可以分解為若干個規(guī)模較小的相同問題; 分解出的子問題的解可以合并為原問題的解；分解出的子問題的解可以合并為原問題的解； 分解出的各個子問題是相互獨立的。分解出的各個子問題是相互獨立的。 給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法二分搜索算法：public static int binarySearch(int a, int x, int n) / 在 a0 =

18、a1 = . = an-1 中搜索 x / 找到x時返回其在數(shù)組中的位置，否則返回-1 int left = 0; int right = n - 1; while (left amiddle) 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)運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復(fù)雜性為O(logn) 。 請設(shè)計一個有效的算法，可以進(jìn)行兩

19、個請設(shè)計一個有效的算法，可以進(jìn)行兩個n n位大整數(shù)的乘法運算位大整數(shù)的乘法運算u小學(xué)的方法：O(n2) 效率太低u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 細(xì)節(jié)問題細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。1. XY = ac 2n + (a-b)(d-c)+ac+bd) 2n/2 + bd2. XY = ac 2n + (a+b)(c+d)-ac-bd) 2n/2 + bd復(fù)雜度分析復(fù)雜度分析T(n)=O(nlog3) =O(n1.5

20、9) 較大的改進(jìn)較大的改進(jìn)11)()2/(3) 1 ()(nnnOnTOnT 請設(shè)計一個有效的算法，可以進(jìn)行兩個請設(shè)計一個有效的算法，可以進(jìn)行兩個n n位大整數(shù)的乘法運算位大整數(shù)的乘法運算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é)果。A和B

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

22、O(n3) 沒有改進(jìn)沒有改進(jìn)22)()2/(8) 1 ()(2nnnOnTOnTu傳統(tǒng)方法：O(n3)u分治法:為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC復(fù)雜度分析復(fù)雜度分析T(n)=O(nlog7) =O(n2.81) 較大的改進(jìn)較大的改進(jìn)22)()2/(

23、7) 1 ()(2nnnOnTOnTu傳統(tǒng)方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcroft和Kerr已經(jīng)證明(1971)，計算2個矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時間復(fù)雜性，就不能再基于計算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是 O(n2.376)是否能找到O(n2)的算法？目前為止還沒有結(jié)果。在一個2k2k 個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示

24、的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。當(dāng)k0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤11。 public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) ret

25、urn; 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 = tc + s) / 特殊方格在此棋盤中 chessBoard(tr,

26、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型骨牌覆蓋左上角 boardtr + stc + s = t; / 覆蓋其余方格 chessBoa

27、rd(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個子集合，分別對2個子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 public static void mergeSort(Comparable a, int left, int right) if (left= x的元素交換到左邊區(qū)域 / 將= x的元素交換到右邊區(qū)域 while (true) while (a+pareTo(x) 0); if

28、 (i = j) break; MyMath.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, 8private static int randomizedPartition (int p, int r) int i = random(p,r); MyMath.swap(a, i, p); ret

29、urn partition (p, r); 快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設(shè)計出采用隨機選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可以在ap:r中隨機選出一個元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機的，從而可以期望劃分是較對稱的。&最壞時間復(fù)雜度：最壞時間復(fù)雜度：O(n2)&平均時間復(fù)雜度：平均時間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)或或O(logn)&穩(wěn)定性：不穩(wěn)定穩(wěn)定性：不穩(wěn)定問題描述： 給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的

30、元素。思想：1、選擇問題的最簡單的解法是直接使用排序算法，排序后取第k個元素即為所求。最好的排序算法（如快速排序），在最壞情況下，快速排序與插入排序、選擇排序一樣為：O(n2)?？焖倥判虻钠骄鶑?fù)雜度為：O(nlogn) 2、快速排序的排序思路可以借鑒，試圖改善平均復(fù)雜度：O(n)3、問題：是否可以在最壞情況下使得選擇可以在O(n)時間內(nèi)完成？給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素private static Comparable randomizedSelect(int p,int r,int k) if (p=r) return ap; int i=ra

31、ndomizedpartition(p,r), j=i-p+1; if (k=j) return randomizedSelect(p,i,k); else return randomizedSelect(i+1,r,k-j); 在最壞情況下，算法randomizedSelect需要O(n2)計算時間但可以證明，算法randomizedSelect可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。如果能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的倍(01是某個正常數(shù))，那么就可以在最壞情況下在最壞情況下用O(n)時間完成選擇任務(wù)。例如，若=9

32、/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。1. 若 ，直接排序數(shù)組，第k個元素即為所求元素；否則，轉(zhuǎn)2；2. 把元素劃分為 組，每組5個元素，不足5個元素的那一組不予處理；3. 取每組的中值元素，構(gòu)成一個規(guī)模為p 的數(shù)組M ；4. 對數(shù)組M 遞歸地執(zhí)行算法，得到一個中值的中值元素m ；5. 把原數(shù)組劃分成三組P,Q, R，使得小于m 的元素存放于P，等于m 的元素存放于Q ，大于m 的元素存放于R；6. 如果 ，對P 遞歸地執(zhí)行算法；否則轉(zhuǎn)7；7. 如果 ，

33、則 m 就是所要選擇的元素；否則轉(zhuǎn)8；8. 對R遞歸地執(zhí)行算法。0nn 5/np kP |kQP|按 遞 增 順 序 ， 找 出 下 面按 遞 增 順 序 ， 找 出 下 面 2 9 個 元 素 的 第個 元 素 的 第 1 8 小 元 素 ：小 元 素 ：8, ,31, ,60, ,33, ,17, ,4, ,51, ,57, ,49, ,35, ,11, ,43, ,37, ,3, ,13, ,52, ,6, ,19, ,25, ,32, ,54, ,16, ,5, ,41, ,7, ,23, ,22, ,46, ,29。當(dāng)當(dāng)k=18k=18時，算法的執(zhí)行步驟如下：時，算法的執(zhí)行步驟如下：

34、1.前面前面25個元素劃分為個元素劃分為5組：組：( (8, ,31, ,60, ,33, ,17),(),(4, ,51, ,57, ,49, ,35), (), (11, ,43, ,37, ,3, ,13),(),(52, ,6, ,19, ,25, ,32) )，( (54, ,16, ,5, ,41, ,7) )，其余，其余4個元素暫不處理；個元素暫不處理；2. . 提取每一組的中值元素，構(gòu)成一個中值元素的集合：（提取每一組的中值元素，構(gòu)成一個中值元素的集合：（31, ,49, ,13, ,25, ,16）；）；3. . 遞歸地使用算法去求取該中值元素集合的中值，得到遞歸地使用算法去

35、求取該中值元素集合的中值，得到m=25m=25；4 . 根 據(jù)根 據(jù) m = 2 5m = 2 5 ， 把 原 來 的 數(shù) 組 劃 分 成， 把 原 來 的 數(shù) 組 劃 分 成 3 個 子 數(shù) 組 ：個 子 數(shù) 組 ： P = P = 8 , , 1 7 , , 4 , , 1 1 , , 3 , , 1 3 , , 6 , , 1 9 , , 1 6 , , 5 , , 7 , , 2 3 , , 2 2 ， Q = Q = 2 5 ，R=R=31, ,60, ,33, ,51, ,57, ,49, ,35, ,43, ,37, ,52, ,32, ,54, ,41, ,46, ,29 ；5

36、. . 由于由于|P|=13|P|=13，|Q|=1|Q|=1，而，而k=18k=18，所以丟棄，所以丟棄P P、Q Q，使，使k=18-13-1=4k=18-13-1=4，對，對R R遞歸地執(zhí)遞歸地執(zhí)行本算法；行本算法；6. . 把把R R劃分成劃分成3組組 ( (31, ,60, ,33, ,51, ,57) )，( (49, ,35, ,43, ,37, ,52) )，( (32, ,54，41, ,46, ,29) )；7. . 這這3組的中值元素分別為：組的中值元素分別為： 51, ,43, ,41 ，它的中值元素是，它的中值元素是43，8 . . 根 據(jù)根 據(jù) 4 3 把 劃 分

37、成把 劃 分 成 3 組 ：組 ： 3 1 , , 3 3 , , 3 5 , , 3 7 , , 3 2 , , 4 1 , , 2 9 ， 4 3 ， 60, ,51, ,57, ,49, ,52, ,54, ,46 ；9. K=4. K=4，丟棄后面兩個子數(shù)組，以，丟棄后面兩個子數(shù)組，以k=4k=4，對第一個子數(shù)組遞歸調(diào)用本算法；，對第一個子數(shù)組遞歸調(diào)用本算法；10. .把這個子數(shù)組劃分成把這個子數(shù)組劃分成5個元素的一組：個元素的一組： 31, ,33, ,35, ,37, ,32,取其中值元素為取其中值元素為33； 11. .根據(jù)根據(jù)33，把第一個子數(shù)組劃分成：，把第一個子數(shù)組劃分成：

38、 31, ,32, ,29,33 ， 35, ,37, ,41 ；12.k=4 .k=4 ，而第一、二個子數(shù)組元素個數(shù)為，而第一、二個子數(shù)組元素個數(shù)為4，所以，所以，33即為所求取的第即為所求取的第18小元素小元素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個元素小于本

39、組的中位數(shù)，而n/5個中位數(shù)中又有(n-5)/10個小于基準(zhǔn)x。同理，基準(zhǔn)x也至少比3(n-5)/10個元素小。而當(dāng)n75時，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個子數(shù)組的長度都至少縮短1/4。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 for ( int i = 0; i

40、=(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/()(21nnnTnTnCCnT上述算法將每一組的

41、大小定為5，并選取75作為是否作遞歸調(diào)用的分界點。這2點保證了T(n)的遞歸式中2個自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。給定平面上n個點的集合S，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。 u為了使問題易于理解和分析，先來考慮一維一維的情形。此時，S中的n個點退化為x軸上的n個實數(shù) x1,x2,xn。最接近點對即為這n個實數(shù)中相差最小的2個實數(shù)。假設(shè)我們用x軸上某個點m將S劃分為2個子集S1和S2 ，基于平衡子問題平衡子問題的思想，用S中各點坐標(biāo)的中位數(shù)來作分割點。遞歸地在S1和S

42、2上找出其最接近點對p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？u如果S的最接近點對是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過d，即p3(m-d,m，q3(m,m+d。u由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于d），并且m是S1和S2的分割點，因此(m-d,m中至多包含S中的一個點。由圖可以看出，如果如果(m-d,m中有中有S中的點，則此點就是中的點，則此點就是S1

43、中最大點。中最大點。u因此，我們用線性時間就能找到區(qū)間(m-d,m和(m,m+d中所有點，即p3和q3。從而我們用線性時間就可以將從而我們用線性時間就可以將S1的解和的解和S2的解合并成為的解合并成為S的解的解。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？u下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點對或者是d，或者是某個p,q，其中pP1且qP2。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p,q？u考慮P1中任意一點p，它若與P2中的點q構(gòu)成最接近點對的候選者，則必有distance(p，q)d。滿足這個條件的滿足這個條件的P2中的點中的點一定落在一個一定落在一個d2d的矩形的矩形R中中u由d的意義可知，P2中任何2個S中的點的距離都不小于d。由此可以推出矩形矩形R中最多只有中最多只有6個個S中的點中的點。u因此，在分治法的合并步驟中最多只需要檢查最多只需要檢查6n/2=3n個個候選者候選者能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？證明證明:將矩形R的長為2d的邊3等分，將它的