計算機算法設(shè)計與分析（第2版）2遞歸與分治策略ppt課件

1、 學(xué)習(xí)要點學(xué)習(xí)要點:了解遞歸的概念。了解遞歸的概念。掌握設(shè)計有效算法的分治戰(zhàn)略。掌握設(shè)計有效算法的分治戰(zhàn)略。經(jīng)過下面的范例學(xué)習(xí)分治戰(zhàn)略設(shè)計技巧。經(jīng)過下面的范例學(xué)習(xí)分治戰(zhàn)略設(shè)計技巧。1二分搜索技術(shù)；二分搜索技術(shù)； 2大整數(shù)乘法；大整數(shù)乘法；3Strassen矩陣乘法；矩陣乘法；4棋盤覆蓋；棋盤覆蓋；5合并排序和快速排序；合并排序和快速排序；6線性時間選擇；線性時間選擇；7最接近點對問題；最接近點對問題；8循環(huán)賽日程表。循環(huán)賽日程表。n將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= n對這k個子問題分別求解。假設(shè)子問題的規(guī)模依然不夠

2、小，那么再劃分為k個子問題，如此遞歸的進展下去，直到問題規(guī)模足夠小，很容易求出其解為止。n對這k個子問題分別求解。假設(shè)子問題的規(guī)模依然不夠小，那么再劃分為k個子問題，如此遞歸的進展下去，直到問題規(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) n將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐漸求出原來問題的解。n將求出的小規(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)n將求出的小規(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) 分治法的設(shè)計思想是，將一個難

4、以直接處理的大問題，分治法的設(shè)計思想是，將一個難以直接處理的大問題，分割成一些規(guī)模較小的一樣問題，以便各個擊破，分割成一些規(guī)模較小的一樣問題，以便各個擊破，分而治之。分而治之。2.1 遞歸的概念n直接或間接地調(diào)用本身的算法稱為遞歸算法。用函數(shù)本身給出定義的函數(shù)稱為遞歸函數(shù)。n由分治法產(chǎn)生的子問題往往是原問題的較小方式，這就為運用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)運用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷減少，最終使子問題減少到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。n分治與遞歸像一對孿生兄弟，經(jīng)常同時運用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。下面來看幾個實例。2.1

5、遞歸的概念例例1 1 階乘函數(shù)階乘函數(shù) 階乘函數(shù)可遞歸地定義為：階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊境條件邊境條件遞歸方程遞歸方程邊境條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只需具備了這兩個要素，才干在有限次計算后得出結(jié)果。2.1 遞歸的概念例例2 Fibonacci2 Fibonacci數(shù)列數(shù)列無窮數(shù)列無窮數(shù)列1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，稱為，稱為FibonacciFibonacci數(shù)列。它可以遞歸地定義為：數(shù)列。它可以遞歸地定義為：邊境條件邊境條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第

6、n個Fibonacci數(shù)可遞歸地計算如下：int fibonacci(int n) if (n 1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。 2.1 遞歸的概念例例5 5 整數(shù)劃分問題整數(shù)劃分問題將正整數(shù)將正整數(shù)n n表示成一系列正整數(shù)之和：表示成一系列正整數(shù)之和：n=n1+n2+nkn=n1+n2+nk，其中其中n1n2nk1n1n2nk1，k1k1。正整數(shù)正整數(shù)n n的這種表示稱為正整數(shù)的這種表示稱為正整數(shù)n n的劃分。求正整數(shù)的劃分。求正整數(shù)n n的不的不同劃分個數(shù)。同劃分個數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6； 5+

7、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) 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 遞歸的概念例

8、例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因此容易用遞歸函數(shù)直接求解。此容易用遞歸函數(shù)直接求解。在本例中，假設(shè)設(shè)在本例中，假設(shè)設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分?jǐn)?shù)，那么難以找到遞歸的劃分?jǐn)?shù)，那么難以找到遞歸關(guān)系，因此思索添加一個自變量：將最大加數(shù)關(guān)系，因此思索添加一個自變量：將最大加數(shù)n1n1不大于不大于m m的劃分的劃分個數(shù)記作個數(shù)記作q(n,m)q(n,m)。可以建立?？梢越(n,m)q(n,m)的如下遞歸關(guān)系。的如下遞歸關(guān)系。11, 1),() 1,() 1,(1),(1),

9、(mnmnmnmnmmnqmnqnnqnnqmnq2.1 遞歸的概念例例5 5 整數(shù)劃分問題整數(shù)劃分問題前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因前面的幾個例子中，問題本身都具有比較明顯的遞歸關(guān)系，因此容易用遞歸函數(shù)直接求解。此容易用遞歸函數(shù)直接求解。在本例中，假設(shè)設(shè)在本例中，假設(shè)設(shè)p(n)p(n)為正整數(shù)為正整數(shù)n n的劃分?jǐn)?shù)，那么難以找到遞歸的劃分?jǐn)?shù)，那么難以找到遞歸關(guān)系，因此思索添加一個自變量：將最大加數(shù)關(guān)系，因此思索添加一個自變量：將最大加數(shù)n1n1不大于不大于m m的劃分的劃分個數(shù)記作個數(shù)記作q(n,m)q(n,m)。可以建立。可以建立q(n,m)q(n,m)的如下遞歸關(guān)

10、系。的如下遞歸關(guān)系。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)。 2.1 遞歸的概念例例6 Hanoi6 Hanoi塔問題塔問題設(shè)設(shè)a,b,ca,b,c是是3 3個塔座。開場時，在塔座個塔座。開場時，在塔座a a上有一疊共上有一疊共n n個圓盤，這個圓盤，這些圓盤自下而上，由大到小地疊在一同。各圓盤從小到大編號些圓盤自下而上，由大到小地疊在一同。各圓盤從小到大編號為為1,2,n,1,2,n,現(xiàn)要求將塔座現(xiàn)要求將塔座a a上的這一疊圓盤移到塔座上的這一疊圓盤移到塔座b b上，并仍上，并仍按同樣順序疊置。在挪動圓盤時應(yīng)遵守以下挪動規(guī)那么：按同樣順序疊置。在挪動圓盤時應(yīng)遵守以下挪動規(guī)那么：規(guī)那么規(guī)那么1

11、 1：每次只能挪動：每次只能挪動1 1個圓盤；個圓盤；規(guī)那么規(guī)那么2 2：任何時辰都不允許將較大的圓盤壓在較小的圓盤之上；：任何時辰都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)那么規(guī)那么3 3：在滿足挪動規(guī)那么：在滿足挪動規(guī)那么1 1和和2 2的前提下，可將圓盤移至的前提下，可將圓盤移至a,b,ca,b,c中任一塔座上。中任一塔座上。在問題規(guī)模較大時，較難找到普通的方法，因此我們嘗試用遞歸技術(shù)來處理這個問題。當(dāng)n=1時，問題比較簡單。此時，只需將編號為1的圓盤從塔座a直接移至塔座b上即可。當(dāng)n1時，需求利用塔座c作為輔助塔座。此時假設(shè)能設(shè)法將n-1個較小的圓盤按照挪動規(guī)那么從塔座a移至塔座c，然

12、后，將剩下的最大圓盤從塔座a移至塔座b，最后，再設(shè)法將n-1個較小的圓盤按照挪動規(guī)那么從塔座c移至塔座b。由此可見，n個圓盤的挪動問題可分為2次n-1個圓盤的挪動問題，這又可以遞歸地用上述方法來做。由此可以設(shè)計出解Hanoi塔問題的遞歸算法如下。2.1 遞歸的概念例例6 Hanoi6 Hanoi塔問題塔問題 void hanoi(int n, int 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)點：構(gòu)造明晰，可讀性強，而且容易用優(yōu)點：構(gòu)造明晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明

13、算法的正確性，因此它數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、調(diào)試程序帶來很大方便。為設(shè)計算法、調(diào)試程序帶來很大方便。缺陷：遞歸算法的運轉(zhuǎn)效率較低，無論是缺陷：遞歸算法的運轉(zhuǎn)效率較低，無論是耗費的計算時間還是占用的存儲空間都比耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。非遞歸算法要多。處理方法：在遞歸算法中消除遞歸調(diào)用，使其處理方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。轉(zhuǎn)化為非遞歸算法。1 1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用任務(wù)棧。該方法通用性強，但本質(zhì)上還是遞用任務(wù)棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了

14、本來由編譯器做的事情，歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。優(yōu)化效果不明顯。2 2、用遞推來實現(xiàn)遞歸函數(shù)。、用遞推來實現(xiàn)遞歸函數(shù)。3 3、經(jīng)過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而、經(jīng)過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。迭代求出結(jié)果。 后兩種方法在時空復(fù)雜度上均有較大改善，后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。由于問題的計算復(fù)雜性普通是隨著問題規(guī)模的添加而添加，因此大部分問題滿足這個特征。這條特征是運用分治法的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的運用能否利用分治法完全取決于問題能否具有這條特征，假設(shè)具備了前兩條

15、特征，而不具備第三條特征，那么可以思索貪婪算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率，假設(shè)各子問題是不獨立的，那么分治法要做許多不用要的任務(wù)，反復(fù)地解公共的子問題，此時雖然也可用分治法，但普通用動態(tài)規(guī)劃較好。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /處理小規(guī)模的問題處理小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題遞歸的解各子問題 return merg

16、e(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)表示該分治法解規(guī)模為|P|=

17、n的問題所需的計算時間，那么有：11)()/() 1 ()(nnnfmnkTOnT經(jīng)過迭代法求得方程的解：1log0log)/()(nmjjjkmmnfknnT留意：遞歸方程及其解只給出留意：遞歸方程及其解只給出n等于等于m的方冪時的方冪時T(n)的值，但的值，但是假設(shè)以為是假設(shè)以為T(n)足夠平滑，那么由足夠平滑，那么由n等于等于m的方冪時的方冪時T(n)的值的值可以估計可以估計T(n)的增長速度。通常假定的增長速度。通常假定T(n)是單調(diào)上升的，從是單調(diào)上升的，從而當(dāng)而當(dāng)minmi+1時，時，T(mi)T(n)T(mi+1)。 分析：假設(shè)n=1即只需一個元素，那么只需比較這個元素和x就可以

18、確定x能否在表中。因此這個問題滿足分治法的第一個適用條件分析：比較x和a的中間元素amid，假設(shè)x=amid，那么x在L中的位置就是mid；假設(shè)xai，同理我們只需在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)模減少了。這就闡明了此問題滿足分治法的第二個和第三個適用條件。 分析：很顯然此問題分解出的子問題相互獨立，即在ai的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。給定已按升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。分析：分析：給定已按

19、升序排好序的給定已按升序排好序的n個元素個元素a0:n-1，現(xiàn)要在這，現(xiàn)要在這n個元素中找個元素中找出一特定元素出一特定元素x。據(jù)此容易設(shè)計出二分搜索算法：template int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x 0時，將2k2k棋盤分割為4個2k-12k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其他3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨

20、牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地運用這種分割，直至棋盤簡化為棋盤11。 void chessBoard(int tr, int tc, int dr, 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 號

21、L型骨牌覆蓋右下角 boardtr + s - 1tc + s - 1 = t; / 覆蓋其他方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆蓋右上角子棋盤 if (dr = 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 &a

22、mp; dc = tr + s & dc = tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號L型骨牌覆蓋左上角 boardtr + stc + s = t; / 覆蓋其他方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 復(fù)雜度分析復(fù)雜度分析T(n)=O(4k) 漸進意義下的最優(yōu)算法漸進意義下的最優(yōu)算法00) 1 () 1(4) 1 ()(kkOkTOkT根本思想：將待排序元素分成大小大致一樣的根本思想：將待排序元素分成大小大致一樣的2個子集合，分個子集合，分別對別對

23、2個子集合進展排序，最終將排好序的子集合合并成為所個子集合進展排序，最終將排好序的子集合合并成為所要求的排好序的集合。要求的排好序的集合。 void MergeSort(Type a, int left, int right) if (leftright) /至少有2個元素 int i=(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ù)雜度分析復(fù)雜度分析T(n)=O

24、(nlogn) 漸進意義下的最優(yōu)算法漸進意義下的最優(yōu)算法11)()2/(2) 1 ()(nnnOnTOnT算法mergeSort的遞歸過程可以消去。初始序列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&最壞時間復(fù)雜度：最壞時間復(fù)雜度：O(nlogn)&平均時間復(fù)雜度：平均時間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)在快速排序中，記錄的比較和交換是從兩端向中間進展的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次

25、就能交換到前面單元，記錄每次挪動的間隔較大，因此總的比較和挪動次數(shù)較少。templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 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

26、= j) break; Swap(ai, aj); 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完成6, 7, 5, 2, 5, 85, 2, 5 6 7, 8templateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r); 快速排序算法的性能取

27、決于劃分的對稱性。經(jīng)過修正算法partition，可以設(shè)計出采用隨機選擇戰(zhàn)略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時，可以在ap:r中隨機選出一個元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機的，從而可以期望劃分是較對稱的。&最壞時間復(fù)雜度：最壞時間復(fù)雜度：O(n2)&平均時間復(fù)雜度：平均時間復(fù)雜度：O(nlogn)&輔助空間：輔助空間：O(n)或或O(logn)給定線性序集中n個元素和一個整數(shù)k，1kn，要求找出這n個元素中第k小的元素templateType RandomizedSelect(Type a,int p,int r,int k)

28、 if (p=r) return ap; int i=RandomizedPartition(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)計算時間但可以證明，算法randomizedSelect可以在O(n)平均時間內(nèi)找出n個輸入元素中的第k小元素。假設(shè)能在線性時間內(nèi)找到一個劃分基準(zhǔn)，使得按這個基準(zhǔn)所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的倍(01是某個正常數(shù))，那么就

29、可以在最壞情況下用O(n)時間完成選擇義務(wù)。例如，假設(shè)=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。l將n個輸入元素劃分成n/5個組，每組5個元素，只能夠有一個組不是5個元素。用恣意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個。l遞歸調(diào)用select來找出這n/5個元素的中位數(shù)。假設(shè)n/5是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分基準(zhǔn)。設(shè)一切元素互不一樣。在這種情況下，找出的基準(zhǔn)x至少比3(n-5)/10個元素大，由于在

30、每一組中有2個元素小于本組的中位數(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。Type Select(Type a, int p, int r, int k) if (r-p75) 用某個簡單排序算法對數(shù)組ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 將ap+5*i至ap+5*i+4的第3小元素 與ap+i交換位置; /找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5 Ty

31、pe 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); else return Select(a,i+1,r,k-j);復(fù)雜度分析復(fù)雜度分析T(n)=O(n)7575)4/3()5/()(21nnnTnTnCCnT上述算法將每一組的大小定為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之外

32、，還有其他選擇。給定平面上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和S2上找出其最接近點對p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點對或者是p1,p2，或者是q1,q2，或者是某個p3,q3，其中p3S1且q3S2。能否在線性時間內(nèi)找到

33、p3,q3？u假設(shè)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中的一個點。由圖可以看出，假設(shè)(m-d,m中有S中的點，那么此點就是S1中最大點。u因此，我們用線性時間就能找到區(qū)間(m-d,m和(m,m+d中一切點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。能否在線性時間內(nèi)找到能否在線性時間內(nèi)找到p3,q3？u下面來思索二維的情形。選取一垂直線l:x=m

34、來作為分割直線。其中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)找到p,q？u思索P1中恣意一點p，它假設(shè)與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等分，將它的長為等分，將它的長為d的邊的邊2等分，由此