遞歸與分治策略

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

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

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

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

5、=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2時(shí)，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時(shí)，類(lèi)似的可以推出M=4時(shí)，A(n,4)的增長(zhǎng)速度非?？欤灾劣跊](méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(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)在復(fù)雜度分析中常遇到。對(duì)于通常所見(jiàn)到的正整數(shù)n，有α(n)≤4。但在理論上α(n)沒(méi)有上界，隨著n的增加，它以難以想象的慢速度趨向正無(wú)窮大。,8,2.1 遞歸的概念,例4 排列問(wèn)題設(shè)計(jì)一個(gè)遞歸算法生成n個(gè)元素{r1,r2,…,rn}的全排列。設(shè)R={r1,r2,…,rn}是要進(jìn)行排列的n個(gè)元素，Ri=R-

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

8、n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整數(shù)n的這種表示稱(chēng)為正整數(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。,10,2.1 遞歸的概念,前面的幾個(gè)例子中，問(wèn)題本身都具有比較明顯的遞歸關(guān)系，因而容易用遞歸函數(shù)直接求解。在本例中，如果設(shè)

9、p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系：q(n,1)=1，n≥1；當(dāng)最大數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式：n=1+1+...+1(共n個(gè))。Q(n,m)=q(n,n)，m≥n；最大加數(shù)n1實(shí)際上不能大于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的劃分?jǐn)?shù)p(n)=q(n,n)。,12,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)要求將塔

11、座a上的這一疊圓盤(pán)移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤(pán)時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：每次只能移動(dòng)1個(gè)圓盤(pán)；任何時(shí)刻都不允許將較大的圓盤(pán)壓在較小的圓盤(pán)之上；在滿(mǎn)足移動(dòng)規(guī)則1和2的前提下，可將圓盤(pán)移至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);　}}思考：如果塔的個(gè)數(shù)變?yōu)閍,b,c,d四個(gè)，現(xiàn)要將n個(gè)圓盤(pán)從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。,13,2.1 遞歸的概念,遞歸小結(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)

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

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

15、.2 分治法的基本思想,分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(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)題。 這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)

16、雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。,17,2.2 分治法的基本思想,分治法的基本步驟divide-and-conquer(P){　if ( | P | <= n0) adhoc(P); //解決小規(guī)模的問(wèn)題　divide P into smaller subinstances P1,P2,...,Pk；//分解問(wèn)題　for (i=1,i<=k,i++)　yi=divide-and-conquer(Pi)

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

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

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

20、相互獨(dú)立的。 很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在a[i]的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿(mǎn)足分治法的第四個(gè)適用條件。,20,算法及其復(fù)雜性,據(jù)此容易設(shè)計(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}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。思考題：給定a，用二分法設(shè)計(jì)出求an的算法。,21,2.4 大整數(shù)的乘法,設(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算小學(xué)的方法：O(n2) ?效率太低分治法:

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

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

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

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

26、為此，Strassen提出了一種只用7次乘法運(yùn)算計(jì)算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復(fù)雜度分析T(n)=O(nlog7) =O(n2.81) ?較大的改進(jìn)?,27,更快的方法,Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究3×3或5×5矩陣的更好算法。在S

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

29、覆蓋任意一個(gè)2k×2k的特殊棋盤(pán)，用到的骨牌數(shù)恰好為(4K-1)/3。,29,分治策略求解,當(dāng)k>0時(shí)，將2k×2k棋盤(pán)分割為4個(gè)2k-1×2k-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)題。遞歸地使用這種分割

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

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

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

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

34、if (left<right) {//至少有2個(gè)元素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); //復(fù)制回?cái)?shù)組a}}復(fù)雜度分析T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法,

35、33,算法改進(jìn),算法mergeSort的遞歸過(guò)程可以消去。初始序列 [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,改進(jìn)后的算法描述及其復(fù)雜性

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

37、中確定；遞歸求解——通過(guò)遞歸調(diào)用快速排序算法分別對(duì)ap：q-1和aq+1：r進(jìn)行排序；合并——由于對(duì)ap：q-1和aq+1：r的排序是就地進(jìn)行的，所以在ap：q-1和aq+1：r都已排好序后不需要執(zhí)行任何計(jì)算ap：r就已排好序。在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(dòng)的距離較大，因而總的比較和移動(dòng)次數(shù)較少?？焖偎惴枋觯簍e

38、mplatevoid QuickSort (Type a[], int p, int r){if (p<r) {int q=Partition(a,p,r);QuickSort (a,p,q-1); //對(duì)左半段排序QuickSort (a,q+1,r); //對(duì)右半段排序}},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,復(fù)雜性分析及隨機(jī)化的快速排序算法,算法復(fù)雜性分析：最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O

41、(logn)快速排序算法的性能取決于劃分的對(duì)稱(chēng)性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱(chēng)的。算法描述：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 線(xiàn)性時(shí)間選擇,元素選擇問(wèn)題：給定線(xiàn)性序集中n個(gè)元素和一個(gè)整數(shù)k，1≤k≤n，要求找出這n個(gè)元素中第k小的元素。RandomizedSelect算法：模仿快速排序算法，首先對(duì)輸入數(shù)組進(jìn)行劃分，然后對(duì)劃分出的子數(shù)組之一進(jìn)行遞歸處理。算法描述如下：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);}算法復(fù)雜性：在最壞情況下，算法randomizedSelect

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

45、算法所需的計(jì)算時(shí)間T(n)滿(mǎn)足遞歸式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。,40,一個(gè)較好的基準(zhǔn)劃分步驟,步驟（如圖所示）：將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è)元素作為劃分

46、基準(zhǔn)。說(shuō)明：設(shè)所有元素互不相同。在這種情況下，找出的基準(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)n≥75時(shí)，3(n-5)/10≥n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。,圖2-7 選擇劃分基準(zhǔn)其中，n個(gè)元素用小圓點(diǎn)表示，　　　空心圓點(diǎn)為每組元素的中位數(shù)；　　

47、　x為中位數(shù)的中位數(shù)；　　　箭頭由較大元素指向較小元素。只要等于基準(zhǔn)的元素不太多，利用這個(gè)基準(zhǔn)來(lái)劃分的兩個(gè)數(shù)組的大小就不會(huì)相差太遠(yuǎn)。,41,算法描述及復(fù)雜性分析,private static Comparable select (int p, int r, int k){//用某個(gè)簡(jiǎn)單排序算法對(duì)數(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);},復(fù)雜度分析 C1為直接簡(jiǎn)單排序時(shí)間C2n為執(zhí)行for循環(huán)的時(shí)間解遞歸方程得T(n)=O(n)說(shuō)明：上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式

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

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

52、n個(gè)實(shí)數(shù)x1,x2,…,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。一個(gè)簡(jiǎn)單的辦法是先把x1,x2,…,xn排好序，再進(jìn)行一次線(xiàn)性?huà)呙杈涂梢哉页鲎罱咏c(diǎn)對(duì)，T(n)=O(nlogn)。然而這種方法無(wú)法推廣到二維情形。假設(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|

53、,|q1-q2|}，S中的最接近點(diǎn)對(duì)或者是{p1,p2}，或者是{q1,q2}，或者是某個(gè){p3,q3}，其中p3∈S1且q3∈S2。能否在線(xiàn)性時(shí)間內(nèi)找到p3,q3？,44,算法描述及復(fù)雜性,如果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的

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

55、決：選取各點(diǎn)坐標(biāo)的中位數(shù)作分割點(diǎn)。,算法描述：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;}復(fù)雜性分析： T(n)=O(nlogn)該算法可推廣到二維的情形中去。,45,二維空間的最接近點(diǎn)對(duì)問(wèn)題,下面

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

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

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

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

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

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

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