算法遞歸與分治策略

1、第2章 遞歸與分治策略學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)；（2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤(pán)覆蓋；（5）合并排序和快速排序；（6）線性時(shí)間選擇；（7）最接近點(diǎn)對(duì)問(wèn)題；（8）循環(huán)賽日程表。題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=小，則再劃分為k k歸的進(jìn)行下去，直對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠?qū)⒁蠼獾妮^大規(guī) 個(gè) 模 子 的 問(wèn) 問(wèn) 題 題 ， 分 如 割 此 成 遞個(gè)更小規(guī)模的子問(wèn)到問(wèn)題規(guī)模足夠小，很容易求出其解為止。算法總體思想對(duì)這k 分小

2、，則再劃分為knT(n)=n/2n/2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4將求出 個(gè) 的 子 小 問(wèn) 規(guī) 題 模的 別 問(wèn) 求 題 解 的 。 解 如 合 果 并 子 為 問(wèn) 一 題 個(gè) 的 更 規(guī) 大 模 規(guī) 仍 模 然 的 不 問(wèn) 夠題的解，自底向上 個(gè) 逐 子 步 問(wèn) 求 題 出 ， 原 如 來(lái) 此 問(wèn) 遞 題 歸 的 的 解 進(jìn) 。 行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。算法總體思想將求出的小規(guī)模的問(wèn)題的解

3、合并為一個(gè)更大規(guī)模的問(wèn)題的解，自底向上逐步求出原來(lái)問(wèn)題的解。nT(n)=n/2n/2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4算法總體思想將求出的小規(guī)模的問(wèn)題的解合并為一個(gè)更大規(guī)模的問(wèn)n/2n/2n/2n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4題的解，自底向上逐步求出原來(lái)問(wèn)

4、題的解。分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，成一分而治之。2.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。2.1 遞歸的概念例1階乘函數(shù)階乘函數(shù)可遞歸地定義為：邊界條件 1 n = 0n!= 遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸

5、函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。F(n) = n =12.1 遞歸的概念例2 Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程 1 n = 01F(n 1)+ F(n 2) n 1第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n)if (n 1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。2.1 遞歸的概念例5整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2n

6、k1，k1。正整數(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。(4) 正整數(shù)n n nm n 的劃分 1實(shí)際上不 1(3) 2.1 遞歸的概念例5整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系

7、。(1) q(n,n)=1+q(n,n-1);當(dāng)最大 n1 的劃分和n 整 -1只有一種劃分即 n =1+1+1(2) q(n,m)=q(n,m-1)+q(n-m,m),nm1;最大加數(shù) 的最大加數(shù)n能 不 大 大 于 于。 的 因 劃 此 分 ， 由 q(1,m)=1。 和n1n-1 的劃分組成。q(n,m) = n =1,m =1n m 12.1 遞歸的概念例5整數(shù)劃分問(wèn)題前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可

8、以建立q(n,m)的如下遞歸關(guān)系。 1q(n,n)1+ q(n,n 1) q(n,m1)+ q(n m,m)正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。2.1 遞歸的概念例6 Hanoi塔問(wèn)題設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤(pán)，這些圓盤(pán)自下而上，由大到小地疊在一起。各圓盤(pán)從小到大編號(hào)為1,2,n,現(xiàn)要求將塔座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤(pán)；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至a,b,c中任一塔座上。用遞歸技術(shù)來(lái)解決這個(gè)問(wèn)題。

9、上即可。較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座a移至塔座c，然后，將剩下的最大圓盤(pán)從塔座a移至塔座b，最后，再設(shè)法將n-1個(gè)較小的圓盤(pán)依照移動(dòng)規(guī)則從塔座c移至塔座b。由此可見(jiàn)，n個(gè)圓盤(pán)的移動(dòng)問(wèn)題可分為2次n-1個(gè)圓盤(pán)的移動(dòng)問(wèn)題，的遞歸算法如下。當(dāng)n1時(shí)，需要利用塔座c作為輔助塔座。此時(shí)若能設(shè)法將n-1個(gè)這又可以遞歸地用上述方法來(lái)做。由此可以設(shè)計(jì)出解Hanoi塔問(wèn)題2.1 遞歸的概念例6 Hanoi塔問(wèn)題在問(wèn)題 hanoi(int 大 比 時(shí) int 簡(jiǎn) 較 int 找 此 到 int ， 般 只 的 要 方 將 法 編 ， 號(hào) 因 為 此我們嘗試塔座a直當(dāng)n=1時(shí) 規(guī) ， 模 問(wèn) 較 題n,較 ，a,

10、單 難 。b,時(shí) 一c) 1的圓盤(pán)從 voidif (n 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、通過(guò)變換能

11、將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征： 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì) 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解； 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加 涉及到 效率 如果各子問(wèn)題是不而增加，因此大部分問(wèn)題滿足這個(gè)特征。用征，

12、則 獨(dú)立的 則分治法要做許多 必要的工作 如果具備了前兩條特征，而不具備第三條，能否利用分治法完全取決于問(wèn)題是否具有這條特征，可以滿足的，此特征反映了遞歸思想的應(yīng)特重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。分治法的基本步驟divide-and-conquer(P)if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)題divide Pinto smaller subinstances P1,P2,.,Pk；/分解問(wèn)題for (i=1,i11m nj=0logm k注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(mén)(n)足夠平滑，那么由

13、n等于m的方冪時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)ai 獨(dú) 此滿足分治法的第四個(gè)適用條件?？梢源_定用條件的后面查找x即可。無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。分二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析： 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題; 分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；if (x = am) retur

14、n m;if (x am) r = m-1; else l = m+1;return -1;二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：templateint BinarySearch(Type a, const Type& x, int l, int r)while (r = l)int m = (l+r)/2; 搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。大整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有

15、效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)效率太低X = a 2n/2 + bY = c 2n/2 + dXY = ac 2n + (ad+bc) 2n/2 + bd分治法:Y=T(n)=O(n2)沒(méi)有改進(jìn)大整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)效率太低1.XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 +復(fù)雜T(n)=O(nlog3) =O(n1.59)較大的改進(jìn)分治法:度分析O(1)( )為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。bd能得到m+1位的結(jié)果，使問(wèn)題的規(guī)模變大，故不選擇第2種方案。bd大

16、整數(shù)的乘法請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2)分治法: O(n1.59)效率太低較大的改進(jìn)更快的方法?如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，將有可能得到更優(yōu)的算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(Fast FourierTransform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法。A和B的乘積矩陣C中的元素Ci,j定義為: = j k B k i A j i C Strassen矩陣乘法nk=1若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個(gè)元素所需的計(jì)算時(shí)間為

17、O(n3)傳統(tǒng)方法：O(n3)由此可得：C11C12C21C22= A 11B11 + A 12B21= A 11B12 + A 12B22= A21B11 + A22B21= A21B12 + A22B22A 3) A22 21 A n2 n Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:例類似的技個(gè)大小相等的子矩陣。由此可將方程C=AB重寫(xiě)為： 11 12T(n112)+ 12O(B11) B12 2C21 C22 T(n)=O(nB21 B22 O(1) n = 2A 11 12 11 C C ) ( = n T2 ) 1 ( = n O = B A A 2 ) ( ) 2 / (

18、 7 2 + n n O n T2 1 12 M M C + =4 3 21 M M C + =7 3 1 5 22 M M M M C + =Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。A 12B11 B12C21 C22 21 22B21 22M 3 = (A21 + A22)B11M 4 = A22(B21 B11)M 5 = (A11 + A22)(B11 + B22)M 6 = (A12 A22)(B21 + B22)M 7 = (A11 A21)(B11 + B12)復(fù)雜度分析M1 = A11(B12 B22) T(n)=O(nlog

19、7) =O(n2.81)較大的改進(jìn)M 2 = (A11 + A12)B22 C11 = M5 +M4 M2 +M6Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法: O(n2.81)更快的方法?Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是 O(n2.376)是否能找到O(n2)的算法？思考題棋盤(pán)覆蓋在一個(gè)2k2k 個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方

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

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

22、s-1, tc+s, s);/ 覆蓋左下角子棋盤(pán)chessBoard(tr+s, tc, tr+s, tc+s-1, s);/ 覆蓋右下角子棋盤(pán)chessBoard(tr, tc, tr+s-1, tc+s-1, s); if (dr = tr + s & dc = tc + s)/ 特殊方格在此棋盤(pán)中chessBoard(tr+s, tc+s, dr, dc, s);else / 用 t 號(hào)L型骨牌覆蓋左上角boardtr + stc + s = t;/ 覆蓋其余方格chessBoard(tr+s, tc+s, tr+s, tc+s, s);T(n)=O(4 / 覆蓋其余方格(1)/

23、 覆蓋左上角子棋盤(pán) if (dr = tr + s & dc tc + s)if (dr + 1 ) ( ) 2 / ( 2 n n O n Tif (leftright) /至少有2個(gè)元素 意義下的最優(yōu)算法合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所int i=(left+right)/2; /取中點(diǎn)mergeSort(a, left, i);mergeSort(a, i+1, right);merge(a, b, left, i, right); /合并到數(shù)組bcopy(a, b, left, right);

24、/復(fù)制回?cái)?shù)組aT(n)=O(nlogn) 漸進(jìn)void MergeSort(Type a, int left,int right) O(1) n 1合并排序算法mergeSort的遞歸過(guò)程可以消去。初始序列49 38 65 97 76 13 2738 4965 9713 7627第一步第二步第三步38 49 65 9713 27 38 49 6513 27 7676 97合并排序最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)快速排序在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單

25、元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少。templatevoid QuickSort (Type a, int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); /對(duì)左半段排序QuickSort (a,q+1,r); /對(duì)右半段排序ii快速排序templateint Partition (Type a, int p, int r)int i = p, j = r + 1;Type x=ap;/ 將 x的元素交換到右邊區(qū)域while (true) while (a+i x);if (i = j) break;

26、Swap(ai, aj);ap = aj;aj = x;return j;初始序列j-;i+;j-;i+;6, 7, 5, 2, 5, 86, 7, 5, 2, 5, 8j5, 7, 5, 2, 6, 8i j5, 6, 5, 2, 7, 8j5, 2, 5, 6, 7, 8i j5, 2, 5 6 7, 8 完成以6為基準(zhǔn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間分是較對(duì)稱的。 ：O(n)或O(logn)templateint RandomizedPartition (Type a, int p, int r)int i = Random(p,r);Swap(ai, ap);return Pa

27、rtition (a, p, r);快速排序快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃序 法。在快 間復(fù)雜度： 的每一步中，當(dāng)數(shù)組還沒(méi)有被算最壞時(shí) 速排序算法 O(n2)線性時(shí)間選擇給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素templateType RandomizedSelect(Type a,int p,int r,int k)if (p=r) return ap;int i=Randomize

28、dPartition(a,p,r),j=i-p+1;if (k=j) return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間但可以證明，算法randomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。執(zhí)行Partition后，數(shù)組ap:r被劃分為2個(gè)子數(shù)組ap:i和ai+1:r，使得ap:i中的每個(gè)元素都不大于ai+1:r中的每個(gè)元素線性時(shí)間選擇如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分

29、出的2個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的倍(01是某個(gè)正常數(shù))，那么就可以在最壞情況下用O(n)時(shí)間完成選擇任務(wù)。例如，若=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。元素作為劃分基準(zhǔn)。線性時(shí)間選擇將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)用select來(lái)找出這n/5個(gè)元素的中位數(shù)。如果n/5是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)設(shè)所有元素

30、互不相同。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個(gè)元素大，因?yàn)樵诿恳唤M中有2個(gè)元素小于本組的中位數(shù)，而n/5個(gè)中位數(shù)中又有(n-5)/10個(gè)小于基準(zhǔn)x。同理，基準(zhǔn)x也至少比3(n-5)/10個(gè)元素小。而當(dāng)n75時(shí)，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。 ) (n Tfor ( int i = 0; i=(r-p-4)/5; i+ ) + + 75 ) 4 / 3 ( ) 5 / ( n n T n T n CT(n)=O(n)上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/

31、5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之Type Select(Type a, int p, int r, int k)if (r-p75) 用某個(gè)簡(jiǎn)單排序算法對(duì)數(shù)組ap:r排序;ap+k-1;將ap+5*i至ap+5*i+4的第3小元素與ap+i交換位置;/找中位數(shù)的中位數(shù)，r-p-4即上面所說(shuō)的n-5Type x = Select(a, p, p+(r-p-4)/5, (r-p-4)/10);int i=Partition(a,p,r, x),j=i-p+1;if (k=j) return Select(a,p,i,k);return 復(fù)雜度分析 2; C1

32、n 75else return 當(dāng)然，除了5和處。 Select(a,i+1,r,k-j);75之外，還有其他選擇。最接近點(diǎn)對(duì)問(wèn)題 定平面上n易于理解和S，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)組S的所n個(gè) 退化為x點(diǎn)對(duì)間n 距離最小。給 為了使問(wèn)題個(gè)點(diǎn)的集合分析，先來(lái)考慮一維的情形。此時(shí)，成中的有點(diǎn)對(duì)中，該軸上的的 個(gè)實(shí)數(shù) x1,x2,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2 ，基于平衡子問(wèn)題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來(lái)作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對(duì)p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，

33、S中的最接近點(diǎn)對(duì)或者是p1,p2，或者是q1,q2，或者是某個(gè)p3,q3，其中p3S1且q3S2。能否在線性時(shí)間內(nèi)找到p3,q3？如果S的最接近點(diǎn)對(duì)是p3,q3，即|p3-q3|d，則p3和q3兩者與m的距離不超過(guò)d，即p3(m-d,m，q3(m,m+d。由于在S1中，每個(gè)長(zhǎng)度為d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于d），并且m是S1和S2的分割點(diǎn)，因此(m-d,m中至多包含S中的一個(gè)點(diǎn)。由圖可以看出，如果(m-d,m中有S中的點(diǎn)，則此點(diǎn)就是S1中最大點(diǎn)。因此，我們用線性時(shí)間就能找到區(qū)間(m-d,m和(m,m+d中所有點(diǎn)，即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。最接近點(diǎn)對(duì)問(wèn)題能否在線性時(shí)間內(nèi)找到p3,q3？最接近點(diǎn)對(duì)問(wèn)題下面來(lái)考慮二維的情形。選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=mind1,d2，S中的最接近點(diǎn)對(duì)或者是d，或者是某個(gè)p,q，其中pP1且qP2。能否在線性時(shí)間內(nèi)找到p,q？25 2最接近點(diǎn)對(duì)問(wèn)題能否在線性時(shí)間內(nèi)找到p3,q3？考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d2d的