遞歸與分治策略

1、算法設計與分析,山東師范大學信息科學與工程學院軟件工程研究所徐連誠 E-Mail：lchxu@163.com2006年9月18日,2,第2章 遞歸與分治策略,本章主要知識點：2.1 遞歸的概念2.2 分治法的基本思想2.3 二分搜索技術2.4 大整數(shù)的乘法2.5 Strassen矩陣乘法2.6 棋盤覆蓋2.7 合并排序2.8 快速排序2.9 線性時間選擇2.10 最接近點對問題2.11 循環(huán)賽日程表計劃授課時

2、間：6～8課時,3,2.1 遞歸的概念,直接或間接地調用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計算機算法設計與分析中，使用遞歸技術往往使函數(shù)的定義和算法的描述簡潔且易于理解。下面來看幾個實例。,4,2.1 遞歸的概念,例1 階乘函數(shù)可遞歸地定義為：其中：n=0時，n!=1為邊界條件n>0時，n!=n(n-1)!為遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才

3、能在有限次計算后得出結果。,5,2.1 遞歸的概念,例2 Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數(shù)列。它可以遞歸地定義為：第n個Fibonacci數(shù)可遞歸地計算如下：public static int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)

4、+fibonacci(n-2); },小兔子問題,6,2.1 遞歸的概念,例3 Ackerman函數(shù)當一個函數(shù)及它的一個變量是由函數(shù)自身定義時，稱這個函數(shù)是雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：前2例中的函數(shù)都可以找到相應的非遞歸方式定義。但本例中的Ackerman函數(shù)卻無法找到非遞歸的定義。,7,2.1 遞歸的概念,A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)：M=0時，A(n,0)=n+2M

5、=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)的增長速度非?？欤灾劣跊]有適當?shù)臄?shù)學式子來表示這一函數(shù)。定義單變量的Ackerman函數(shù)A(n)為，A(n)=A(

6、n，n)。定義其擬逆函數(shù)α(n)為：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在復雜度分析中常遇到。對于通常所見到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨向正無窮大。,8,2.1 遞歸的概念,例4 排列問題設計一個遞歸算法生成n個元素{r1,r2,…,rn}的全排列。設R={r1,r2,…,rn}是要進行排列的n個元素，Ri=R-

7、{ri}。集合X中元素的全排列記為perm(X)。(ri)perm(X)表示在全排列perm(X)的每一個排列前加上前綴得到的排列。R的全排列可歸納定義如下：當n=1時，perm(R)=(r)，其中r是集合R中唯一的元素；當n>1時，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)構成。,9,2.1 遞歸的概念,例5 整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+

8、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。,10,2.1 遞歸的概念,前面的幾個例子中，問題本身都具有比較明顯的遞歸關系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設

9、p(n)為正整數(shù)n的劃分數(shù)，則難以找到遞歸關系，因此考慮增加一個自變量：將最大加數(shù)n1不大于m的劃分個數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關系：q(n,1)=1，n≥1；當最大數(shù)n1不大于1時，任何正整數(shù)n只有一種劃分形式：n=1+1+...+1(共n個)。Q(n,m)=q(n,n)，m≥n；最大加數(shù)n1實際上不能大于n。因此，q(1,m)=1。q(n,n)=1+q(n,n-1)；正整數(shù)n的劃分由n1=n的劃分和n1

10、≤n-1的劃分組成。q(n,m)=q(n,m-1)+q(n-m,m),n>m>1；正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1≤m-1 的劃分組成。,11,2.1 遞歸的概念,正整數(shù)n的劃分數(shù)p(n)=q(n,n)。,12,2.1 遞歸的概念,例6 Hanoi塔問題設a,b,c是3個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1,2,…,n,現(xiàn)要求將塔

11、座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則：每次只能移動1個圓盤；任何時刻都不允許將較大的圓盤壓在較小的圓盤之上；在滿足移動規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。public static void hanoi(int n, int a, int b, int c){　if (n > 0)　{　　hanoi(n-1, a, c, b);　　move(a,b

12、);　　hanoi(n-1, c, b, a);　}}思考：如果塔的個數(shù)變?yōu)閍,b,c,d四個，現(xiàn)要將n個圓盤從a全部移動到d，移動規(guī)則不變，求移動步數(shù)最小的方案。,13,2.1 遞歸的概念,遞歸小結優(yōu)點：結構清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調試程序帶來很大方便。缺點：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。解決方法：在遞歸算法中消除遞歸調

13、用，使其轉化為非遞歸算法。采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調用工作棧。該方法通用性強，但本質上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。用遞推來實現(xiàn)遞歸函數(shù)。通過Cooper變換、反演變換能將一些遞歸轉化為尾遞歸，從而迭代求出結果。后兩種方法在時空復雜度上均有較大改善，但其適用范圍有限。,14,2.2 分治法的基本思想,分治法的基本思想分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這

14、些子問題互相獨立且與原問題相同。對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。,凡治眾如治寡，分數(shù)是也?！獙O子兵法,15,2.2 分治法的基本思想,16,2

15、.2 分治法的基本思想,分治法的適用條件分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。 這條特征涉及到分治法的效率，如果各子問題是不獨立的，則分治法要做許多不必要的工作，重復地解公共的子問題，此時

16、雖然也可用分治法，但一般用動態(tài)規(guī)劃較好。,17,2.2 分治法的基本思想,分治法的基本步驟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)

17、; //遞歸的解各子問題　return merge(y1,...,yk); //將各子問題的解合并為原問題的解}人們從大量實踐中發(fā)現(xiàn)，在用分治法設計算法時，最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。,18,2.2 分治法的基本思想,分治法的復雜性分析一個分治法將規(guī)

18、模為n的問題分成k個規(guī)模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時間，則有（右上）。通過迭代法求得方程解（右下） 。注意：遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)

19、的值可以估計T(n)的增長速度。通常假定T(n)是單調上升的，從而當mi≤n<mi+1時，T(mi)≤T(n)<T(mi+1)。,19,2.3 二分搜索技術,給定已按升序排好序的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一特定元素x。適用分治法求解問題的基本特征：該問題的規(guī)?？s小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的各個子問題是

20、相互獨立的。 很顯然此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治法的第四個適用條件。,20,算法及其復雜性,據(jù)此容易設計出二分搜索算法：public static int binarySearch(int [] a, int x, int n){// 在 a[0] a[middle]) left = middle + 1;else right = middle - 1;}ret

21、urn -1; // 未找到x}算法復雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內運算需要O(1) 時間，因此整個算法在最壞情況下的計算時間復雜性為O(logn) 。思考題：給定a，用二分法設計出求an的算法。,21,2.4 大整數(shù)的乘法,設計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算小學的方法：O(n2) ?效率太低分治法:

22、 X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd復雜度分析 T(n)=O(n2) ?沒有改進?,22,算法改進,為了降低時間復雜度，必須減少乘法的次數(shù)。為此，我們把XY寫成另外的形式：XY = ac 2n + ((a-c)(b-d)+ac+bd) 2n/2 + bd 或XY = ac 2n + ((a+c)(b+d)-ac-bd) 2n/2 + bd復雜性：這兩個算式看起來更復雜一些

23、，但它們僅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是 T(n)=O(nlog3) =O(n1.59) ?較大的改進?細節(jié)問題：兩個XY的復雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結果，使問題的規(guī)模變大，故不選擇第2種方案。,23,更快的方法,小學的方法：O(n2)——效率太低分治法: O(n1.59)——較大的改進更快的方法？如果將大整數(shù)分成更多段，用更復雜的

24、方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個復雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內解決。是否能找到線性時間的算法？目前為止還沒有結果。,24,2.5 Strassen矩陣乘法,n×n矩陣A和B的乘積矩陣C中的元素C[i,j]定義為：若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元

25、素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個元素所需的計算時間為O(n3),25,簡單分治法求矩陣乘,首先假定n是2的冪。使用與上例類似的技術，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：由此可得：復雜度分析T(n)=O(n3) ?沒有改進?,26,改進算法,為了降低時間復雜度，必須減少乘法的次數(shù)。而其關鍵在于計算2個2階方陣的乘積時所用乘法次數(shù)能否少于8次。

26、為此，Strassen提出了一種只用7次乘法運算計算2階方陣乘積的方法（但增加了加/減法次數(shù)）：M1=A11(B12-B22)　M2=(A11+A12)B22M3=(A21+A22)B11　M4=A22(B21-B11)M5=(A11+A22)(B11+B22)　M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)做了這7次乘法后，在做若干次加/減法就可以得到：C11=M5+M4-M2+M6　

27、C12=M1+M2C21=M3+M4　C22=M5+M1-M3-M7復雜度分析T(n)=O(nlog7) =O(n2.81) ?較大的改進?,27,更快的方法,Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應當研究3×3或5×5矩陣的更好算法。在S

28、trassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是 O(n2.376)是否能找到O(n2)的算法？目前為止還沒有結果。,28,2.6 棋盤覆蓋,在一個2k×2k個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。易知，

29、覆蓋任意一個2k×2k的特殊棋盤，用到的骨牌數(shù)恰好為(4K-1)/3。,29,分治策略求解,當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1 子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割

30、，直至棋盤簡化為棋盤1×1。,30,算法描述,void CB(int tr,tc,dr,dc,size){if (size == 1) return;int t = tile++; // L型骨牌號s = size/2; // 分割棋盤// 覆蓋左上角子棋盤if (dr = tc + s)// 特殊方格在此棋盤中CB(tr, tc+s, dr, dc, s);else {// 此棋盤中無特殊方格// 用 t

31、 號L型骨牌覆蓋左下角board[tr + s - 1][tc + s] = t;// 覆蓋其余方格CB(tr,tc+s,tr+s-1,tc+s, s);},// 覆蓋左下角子棋盤if (dr >= tr + s && dc = tr + s && dc >= tc + s)// 特殊方格在此棋盤中CB(tr+s, tc+s, dr, dc, s);else {// 用 t 號L

32、型骨牌覆蓋左上角board[tr + s][tc + s] = t;// 覆蓋其余方格CB(tr+s, tc+s, tr+s, tc+s, s);}},,31,復雜度分析,說明：整形二維數(shù)組Board表示棋盤，Borad[0][0]使棋盤的左上角方格。tile是一個全局整形變量，用來表示L形骨牌的編號，初始值為0。tr：棋盤左上角方格的行號；tc：棋盤左上角方格的列號；dr：特殊方各所在的行號；dc：特殊方各所在的列號；

33、size：size=2k，棋盤規(guī)格為2k×2k。復雜度分析： T(k)=4k-1=O(4k) 漸進意義下的最優(yōu)算法,32,2.7 合并排序,基本思想：將待排序元素分成大小大致相同的2個子集合，分別對2個子集合進行排序，最終將排好序的子集合合并成為所要求的排好序的集合。遞歸算法描述：public static void mergeSort(Comparable a[], int left, int right){

34、if (left<right) {//至少有2個元素int i=(left+right)/2; //取中點mergeSort(a, left, i);mergeSort(a, i+1, right);merge(a, b, left, i, right); //合并到數(shù)組bcopy(a, b, left, right); //復制回數(shù)組a}}復雜度分析T(n)=O(nlogn) 漸進意義下的最優(yōu)算法,

35、33,算法改進,算法mergeSort的遞歸過程可以消去。初始序列 [49] [38] [65] [97] [76] [13] [27]第一步　 [38 49] [65 97] [13 76] [27]第二步　 [38 49 65 97] [13 27 76]第三步　 [13 27 38 49 65 76 97],34,改進后的算法描述及其復雜性

36、,算法描述：略復雜性分析：最壞時間復雜度：O(nlogn)平均時間復雜度：O(nlogn)輔助空間：O(n)思考題：給定有序表A[1:n]，修改合并排序算法，求出該有序表的逆序對數(shù)。,35,2.8 快速排序,快速排序是基于分治策略的另一個排序算法，其基本思想是：分解——以ap為基準元素將ap：r劃分成3段ap：q-1、aq和aq+1：r，使得ap：q-1中任何元素小于aq ，aq+1：r中任何元素大于aq ；下標q在劃分過程

37、中確定；遞歸求解——通過遞歸調用快速排序算法分別對ap：q-1和aq+1：r進行排序；合并——由于對ap：q-1和aq+1：r的排序是就地進行的，所以在ap：q-1和aq+1：r都已排好序后不需要執(zhí)行任何計算ap：r就已排好序。在快速排序中，記錄的比較和交換是從兩端向中間進行的，關鍵字較大的記錄一次就能交換到后面單元，關鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大，因而總的比較和移動次數(shù)較少。快速算法描述：te

38、mplatevoid QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); //對左半段排序QuickSort (a,q+1,r); //對右半段排序}},36,分解/劃分算法描述,分解/劃分算法描述：templateint Partition (Type a[], int p, int

39、r){int i = p, j = r + 1; Type x=a[p];// 將 x的元素交換到右邊區(qū)域while (true) {while (a[++i] x);if (i >= j) break; Swap(a[i], a[j]);}a[p] = a[j];a[j] = x;return j;},{6, 7, 51, 2, 5, 8} 初始序列{6, 7, 51, 2, 5, 8} j--;↑

40、i　　　　　　↑j{5, 7, 51, 2, 6, 8} i++;　 ↑i　　　 ↑j{5, 6, 51, 2, 7, 8} j--;　 ↑i　 　↑j{5, 2, 51, 6, 7, 8} i++;　　　↑i ↑j{5, 2, 51}6{7, 8} 完成快速排序具有不穩(wěn)定性！,,37,復雜性分析及隨機化的快速排序算法,算法復雜性分析：最壞時間復雜度：O(n2)平均時間復雜度：O(nlogn)輔助空間：O(n)或O

41、(logn)快速排序算法的性能取決于劃分的對稱性。通過修改算法partition，可以設計出采用隨機選擇策略的快速排序算法。在快速排序算法的每一步中，當數(shù)組還沒有被劃分時，可以在a[p:r]中隨機選出一個元素作為劃分基準，這樣可以使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。算法描述：templateint RandomizedPartition (Type a[], int p, int r){int i = R

42、andom(p,r);Swap(a[i], a[p]);return Partition (a, p, r);},38,2.9 線性時間選擇,元素選擇問題：給定線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素。RandomizedSelect算法：模仿快速排序算法，首先對輸入數(shù)組進行劃分，然后對劃分出的子數(shù)組之一進行遞歸處理。算法描述如下：templateType RandomizedSelect

43、(Type a[],int p,int r,int k){if (p==r) return a[p];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

44、需要O(n2)計算時間。但可以證明，算法RandomizedSelect可以在O(n)平均時間內找出n個輸入元素中的第k小元素。,39,改進算法,基本思路：如果能在線性時間內找到一個劃分基準，使得按這個基準所劃分出的2個子數(shù)組的長度都至少為原數(shù)組長度的ε倍(0<ε<1是某個正常數(shù))，那么就可以在最壞情況下用O(n)時間完成選擇任務。例如，若ε=9/10，算法遞歸調用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，

45、算法所需的計算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。,40,一個較好的基準劃分步驟,步驟（如圖所示）：將n個輸入元素劃分成?n/5?個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共?n/5?個。遞歸調用select來找出這?n/5?個元素的中位數(shù)。如果?n/5?是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分

46、基準。說明：設所有元素互不相同。在這種情況下，找出的基準x至少比3(n-5)/10個元素大，因為在每一組中有2個元素小于本組的中位數(shù)，而n/5個中位數(shù)中又有(n-5)/10個小于基準x（如圖）。同理，基準x也至少比3(n-5)/10個元素小。而當n≥75時，3(n-5)/10≥n/4所以按此基準劃分所得的2個子數(shù)組的長度都至少縮短1/4。,圖2-7 選擇劃分基準其中，n個元素用小圓點表示，　　　空心圓點為每組元素的中位數(shù)；　　

47、　x為中位數(shù)的中位數(shù)；　　　箭頭由較大元素指向較小元素。只要等于基準的元素不太多，利用這個基準來劃分的兩個數(shù)組的大小就不會相差太遠。,41,算法描述及復雜性分析,private static Comparable select (int p, int r, int k){//用某個簡單排序算法對數(shù)組a[p:r]排序; if (r-p<75) {bubbleSort(p,r);return a[p+k-1];}//

48、將ap+5*i至ap+5*i+4的第3小元素與ap+i交換;//找中位數(shù)的中位數(shù)，r-p-4即前述n-5;for ( int i = 0; i<=(r-p-4)/5; i++ ){int s=p+5*i,t=s+4;for (int j=0;j<3;j++) bubble(s,t-j);MyMath.swap(a, p+i, s+2);}Comparable x = select(p, p+(r-p-4)/

49、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);},復雜度分析 C1為直接簡單排序時間C2n為執(zhí)行for循環(huán)的時間解遞歸方程得T(n)=O(n)說明：上述算法將每一組的大小定為5，并選取75作為是否作遞歸調用的分界點。這2點保證了T(n)的遞歸式

50、中2個自變量之和n/5+3n/4=19n/20=εn，0<ε<1。這是使T(n)=O(n)的關鍵之處。當然，除了5和75之外，還有其他選擇。上述算法中我們假設元素互不相等已保證劃分后子數(shù)組不超過3n/4。當元素可能相等時，設有m個（將他們集中起來），若j≤k≤j+m-1時返回ai；否則調用select(i+m+1, r, k-j-m)。,42,2.10 最接近點對問題,問題描述：給定平面上n個點，找其中的一對點，使得在n個

51、點所組成的所有點對中，該點對間的距離最小。說明：嚴格來講，最接近點對可能多于一對，為簡便起見，我們只找其中的一對作為問題的解。一個簡單的做法是將每一個點與其他n-1個點的距離算出，找出最小距離的點對即可。該方法的時間復雜性是T(n)=n(n-1)/2+n=O(n2)，效率較低。已經(jīng)證明，該算法的計算時間下界是Ω(nlogn)。,43,一維空間中的情形,為了使問題易于理解和分析，先來考慮一維的情形。此時，S中的n個點退化為x軸上的

52、n個實數(shù)x1,x2,…,xn。最接近點對即為這n個實數(shù)中相差最小的2個實數(shù)。一個簡單的辦法是先把x1,x2,…,xn排好序，再進行一次線性掃描就可以找出最接近點對，T(n)=O(nlogn)。然而這種方法無法推廣到二維情形。假設我們用x軸上某個點m將S劃分為2個子集S1和S2 ，基于平衡子問題的思想，用S中各點坐標的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對{p1,p2}和{q1,q2}，并設d=min{|p1-p2|

53、,|q1-q2|}，S中的最接近點對或者是{p1,p2}，或者是{q1,q2}，或者是某個{p3,q3}，其中p3∈S1且q3∈S2。能否在線性時間內找到p3,q3？,44,算法描述及復雜性,如果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的

54、分割點，因此(m-d,m]中至多包含S中的一個點。由圖可以看出，如果(m-d,m]中有S中的點，則此點就是S1中最大點。因此，我們用線性時間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點，即p3和q3。從而我們用線性時間就可以將S1的解和S2的解合并成為S的解。分割點m的選取不當，會造成|Si|=1，|Sj|=n-1(i+j=1)的情形，使得T(n) =T(n-1)+O(n)=O(n2)。這種情形可以通過“平衡子問題”方法加以解

55、決：選取各點坐標的中位數(shù)作分割點。,算法描述：bool CPair1(S, d){n=|S|;if (nS1+S2;//S1={x|xm}CPair1(S1, d1);CPair1(S2, d2);p=max(S1);q=min(S2);d=min(d1, d2, q-p);return ture;}復雜性分析： T(n)=O(nlogn)該算法可推廣到二維的情形中去。,45,二維空間的最接近點對問題,下面

56、來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設d=min{d1,d2}，S中的最接近點對或者是d，或者是某個{p,q}，其中p∈P1且q∈P2 ，如圖2-9所示。能否在線性時間內找到p,q？考慮P1中任意一點p，它若與P2中的點q構成最接近點對的候選者，則必有distance(p，q)＜d。滿足這個條件的P2中的

57、點一定落在一個d×2d的矩形R中，如圖2-10所示。由d的意義可知，P2中任何2個S中的點的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點。,圖2-9距離直線l小于d的所有點,圖2-10包含q的d×2d矩形R,46,R中至多包含6個S中的點的證明,證明：將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導出6個(d/2)×(2d/3)的矩形（如圖(a)所示 ）。若矩形R中有多于6個S

58、中的點，則由鴿舍原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點。設u，v是位于同一小矩形中的2個點，則因此，distance(u,v)<d。這與d的意義相矛盾。也就是說，矩形R中最多有6個S中的點。極端情形：圖(b)是矩形R中恰有6個S中的點的極端情形。,47,說明,因此，在分治法的合并步驟中最多只需要檢查6×n/2=3n個候選者。為了確切地知道要檢查哪6個點，可以將p和P2

59、中所有S2的點投影到垂直線l上。由于能與p點一起構成最接近點對候選者的S2中點一定在矩形R中，所以它們在直線l上的投影點距p在l上投影點的距離小于d。由上面的分析可知，這種投影點最多只有6個。因此，若將P1和P2中所有S中點按其y坐標排好序，則對P1中所有點，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者。對P1中每一點最多只要檢查P2中排好序的相繼6個點。,48,算法描述及復雜性分析,算法描述：public stati

60、c double CPair2(S){n=|S|;if (n m}d1=cpair2(S1);d2=cpair2(S2);dm=min(d1,d2);設P1是S1中距垂直分割線l的距離在dm之內的所有點組成的集合；P2是S2中距分割線l的距離在dm之內所有點組成的集合；將P1和P2中點依其y坐標值排序；并設X和Y是相應的已排好序的點列；,通過掃描X以及對于X中每個點檢查Y中與其距離在dm之內的所有點(最多6個)可以完

61、成合并；當X中的掃描指針逐次向上移動時，Y中的掃描指針可在寬為2dm的區(qū)間內移動；設dl是按這種掃描方式找到的點對間的最小距離；d=min(dm,dl);return d;}復雜度分析： T(n)=O(nlogn)算法的具體實現(xiàn)：略。,49,2.11 循環(huán)賽日程表,分治法不僅可以用來設計算法，而且再其他方面也有廣泛應用：利用分治法設計電路、構造數(shù)學證明等。循環(huán)賽日程標問題，設有n=2k個選手要進行循環(huán)賽，設計一個滿足

62、以下要求的比賽日程表：每個選手必須與其他n-1個選手各賽一次；每個選手一天只能賽一次；循環(huán)賽一共進行n-1天。按此要求，可以將比賽日程表設計成n行n-1列的表格，i行j列表示第i個選手在第j天所遇到的選手?；舅悸罚喊捶种尾呗?，將所有的選手分為兩組，n個選手的比賽日程表就可以通過為n/2個選手設計的比賽日程表來決定。遞歸地用對選手進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單。這時只要讓這2個選手進行比賽就可以了