1、算法設(shè)計(jì)與分析,山東師范大學(xué)信息科學(xué)與工程學(xué)院軟件工程研究所 徐連誠(chéng) E-Mail： 2006年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 線性時(shí)間選擇 2.10 最接近點(diǎn)對(duì)問(wèn)題 2.11 循環(huán)賽日程表 計(jì)劃授課時(shí)間：68課時(shí),3,2.1 遞歸的概念,直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 在計(jì)算機(jī)算法設(shè)計(jì)與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡(jiǎn)

2、潔且易于理解。 下面來(lái)看幾個(gè)實(shí)例。,4,2.1 遞歸的概念,例1 階乘函數(shù) 可遞歸地定義為： 其中： n=0時(shí)，n!=1為邊界條件 n0時(shí)，n!=n(n-1)!為遞歸方程 邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。,5,2.1 遞歸的概念,例2 Fibonacci數(shù)列 無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為Fibonacci數(shù)列。它可以遞歸地定義為： 第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下： public static int fibonacci(int n) if (n = 1) return 1; retu

3、rn fibonacci(n-1)+fibonacci(n-2); ,小兔子問(wèn)題,6,2.1 遞歸的概念,例3 Ackerman函數(shù) 當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身定義時(shí)，稱這個(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+2 M=1時(shí)，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2時(shí)，A(n,2

4、)=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)= 2n 。 M=3時(shí)，類似的可以推出 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(n，n)。 定義其擬逆函數(shù)(n)為：(n)=minkA(k)n。即(n)是使nA(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è)

5、遞歸算法生成n個(gè)元素r1,r2,rn的全排列。 設(shè)R=r1,r2,rn是要進(jìn)行排列的n個(gè)元素，Ri=R-ri。 集合X中元素的全排列記為perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一個(gè)排列前加上前綴得到的排列。R的全排列可歸納定義如下： 當(dāng)n=1時(shí)，perm(R)=(r)，其中r是集合R中唯一的元素； 當(dāng)n1時(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+n2+nk， 其中n1n2nk1，k1。 正整數(shù)n的這種表示稱為正整數(shù)n

6、的劃分。求正整數(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è)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，n1；當(dāng)最大數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式：n=1+1+

7、.+1(共n個(gè))。 Q(n,m)=q(n,n)，mn；最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。 q(n,n)=1+q(n,n-1)；正整數(shù)n的劃分由n1=n的劃分和n1n-1的劃分組成。 q(n,m)=q(n,m-1)+q(n-m,m),nm1；正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1m-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)要求將塔座

8、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)之上； 在滿足移動(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); 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 遞歸的概念,遞歸小

9、結(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)化為非遞歸算法。 采用一個(gè)用戶定義的棧來(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 分治法的基本思想,分治法的基本

10、思想 分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(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ù)是也。 孫子兵法,15,2.2 分治法的基本思想,16,2.2 分治法的基本思想,分治法的適用條件 分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征： 該問(wèn)

11、題的規(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)題。 這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。,17,2.2 分治法的基本思想,分治法的基本步驟 divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問(wèn)題 divide P into smaller

12、 subinstances P1,P2,.,Pk；/分解問(wèn)題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問(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ī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的

13、子問(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)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)minmi+1時(shí)，T(mi)T(n)T(mi+1)。,19,2.3 二分搜索技術(shù),給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)

14、要在這n個(gè)元素中找出一特定元素x。 適用分治法求解問(wèn)題的基本特征： 該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決； 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題; 分解出的子問(wèn)題的解可以合并為原問(wèn)題的解； 分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。,20,算法及其復(fù)雜性,據(jù)此容易設(shè)計(jì)出二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right =

15、middle - 1; return -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) 效率太低 分治法: X=a2n/2+b Y=c2n/2+d XY=ac2n+(ad+bc)2n/2+bd 復(fù)雜度分析 T(n)=O(n2) 沒(méi)有改進(jìn),22,

16、算法改進(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ù)雜一些，但它們僅需要3次n/2位乘法ac、bd和(ac)(bd)，于是 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)效率太低 分

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

18、25,簡(jiǎn)單分治法求矩陣乘,首先假定n是2的冪。使用與上例類似的技術(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次。為此，Strassen提出了一種只用7次乘法運(yùn)算計(jì)算2階方陣乘積的方法（但增加了加/減法次數(shù)）： M1=A11(B12-B22)M2=(A11+A12)B22 M3=(A21+A22)B11M4=A22(B21-B11) M5=(A11+A22)(B11+B22)M6=(

19、A12-A22)(B21+B22) M7=(A11-A21)(B11+B12) 做了這7次乘法后，在做若干次加/減法就可以得到： C11=M5+M4-M2+M6C12=M1+M2 C21=M3+M4C22=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ì)算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究33或55矩陣的更好算法。 在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性

20、。 目前最好的計(jì)算時(shí)間上界是 O(n2.376) 是否能找到O(n2)的算法？目前為止還沒(méi)有結(jié)果。,28,2.6 棋盤(pán)覆蓋,在一個(gè)2k2k個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤(pán)為一特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。 易知，覆蓋任意一個(gè)2k2k的特殊棋盤(pán)，用到的骨牌數(shù)恰好為(4K-1)/3。,29,分治策略求解,當(dāng)k0時(shí)，將2k2k棋盤(pán)分割為4個(gè)2k-12k-1 子棋盤(pán)(a)所示。特殊方格必位于4個(gè)較小子棋盤(pán)之一中，其余3個(gè)子棋盤(pán)中無(wú)特殊方格。為了將這

21、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。,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 號(hào)L型骨牌覆蓋左下角 boa

22、rdtr + s - 1tc + s = t; / 覆蓋其余方格 CB(tr,tc+s,tr+s-1,tc+s, s);,/ 覆蓋左下角子棋盤(pán) if (dr = tr + s ,31,復(fù)雜度分析,說(shuō)明： 整形二維數(shù)組Board表示棋盤(pán)，Borad00使棋盤(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)； size：size=2k，棋盤(pán)規(guī)格為2k2k。 復(fù)雜度分析： T(k)=4k-1=O(4k) 漸進(jìn)意義下的最優(yōu)算法,32,2.7 合并排序,基本思想：

23、將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 遞歸算法描述： public static void mergeSort(Comparable a, int left, int right) if (leftright) /至少有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ù)組b copy(a, b, left, right); /復(fù)制回?cái)?shù)組

24、a 復(fù)雜度分析 T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法,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ù)雜性,算法描述：略 復(fù)雜性分析： 最壞時(shí)間復(fù)雜度：O(nlogn) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n) 思考題：給定有序表A1:n，修改合并排序算法，求出該有序表的逆序?qū)?shù)。,35,2.8 快速排序,快速排序是基于分治策略的另

25、一個(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ò)程中確定； 遞歸求解通過(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ù)較少

26、。 快速算法描述： template void 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ì)右半段排序 ,36,分解/劃分算法描述,分解/劃分算法描述： template int 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

27、 = j) break; Swap(ai, aj); ap = aj; aj = x; return j; ,6, 7, 51, 2, 5, 8 初始序列 6, 7, 51, 2, 5, 8 j-; ij 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, 5167, 8 完成 快速排序具有不穩(wěn)定性！,37,復(fù)雜性分析及隨機(jī)化的快速排序算法,算法復(fù)雜性分析： 最壞時(shí)間復(fù)雜度：O(n2) 平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n)或O(logn) 快速排序算法的性能取決于

28、劃分的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。 算法描述： template int RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r); ,38,2.9 線性時(shí)間選擇,元素選擇問(wèn)題：給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元

29、素中第k小的元素。 RandomizedSelect算法：模仿快速排序算法，首先對(duì)輸入數(shù)組進(jìn)行劃分，然后對(duì)劃分出的子數(shù)組之一進(jìn)行遞歸處理。算法描述如下： template Type RandomizedSelect(Type a,int p,int r,int k) 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); 算法復(fù)雜性：在最壞情況下，算法ra

30、ndomizedSelect需要O(n2)計(jì)算時(shí)間。但可以證明，算法RandomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。,39,改進(jìn)算法,基本思路：如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的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)。,40,一個(gè)較好的基準(zhǔn)劃分步驟,步驟（如圖所示）：

31、將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è)元素作為劃分基準(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)n75時(shí)，3(n-5)/10n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短

32、1/4。,圖2-7 選擇劃分基準(zhǔn) 其中，n個(gè)元素用小圓點(diǎn)表示， 空心圓點(diǎn)為每組元素的中位數(shù)； 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ù)組ap:r排序; if (r-p75) bubbleSort(p,r); return ap+k-1; /將ap+5*i至ap+5*i+4的第3小元素與ap+i交換; /找中位數(shù)的中位數(shù)，r-p-4即前述n-5;

33、for ( int i = 0; i=(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ù)雜度分析 C1為直接簡(jiǎn)單排序時(shí)間 C2n為執(zhí)行for循環(huán)的時(shí)間 解遞歸方

34、程得T(n)=O(n) 說(shuō)明： 上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n/5+3n/4=19n/20=n，01。這是使T(n)=O(n)的關(guān)鍵之處。當(dāng)然，除了5和75之外，還有其他選擇。 上述算法中我們假設(shè)元素互不相等已保證劃分后子數(shù)組不超過(guò)3n/4。當(dāng)元素可能相等時(shí)，設(shè)有m個(gè)（將他們集中起來(lái)），若jkj+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è)點(diǎn)所組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。 說(shuō)明： 嚴(yán)格

35、來(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軸上的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)行一次線性掃描就可以找出最接近點(diǎn)對(duì)，T(n)=O(nlogn)。然而這種方法無(wú)法推廣到二維情形。

36、 假設(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|，S中的最接近點(diǎn)對(duì)或者是p1,p2，或者是q1,q2，或者是某個(gè)p3,q3，其中p3S1且q3S2。 能否在線性時(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和

37、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)m的選取不當(dāng)，會(huì)造成|Si|=1，|Sj|=n-1(i+j=1)的情形，使得T(n) =T(n-1)+O(n)=O(n2)。這種情形可以通過(guò)“平衡子問(wèn)題”方法加以解決：選取各點(diǎn)坐標(biāo)的中位數(shù)作分割點(diǎn)。,算法描述： bool CPair1(S, d) n=|S|; if (nS1+S2;/S1=x|xm CPair1(S1, d

38、1); 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)題,下面來(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 ，如圖2-9所示。 能否在線性時(shí)間內(nèi)找到p,q？ 考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d2d的矩形R中，如圖2-10所示。 由d的意義可知，P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個(gè)S中的點(diǎn)。,圖2-9距離直線l小于d的所有點(diǎn),圖2-10包含q的d2d矩形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)所示