算法設(shè)計(jì)與分析第二章遞歸與分治策略

1、算法設(shè)計(jì)與分析第二章 遞歸與分治策略楊圣洪 學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）棋盤覆蓋；（5）合并排序和快速排序；（6）線性時(shí)間選擇；（7）最接近點(diǎn)對(duì)問(wèn)題；（8）循環(huán)賽日程表。2第2章 遞歸與分治策略本章主要知識(shí)點(diǎn)：2.1 遞歸的概念2.2 分治法的基本思想2.3 二分搜索技術(shù)2.4 大整數(shù)的乘法2.5 Strassen矩陣乘法2.6 棋盤覆蓋2.7 合并排序2.8 快速排序2.9 線性時(shí)間選擇2.10 最接近點(diǎn)對(duì)問(wèn)題2.11 循環(huán)賽日程表計(jì)劃授課時(shí)間：68課時(shí)

2、32.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計(jì)算機(jī)算法設(shè)計(jì)與分析中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡(jiǎn)潔且易于理解。下面來(lái)看幾個(gè)實(shí)例。42.1 遞歸的概念例1 階乘函數(shù)可遞歸地定義為：高低其中：n=0時(shí)，n!=1為邊界條件n0時(shí)，n!=n(n-1)!為遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果。T=1;for (i=2;in+1;i+) T=T*i; 循環(huán)低高52.1 遞歸的概念例2 Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，被稱為F

3、ibonacci數(shù)列。遞歸地定義：第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：public static int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); pubic static int fibonacciLoop(int n) f0=1;f1=1; for (i=2;i1時(shí)，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)構(gòu)成。92.1 遞歸的概念例5 整數(shù)劃分問(wèn)題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1

4、，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。102.1 遞歸的概念如果設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)則難以找到遞歸關(guān)系換函數(shù)q(n,m) ：最大加數(shù)n1 m 時(shí)n的劃分個(gè)數(shù)。q(n,m)的如下遞歸關(guān)系：q(n,1)=1，n1；最大加數(shù) 1時(shí)，任何正整數(shù)n只有一種劃分形式：n=1+1+.+1(共n個(gè))。q(n,m)=q(n,n)，mn；最大加數(shù)nq(1,m)=1。q(n,n)=1+q(n,n

5、-1)；n的劃分=最大加數(shù)=n的劃分最大加數(shù)n-1的劃分。q(n,m)=q(n,m-1)+q(n-m,m),nm1；最大加數(shù) m的劃分=最大加數(shù)m-1 的劃分最大加數(shù)n1=m的劃分 = =最大加數(shù)m-1 的劃分最大加數(shù)n1+(n-n1)即(n-m) 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è)圓盤從a全部移動(dòng)到d，移動(dòng)規(guī)則不變，求移動(dòng)步數(shù)最小的方案。132.1 遞歸的概念5個(gè)盤子循環(huán)1號(hào)順移B :2345 1 _2號(hào)到C: 345 1 2 1號(hào)順移C :345 _ 123號(hào)到B: 4

6、5 3 121號(hào)順移A : 145 3 2 2號(hào)到B: 145 23 _1號(hào)順移B : 45 123 _ 4號(hào)到C: 5 123 4 1號(hào)順移C : 5 23 142到A:25 3 141號(hào)順移A:125 3 4 3號(hào)到C:125 _ 341號(hào)順移B:25 1 342號(hào)到C：5 1 234 1號(hào)順移C:5 _ 1234到B：_ 5 12341號(hào)順移A:1 5 2342到B：1 25 341號(hào)順移B:_ 125 343到A：3 125 41號(hào)順移C:3 25 14 2到A:23 5 141號(hào)順移A:123 5 44到B:123 45 _1號(hào)順移B:23 145 _2到C:3 145 21號(hào)順移C

7、:3 45 123到B :_ 345 12 142.1 遞歸的概念遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，且用數(shù)學(xué)歸納法證明正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸運(yùn)行效率較低，時(shí)間,空間比非遞歸多。解決方法：消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。自頂向下保存現(xiàn)場(chǎng)用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。通過(guò)Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。討論題：遞歸的執(zhí)行過(guò)程如何？152.2

8、分治法的基本思想分治法的基本思想將一個(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)題的解。將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。凡治眾如治寡，分?jǐn)?shù)是也。孫子兵法16練習(xí)1,算法分析的基本原則有哪些？2,試設(shè)計(jì)一算法，實(shí)現(xiàn)有31個(gè)網(wǎng)球運(yùn)動(dòng)員參加比賽的循環(huán)賽日程表。且簡(jiǎn)要分析你設(shè)計(jì)算法的時(shí)間和空間復(fù)雜性。31*31矩

9、陣,主對(duì)角線為0,每行中1-31只能出現(xiàn)一次,每列也是如此.討論題：什么時(shí)候可使用遞歸？程序中遞歸的執(zhí)行過(guò)程如何？17分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：1,該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決；2,該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)3,利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；4,該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于

10、問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，一般用動(dòng)態(tài)規(guī)劃.2.2 分治法的基本思想分治法的適用條件182.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

11、-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ī)模不等的做法要好。云計(jì)算mapreduce192.2 分治法的基本思想分治法的復(fù)雜性分析一個(gè)分治法將規(guī)模為n的問(wèn)題分成k個(gè)規(guī)模為nm的子問(wèn)題去解。分解閾值n0=1，adhoc解耗費(fèi)1個(gè)單位時(shí)間。將原問(wèn)題分解為k個(gè)子問(wèn)題以及用merge將k個(gè)子問(wèn)

12、題的解合并為原問(wèn)題的解需用f(n)個(gè)單位時(shí)間。分治法解規(guī)模為|P|=n的問(wèn)題所需的計(jì)算時(shí)間，則有（右上）。通過(guò)迭代法求得其規(guī)模為右下 。注意：遞歸方程及其解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(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)。202.3 二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。適用分治法求解問(wèn)題的基本特征：分形術(shù)問(wèn)題規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解

13、出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 二分法：在a0:i與ai+1:n-1各自查找x，滿足分治法的四個(gè)適用條件。21算法及其復(fù)雜性據(jù)此容易設(shè)計(jì)出二分搜索算法：public static int binarySearch(int a, int x, int n)/ 在 a0 = a1 = . = an-1 中搜索 x/ 找到x時(shí)返回其在數(shù)組中的位置，否則返回-1int left = 0; int right = n - 1;while (left amiddle) left = middle + 1;else right = middle - 1;return -

14、1; / 未找到x算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。最壞情況任意二個(gè)相鄰元素都要分劃到，即2m=n,log2n=m因此，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。22Template (class Type)Int BinarySearch1(Type a,const Type& x,int n) Int left=0;int right=n-1;While (leftamiddle) left = middle; else right=middle; retu

15、rn -1; Template (class Type)Int BinarySearch2(Type a,const Type& x,int n) Int left=0;int right=n-1;While (leftright-1) int middle=(left+right)/2; if (x=amiddle) left = middle; else right=middle; if (x=aleft) return left; else return -1;Template (class Type)Int BinarySearch4(Type a,const Type& x,int

16、n) If (n0 & x=a0) Int left=0;int right=n-1;While (leftright) int middle=(left+right)/2; if (xamiddle) right = middle-1; else left=middle; if (x=aleft) return left; return -1;習(xí)題2-2/p351. 與主教材中的算法BinarySearch相比，數(shù)組段左、右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致陷入死循環(huán)。2. 與主教材中的算法BinarySearch相比，數(shù)組段左、右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an

17、-1時(shí)返回錯(cuò)誤。3. 與正確算法BinarySearch5相比，數(shù)組段左、右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致當(dāng)x=an-1時(shí)返回錯(cuò)誤。4. 與正確算法BinarySearch5相比，數(shù)組段左、右游標(biāo)left和right的調(diào)整不正確，導(dǎo)致陷入死循環(huán)。232.4 大整數(shù)的乘法設(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算。分成二段再相乘，即分治也小學(xué)的方法：O(n2) 效率太低分治法: X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd復(fù)雜度分析 T(n)=O(n2) 沒(méi)有改進(jìn) n/2位 n/2位 n/2位 n/2位X=Y=ABCD24算法改進(jìn)為了降低

18、時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。為此，我們把XY寫成另外的形式：XY = ac 2n + (a-b)(d-c)+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種方案。25更快的方法小學(xué)的方法：O(n2)效率太低分治法: O(n1.59)較大的改進(jìn)更

19、快的方法？如果將大整數(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é)果。FFT?26課堂練習(xí)習(xí)題2-4 大整數(shù)乘法的O(nmlog3/2) 給定2個(gè)大整數(shù)u和v,他們分別有m位和n位數(shù)字，且m0時(shí)，將2k2k棋盤分割為4個(gè)2k-12k-1 子棋盤(a)所示。 特殊方格必位于4個(gè)較小子棋盤之一，其余3個(gè)無(wú)特殊方格。 為了將這3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋

20、盤，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處， 如 (b)！關(guān)鍵。 從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的特殊棋盤覆蓋問(wèn)題即4個(gè)同樣的小問(wèn)題,直至棋盤簡(jiǎn)化為棋盤11。其他三種情況，畫在黑板上35分治策略求解CB(tr,tc,dr,dc,size):tr,tc是四小塊中某塊左上角在原始圖中行號(hào)列號(hào)dr,dc是該小塊中不能用L型磚覆蓋的地方size:該小塊寬目標(biāo)除特殊塊以外，其他位置用L型磚覆蓋。36算法描述void CB(int tr,tc,dr,dc,size)if (size = 1) return;int t = tile+; / L型骨牌號(hào)s = size/2; / 分割棋盤/ 覆蓋左上角

21、子棋盤if (dr tr + s & dc tc + s)/ 此塊左上角為(tr,tc)CB(tr, tc, dr, dc, s);else / 無(wú)特殊方格/ 用 t 號(hào)L型骨牌覆蓋右下角boardtr + s - 1tc + s - 1 = t;/ 再處理CB(tr, tc, tr+s-1, tc+s-1, s);/ 覆蓋右上角子棋盤if (dr = tc + s)/ 此塊左上角為(tr,tc+s)CB(tr, tc+s, dr, dc, s);else / 無(wú)特殊方格/ 用 t 號(hào)L型骨牌覆蓋左下角boardtr + s - 1tc + s = t;/ 再處理CB(tr,tc+s,tr+s

22、-1,tc+s, s);/ 覆蓋左下角子棋盤if (dr = tr + s & dc = tr + s & dc = tc + s)/此塊左上角為(tr+s,tc+s) CB(tr+s, tc+s, dr, dc, s);else / 用 t 號(hào)L型骨牌覆蓋左上角boardtr + stc + s = t;/ 再處理CB(tr+s, tc+s, tr+s, tc+s, s);37復(fù)雜度分析說(shuō)明：整形二維數(shù)組Board表示棋盤，Borad00是棋盤的左上角方格。tile是全局整形變量，表示L形骨牌的編號(hào)，初始值為0。tr:棋盤左上角方格的行號(hào)；tc:棋盤左上角方格的列號(hào)；dr:特殊方格所在的行號(hào)

23、；dc:特殊方格所在的列號(hào)；size：size=2k，棋盤規(guī)格為2k2k。復(fù)雜度分析： T(k)=4k-1=O(4k) 漸進(jìn)意義下的最優(yōu)算法38非遞歸求解-分治策略求解CB2(dr,dc,size):dr,dc是該小塊中不能用L型磚覆蓋的地方size:該小塊寬基本思想：以8*8為例在黑板上演示 (1)分成4塊，當(dāng)每塊格子數(shù)4時(shí)，將每個(gè)4個(gè)格子的連接處用L型條子覆蓋。 (2)每塊又分成4塊。當(dāng)每塊格子數(shù)4時(shí)，將每個(gè)4個(gè)格子的連接處用L型條子覆蓋。 (3)當(dāng)每塊格子數(shù)為4后，不再細(xì)分，針對(duì)每4個(gè)格子用L型覆蓋。 39算法描述void CB2(dr,dc,size)var t=1; if (size

24、=2) for (i=0;isize;i=i+sizesub*2) for (j=0;jsize;j=j+sizesub*2) /判斷左上角是否變臟了 t+; sumTmp=0; for (dr1=0;dr1sizesub;dr1+) for (dc1=0;dc1sizesub;dc1+) sumTmp+=Boarddr1+idc1+j; if (sumTmp=0) Boardi+sizesub-1j+sizesub-1=t; /判斷右上角是否臟了 sumTmp=0; for (dr1=0;dr1sizesub;dr1+) for (dc1=0;dc1sizesub;dc1+) sumTmp+

25、=Boarddr1+idc1+sizesub+j; if (sumTmp=0) Boardi+sizesub-1j+sizesub=t; /判斷左下角是否臟了 sumTmp=0; for (dr1=0;dr1sizesub;dr1+) for (dc1=0;dc1sizesub;dc1+) sumTmp+=Boarddr1+sizesub+idc1+j; if (sumTmp=0) Boardi+sizesubj+sizesub-1=t; /判斷右下角是否臟了 sumTmp=0; for (dr1=0;dr1sizesub;dr1+) for (dc1=0;dc1sizesub;dc1+) s

26、umTmp+=Boarddr1+sizesub+idc1+sizesub+j; if (sumTmp=0) Boardi+sizesubj+sizesub=t; sizesub=sizesub/2; 40算法描述/最后都是2行2列的未處理完 for (i=0;isize;i=i+2) for (j=0;jsize;j=j+2) /處理一個(gè)小四塊 for (dr1=0;dr12;dr1+) for (dc1=0;dc12;dc1+) if (Boarddr1+idc1+j=0) Boarddr1+idc1+j=t; t+; 非遞歸算法也可以解決，關(guān)鍵在于細(xì)心的觀察！41課堂思考為什么必須是2k2

27、k的方格？422.7 排序最原始的排序方法？給出代碼冒泡法：從后往前兩兩比較，小的往前，一輪又一輪 給出代碼插入排序 給出代碼合并排序自然排序快速排序線性時(shí)間選擇432.7 合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集，分別對(duì)2個(gè)子集合進(jìn)行排序，將排好序的子集合合并成為所要求的排好序的集合。 直到子集中只有1個(gè)元素為止，然后再兩兩合并。遞歸算法描述：public static void mergeSort(Comparable a, int left, int right)if (leftright) /至少有2個(gè)元素int i=(left+right)/2; /取中點(diǎn),一定要取整

28、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)算法44算法改進(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 9745非遞歸算法描述及其復(fù)雜性算法描述：直接在板上演示MergeS

29、ortMergePassMerge46Conti復(fù)雜性分析：最壞時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)思考題：給定有序表a1:n，修改合并排序算法，求出該有序表的逆序?qū)?shù)。自然合并排序?47Conti在一種極端情況：序列已排好序自然合并排序： O(n)合并排序：O(nlogn)一般情況下，自然合并排序所需的合并次數(shù)較少。48課堂練習(xí)習(xí)題2-13：n1/2段合并排序算法如果在合并排序算法的分段步驟中，將數(shù)組a0,n-1劃分為n1/2個(gè)子數(shù)組，每個(gè)子數(shù)組有O(n1/2)個(gè)元素。然后遞歸地對(duì)分段后的子數(shù)組進(jìn)行排序，最后將所得到的n1/2個(gè)排好序的子數(shù)組合并成所

30、要求的排好序的a0,n-1。設(shè)計(jì)一個(gè)實(shí)現(xiàn)上述策略的合并排序算法，并分析算法的計(jì)算復(fù)雜性。習(xí)題2-14：自然合并排序算法對(duì)所給元素存儲(chǔ)于數(shù)組中和存儲(chǔ)于鏈表中2種情形，寫出自然合并排序算法。492.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ò)程中確定；遞歸求解通過(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都已排好

31、序后不需要執(zhí)行任何計(jì)算ap：r就已排好序。在快速排序中，記錄的比較和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動(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ì)右半段排序50分解/劃分算法描述分解/劃分算

32、法描述：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; Swap(ai, aj);ap = aj;aj = x;return j;6, 7, 51, 2, 5, 8 初始序列6, 7, 51, 2, 5, 8 j-;ij5, 7, 51, 2, 6, 8 i+; i j5, 6, 51, 2, 7, 8 j-; i j5, 2, 51, 6, 7, 8 i+;i j5, 2

33、, 5167, 8 完成快速排序具有不穩(wěn)定性！51復(fù)雜性分析及隨機(jī)化的快速排序算法算法復(fù)雜性分析：最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)52Conti快速排序算法的性能取決于劃分的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。算法描述：templateint RandomizedPartition (Type a, int p, int r)int i

34、 = Random(p,r);Swap(ai, ap);return Partition (a, p, r);532.9 線性時(shí)間選擇元素選擇問(wèn)題：給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素。RandomizedSelect算法：模仿快速排序算法，首先對(duì)輸入數(shù)組進(jìn)行劃分，然后對(duì)劃分出的子數(shù)組之一進(jìn)行遞歸處理。算法描述如下：templateType 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=

35、j) return RandomizedSelect(a,p,i,k);else return RandomizedSelect(a,i+1,r,k-j);54時(shí)間復(fù)雜性分析RandomizedSelectRandomizedPartitionPartition快速排序算法中的隨機(jī)化劃分，T(n)?快速排序算法中的劃分，O(nlogn)最壞情況下， Omega(n2)比如要找最小元素，但總是在最大元素處劃分算法復(fù)雜性：在最壞情況下，算法randomizedSelect需要O(n2)計(jì)算時(shí)間。但可以證明，算法RandomizedSelect可以在O(n)平均時(shí)間內(nèi)找出n個(gè)輸入元素中的第k小元素。

36、55改進(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)。T(n)+O(n)56一個(gè)較好的基準(zhǔn)劃分步驟步驟（如圖所示）：將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共n/5個(gè)。遞歸調(diào)

37、用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)度都至少縮短1/4。圖2-7 選擇劃分基準(zhǔn)其中，n個(gè)元素用小圓點(diǎn)表示，空心圓點(diǎn)為每組元素的中位數(shù)；x為中位數(shù)的中位數(shù)；箭頭由較大元素指向較小元素。只要等于基準(zhǔn)的元素不太多，

38、利用這個(gè)基準(zhǔn)來(lái)劃分的兩個(gè)數(shù)組的大小就不會(huì)相差太遠(yuǎn)。ai3(n-5)/10aixn/5+(n/5-1)/23(n-5)/1057算法描述及復(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;for ( int i = 0; i=(r-p-4)/5; i+ )int s=p+5*i,t=s+4;for (i

39、nt 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í)間解遞歸方程得T(n)=O(n)說(shuō)明：上述算法將每一組的大小定為5，并選取75作為是否作遞歸調(diào)用的分界點(diǎn)。這2點(diǎn)保證了T(n)的遞歸式中2個(gè)自變量之和n

40、/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)。58課堂練習(xí)習(xí)題2-11 O(1)空間子數(shù)組換位算法設(shè)a0,n-1是一個(gè)有n個(gè)元素的數(shù)組，k是一個(gè)非負(fù)整數(shù)。試設(shè)計(jì)一個(gè)算法將子數(shù)組a0,k-1與ak,n-1換位。要求算法在最壞情況下耗時(shí)O(n)，且只用到O(1)的輔助空間。習(xí)題2-12 O(1)空間合并算法設(shè)a0,k-1和ak,n-1)已排

41、好序。試設(shè)計(jì)一個(gè)算法將這兩個(gè)子數(shù)組合并為排好序的數(shù)組a0,n-1)。要求算法在最壞情況下所用的計(jì)算時(shí)間為O(n)，且只用到O(1)的輔助空間。592.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)格來(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)。60一維空間中的情形為了使問(wèn)題易于理解和分析，先來(lái)

42、考慮一維的情形。此時(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ú)法推廣到二維情形。假設(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)找到

43、p3,q3？61算法描述及復(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的分割點(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(

44、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|xmCPair1(S1, d1);CPair1(S2, d2);p=max(S1);q=min(S2);d=min(d1, d2, q-p);return ture;復(fù)雜性分析： T(n)=O(nlogn)該算法可推廣到二維的情形中去。62二維空間的最接近點(diǎn)對(duì)問(wèn)題下面來(lái)考慮二維的情形。選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S

45、1和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矩形R63R中至多包含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中的點(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中最多有