第2章-遞歸與分治策略

第2章遞歸與分治策略上海大學(xué)計(jì)算機(jī)學(xué)院主要內(nèi)容2.1遞歸的概念2.2分治法的基本思想2.3二分搜索技術(shù)2.4大整數(shù)的乘法2.5Strassen矩陣乘法2.6棋盤覆蓋2.7合并排序（自學(xué)）2.8快速排序（自學(xué)）2.9線性時(shí)間選擇2.10最接近點(diǎn)對(duì)問(wèn)題2.11循環(huán)賽日程表學(xué)習(xí)要點(diǎn)

理解遞歸的概念，掌握遞歸程序編寫方法。根據(jù)一些問(wèn)題，求解較簡(jiǎn)單的遞推方程。掌握分治算法的分析方法，能確定常見(jiàn)問(wèn)題的復(fù)雜性的階通過(guò)典型范例，學(xué)習(xí)分治策略設(shè)計(jì)技巧。2.1遞歸的概念遞歸算法：一個(gè)直接或間接地調(diào)用自身的算法遞歸函數(shù)：使用函數(shù)自身給出定義的函數(shù)遞歸方程：對(duì)于遞歸算法，一般可把時(shí)間代價(jià)表示為一個(gè)遞歸方程解遞歸方程最常用的方法是進(jìn)行遞歸擴(kuò)展遞歸函數(shù)舉例(1,2)階乘函數(shù)

n！=1n=1n(n-1)！n>1Fibonacci數(shù)列

F(n)=1n=0F(n-1)+F(n-2)n>11n=1初始條件與遞歸方程是遞歸函數(shù)的二個(gè)要素遞歸函數(shù)舉例(3)Ackerman函數(shù)

A(1,0)=2Ackerman函數(shù):雙遞歸函數(shù)A(0,m)=1m>=0A(n,0)=n+2n>=2A(n,m)=A(A(n-1,m),m-1)n,m>=1雙遞歸函數(shù)：一個(gè)函數(shù)及它的一個(gè)變量由函數(shù)自身定義A(n，m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)Fm(n)

遞歸函數(shù)舉例(3)Ackerman函數(shù)的性狀m=0時(shí)，A(n,0)=n+2,n>=2；A(1,0)=2m=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í)，類似的可以推出m=4時(shí)，A(n,4)的增長(zhǎng)速度非?？?，以至于沒(méi)有適當(dāng)?shù)臄?shù)學(xué)式子來(lái)表示這一函數(shù)。遞歸函數(shù)舉例(3)單變量的Ackerman函數(shù)A(n)定義為

A(n)=A(n，n)。定義其擬逆函數(shù)α(n)為：

α(n)=min{k｜A(k)≥n}。α(n)：隨n的增長(zhǎng)非常慢Ackerman函數(shù)的作用遞歸函數(shù)舉例(4)排列問(wèn)題設(shè)R={r1，r2，…，rn}是要進(jìn)行排列的n個(gè)元素，Ri=R－{ri}。集合X中元素的全排列記為Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一個(gè)排列前加上前綴ri得到的排列。R的全排列可歸納定義如下：當(dāng)n＝l時(shí)，Perm(R)=（r），其中r是集合R中唯一的元素；當(dāng)n>l時(shí)，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),…,(rn)Perm(Rn)構(gòu)成。產(chǎn)生置換Perm(R)的遞歸算法voidSwap(Type&a,Type&b)//Swap是交換a，b的值voidPerm(Typelist[],intk,intm){//生成全部排列l(wèi)ist[k:m].if(k==m){for(inti=0;i<=m;i++)cout<<list[i];cout<<endl;}else//list[k:m]有多于一個(gè)置換，遞歸產(chǎn)生

for(inti=k;i<=m;i++){Swap(list[k],1ist[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}調(diào)用Perm(list,0,n-1)遞歸函數(shù)舉例(5)整數(shù)劃分問(wèn)題將一個(gè)正整數(shù)n表示成一系列正整數(shù)之和，

n＝

n1+n2+…+nk，其中，n1

n2…nk

分劃數(shù)，p(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。對(duì)偶圖形及其問(wèn)題轉(zhuǎn)化遞歸函數(shù)舉例(5)q(n,m):正整數(shù)n的不同的劃分中，最大加數(shù)不大于m的劃分個(gè)數(shù)1n=1,m=1q(n,n)n<m1+q(n,n-1)n=mq(n,m-1)+q(n-m,m)n>m>1q(n,m)=整數(shù)劃分問(wèn)題的遞歸關(guān)系q(n,m)如設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系通過(guò)打表形式可以計(jì)算q(n,m)遞歸函數(shù)舉例(6)“Hanoi塔”問(wèn)題：設(shè)a,b,c是3個(gè)塔座。開(kāi)始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1,2,…,n,現(xiàn)要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤；規(guī)則2：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；規(guī)則3：在滿足移動(dòng)規(guī)則1和2的前提下，可將圓盤移至a,b,c中任一塔座上。abcacbbcaabc初始步驟1步驟2步驟3“Hanoi塔”問(wèn)題演示

“Hanoi塔”問(wèn)題程序voidhanoi(intn,a,b,c)//A上n個(gè)盤借助C移到B{if(n==1)move(1,a,b);//將1個(gè)盤從a移到belse{

hanoi(n-1,a,c,b);move(n,a,b); //將第n個(gè)盤從a移到b

hanoi(n-1,c,b,a);}}遞歸函數(shù)舉例(6)遞歸函數(shù)舉例(6)“Hanoi塔”問(wèn)題移動(dòng)次數(shù)遞推關(guān)系T(n)=2T(n-1)+1(n>1)1(n=1)遞歸程序代價(jià)遞歸程序每次調(diào)用需要分配不同的運(yùn)行空間，一旦某一層被啟用，就要為之開(kāi)辟新的空間。而當(dāng)一層執(zhí)行完畢，釋放相應(yīng)空間掉，退到上一層。當(dāng)遞歸過(guò)程每層所需空間為常量C時(shí)，整個(gè)動(dòng)態(tài)空間的代價(jià)就與遞歸的深度有關(guān)。如果遞歸深度為ｈ，動(dòng)態(tài)空間代價(jià)為C*h。遞歸優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)遞歸缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。2.2分治法分治策略是一種用得最多的一種有效方法基本思想：將問(wèn)題分解成若干子問(wèn)題，然后求解子問(wèn)題。然后由子問(wèn)題的解構(gòu)造大問(wèn)題的解。子問(wèn)題較原問(wèn)題更容易些或與大問(wèn)題類型相同就用同樣方法求解，由此得出原問(wèn)題的解，就是所謂的“分而治之”的意思。分治策略可以遞歸進(jìn)行，即子問(wèn)題仍然可以用分治策略來(lái)處理，但最后的問(wèn)題要非?；径?jiǎn)單。設(shè)：被求解問(wèn)題的輸入規(guī)模為n。步驟2：逐步合并子問(wèn)題的解，直到獲得原問(wèn)題的解。步驟1：把問(wèn)題分解為k個(gè)性質(zhì)相同、但規(guī)模較小的子問(wèn)題（1kn)，并求解這些子問(wèn)題。（如果這些子問(wèn)題的規(guī)模還不夠“小”，則可以進(jìn)一步分解，直到可以求解為止）

一、分治法概述

二、分治法算法構(gòu)架divide-and-conquer(P){if(|P|<=n0)adhoc(P);//直接解決小規(guī)模的問(wèn)題將P分解為子問(wèn)題P1,P2,...,Pk；//分解問(wèn)題

for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//遞歸地解各子問(wèn)題

returnmerge(y1,...,yk);//將各子問(wèn)題的解合并為原問(wèn)題的解

}PP1P2Pk…T1(n)T2(n)Tk(n)T(n)f(n)有：T(n)=T1(n)+T2(n)+…+Tk(n)+f(n)

三、分治法示例四、代價(jià)分析T(n)=kT(n/m)+f(n)n>1O(1)n=1記n=mt,則T(n)=ktT(1)+=klogmn

+對(duì)一般的n，如何估計(jì)T(n)？注意：遞歸方程解只給出n等于m的方冪時(shí)T(n)的值，但是如果認(rèn)為T(n)足夠平滑，那么由n=mt時(shí)T(n)的值可以估計(jì)T(n)的增長(zhǎng)速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)mi≤n<mi+1時(shí)，T(mi)≤T(n)<T(mi+1)。該處理方式有一般性。2.3二分搜索技術(shù)問(wèn)題：給定已按升序排好序的n個(gè)元素a[0:n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：需考察該問(wèn)題的規(guī)?？s小到一定的程度是否就可容易解決？該問(wèn)題可否分解為若干個(gè)規(guī)模較小的相同問(wèn)題？分解出的各個(gè)子問(wèn)題是否相互獨(dú)立的？各子問(wèn)題的解可否合并為原問(wèn)題的解？如果n=1，則只要x與這個(gè)唯一元素比較，就可以確定x是否在表中比較x和a的中間元素a[mid]，無(wú)論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過(guò)是查找的規(guī)?？s小了在a[i]的前面或后面查找x是獨(dú)立的子問(wèn)題2.3二分搜索技術(shù)

給定已排好序的n個(gè)元素a[0：n-1]，現(xiàn)要在這n個(gè)元素中找出一特定元素x。1.順序搜索方法:最好時(shí)1次，最壞時(shí)n次

2.二分搜索方法基本思想：將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與x作比較。如果x=a[n/2]，則找到x，算法終止；如果x<a[n/2]，則在數(shù)組a的左半部繼續(xù)搜索x。如果x>a[n/2]，則在數(shù)組a的右半部繼續(xù)搜索x。

二分搜索法復(fù)雜性T(n)=T(n/2)+1求解：T(n)=logn復(fù)雜性：O(logn)直觀上看，程序在最壞情況下，while循環(huán)被執(zhí)行了O(logn)次。循環(huán)體內(nèi)運(yùn)算需要O(1)時(shí)間1、評(píng)價(jià)算法的一般準(zhǔn)則算法正確性算法結(jié)構(gòu)簡(jiǎn)單性算法工作量時(shí)空復(fù)雜性：時(shí)間復(fù)雜度，空間復(fù)雜度最佳性小結(jié)算法分析的一般方法

算法分析的一般方法2、算法工作量的度量方法用執(zhí)行時(shí)間來(lái)作為算法工作量的度量用算法程序中所執(zhí)行的指令條數(shù)或語(yǔ)句條數(shù)來(lái)度量從運(yùn)算的執(zhí)行次數(shù)來(lái)度量（受問(wèn)題性質(zhì)、大小、輸入情況的影響），一般指計(jì)算所需的一些基本運(yùn)算的次數(shù)。如比較次數(shù)，加法和乘法次數(shù)，待排序元素的“移動(dòng)”次數(shù)。第①條因計(jì)算機(jī)而異，很難確定第②條與與所用的程序語(yǔ)言和程序員的習(xí)慣有關(guān)。第③條容易刻畫。需明確被分析算法的“關(guān)鍵操作”是什么nnlogn2nn512345543210nf(n)3.考察算法的“關(guān)鍵操作”數(shù)，隨“問(wèn)題規(guī)?！倍兓囊?guī)律longF(intn){longtemp;if(n==0)temp=1;elseif(n==1)temp=1;elsetemp=F(n-1)+F(n-2);returntemp;}F(n)=F(n-1)+F(n-2)(n>1)1(n=0)1(n=1)例：求Fibonacci序列的Fn通項(xiàng)表示

解：(R):F(n)=F(n-1)+F(n-2)(E):x2-x-1=0(E)的根

因?yàn)閤1

x2

所以F(n)=c1x1n+c2x2n

由F(0)=1和F(1)=1知：“Hanoi塔”問(wèn)題算法復(fù)雜性算法T(n)=2T(n-1)+k(n>1)(k:正數(shù)）k(n=1)

解：(R’):T(n)=2T(n-1)+k(R):T’(n)=2T’(n-1)(E):x-2=0x=2(R)的通解：T’(n)=c2n

因?yàn)?R’)中，f(n)=k

所以，設(shè)：T*(n)=p

顯然，T*(n-1)=p

把T*(n)、T*(n-1)代入(R’),

有：p=2p+kp=-k

故：T*(n)=-k(R’)的通解：T(n)=T’(n)+T*(n)=c2n-k

由T(1)=k,把它代入上式，有：2c-k=kc=k

(R’)的通解：T(n)=k(2n-1)=O(2n)2.4大整數(shù)的乘法問(wèn)題：設(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位大整數(shù)的乘法運(yùn)算，并分析算法關(guān)于二進(jìn)制數(shù)運(yùn)算（乘法、加法、移位）的時(shí)間復(fù)雜度。小學(xué)的方法：O(n2)效率太低分治法:已知：x、y是n位二進(jìn)制數(shù)（n=2r；r:非負(fù)正數(shù)）,a、b、c、d與x、y的關(guān)系如下所示。計(jì)算：p=xyx:aby:cdp=xy=(a2n/2+b)(c2n/2+d)=ac2n+(ad+bc)2n/2+bd1）計(jì)算ac,并將結(jié)果“左移”n位；2）分別計(jì)算ad、bc,并求它們的和，再對(duì)和數(shù)“左移”n/2位；3）計(jì)算bd;4）對(duì)1)、2)、3)的結(jié)果求和。

時(shí)間復(fù)雜度遞推式：4T(n/2)+kn(n>1)k(n=1)T(n)=

解上述遞推式，得：T(n)=2kn2-kn=O(n2)（k:正數(shù)）算法之一沒(méi)有改進(jìn)

方案1：令：u=(a+b)(c+d),v=ac,w=bd

有:p=xy=v2n+(u-v-w)2n/2+w

方案2：p=xy=ac2n+(ac+bd-(a-b)(c-d))2n/2+bd

遞推關(guān)系式：3T(n/2)+kn(n>1)c(n=1)

解上述遞推式：

T(n)=3T(n/2)+kn=3[3T(n/22)+k(n/2)]+kn

=……=3r+1

k-2kn=3k3log2n-2kn3kn1.59-2kn=O(n1.59)T(n)=

改進(jìn)算法對(duì)大整數(shù)乘法的算法思考有沒(méi)有更快的方法??如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，可否得到更優(yōu)的算法？引申：這個(gè)思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法。卷積2.5矩陣乘法若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的所有元素所需的計(jì)算時(shí)間為O(n3)A和B的乘積矩陣C=AB中的元素C[i,j]定義為:

傳統(tǒng)方法：O(n3)分治法：如何？使用技術(shù)：分塊

Cnn=Ann

Bnn(n=2r;r:非負(fù)整數(shù)）

算法之一：

由：C11=A11B11+A12B21;C12=A11B12+A12B22;C21=A21B11+A22B21;C22=A21B12+A22B22

遞推關(guān)系式：T(n)=8T(n/2)+an2(n>2)b(n2)T(n)=O(n3)矩陣乘法算法分析沒(méi)有改進(jìn)

令：P=(A11+A22)(B11+B22);Q=(A21+A22)B11;R=A11(B12-B22);S=A22(B21-B11);T=(A11+A12)B22;U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)

有：C11=P+S-T+V;C12=R+T;C21=Q+S;C22=P+R-Q+U

時(shí)間復(fù)雜度遞推式：T(n)=7T(n/2)+an2(n>2)b(n2)T(n)O(n2.81)算法之二(Strassen算法）：為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。對(duì)矩陣乘法的算法思考目前最好的計(jì)算時(shí)間上界是O(n2.376)可否得到更優(yōu)的算法？是否能找到O(n2)的算法？2.6棋盤覆蓋問(wèn)題描述：在一個(gè)2k×2k

個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。棋盤覆蓋

特殊棋盤、特殊方格L型骨牌

問(wèn)題：用4種不同形狀的L型骨牌如何覆蓋一個(gè)特殊棋盤？分治策略：分治策略將棋盤分割為4個(gè)2k-1×2k-1的子棋盤

對(duì)無(wú)特殊方格的3個(gè)子棋盤，在靠近中心的位置上各添一個(gè)特殊方格，轉(zhuǎn)化為特殊棋盤對(duì)四個(gè)已成特殊子棋盤的棋盤進(jìn)行同樣處理覆蓋特殊棋盤的復(fù)雜性設(shè)覆蓋規(guī)模為n=2k的棋盤需要時(shí)間T(n)將棋盤分割為4個(gè)2k-1×2k-1的子棋盤：在實(shí)現(xiàn)過(guò)程中不體現(xiàn)對(duì)無(wú)特殊方格的3個(gè)子棋盤，在靠近中心的位置上各添一個(gè)特殊方格，轉(zhuǎn)化為特殊棋盤：每個(gè)復(fù)雜性為常數(shù)C，3個(gè)子棋盤總的需3C對(duì)四個(gè)已成特殊子棋盤的棋盤進(jìn)行同樣處理：需要時(shí)間4*T(n/2)覆蓋特殊棋盤的復(fù)雜性

時(shí)間復(fù)雜度遞推式：4T(n/2)+O(1)(n>1)O(1)(n=1)T(n)=

解上述遞推式，得：T(n)=n2+kn=O(n2)復(fù)雜度分析:變形求得：T(n)=O(4k)=O(n2)，漸進(jìn)意義下的最優(yōu)算法程序?qū)崿F(xiàn){if(size==1)return;intt=tile++,//L型骨牌號(hào)

s=size/2;//分割棋盤

//覆蓋左上角子棋盤

if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc,dr,dc,s);else{//此棋盤中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋右下角

board[tr+s-1][tc+s-1]=t;//覆蓋其余方格

chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆蓋右上角子棋盤

if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr,tc+s,dr,dc,s);else{//此棋盤中無(wú)特殊方格

//用t號(hào)L型骨牌覆蓋左下角

board[tr+s-1][tc+s]=t;//覆蓋其余方格

chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤

if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc,dr,dc,s);else{//用t號(hào)L型骨牌覆蓋右上角

board[tr+s][tc+s-1]=t;//覆蓋其余方格

chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤

if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中

chessBoard(tr+s,tc+s,dr,dc,s);else{//用t號(hào)L型骨牌覆蓋左上角

board[tr+s][tc+s]=t;//覆蓋其余方格

chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidchessBoard(inttr,inttc,intdr,intdc,intsize)2.7合并排序-自學(xué)合并是將兩個(gè)或多個(gè)有序表合并成一個(gè)有序表二路歸并：對(duì)兩個(gè)已排好序的表進(jìn)行合并下圖所示的兩個(gè)有序表經(jīng)合并運(yùn)算后得到一個(gè)有序表。合并排序算法是用分治策略實(shí)現(xiàn)對(duì)n個(gè)元素進(jìn)行排序的算法。71013154819204781013151920打擂臺(tái)合并排序思想合并排序是利用多次合并進(jìn)行排序先將n個(gè)數(shù)據(jù)看成n個(gè)長(zhǎng)度為1的表，將相鄰的表成對(duì)合并，得到長(zhǎng)度為2的n/2個(gè)有序表；再將相鄰表成對(duì)合并，得到長(zhǎng)度為4的n/4個(gè)有序表；……如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個(gè)長(zhǎng)度為n的有序表為止，即完成排序。合并排序圖示Lhm分別排序！二路合并兩個(gè)有序表合并排序算法實(shí)現(xiàn)-遞歸形式template<classType>voidMergeSort(Typea[],intleft,intright){if(left<right){//至少有

2個(gè)元素

inti=(left+right)/2;//取中點(diǎn)

MergeSort(a,left,i);MergeSort(a,i+1,right);Merge(a,b,left,i,righ);//合并到數(shù)組

bCopy(a,b,left,right);//復(fù)制回?cái)?shù)組

a}}分治方法合并排序復(fù)雜性

時(shí)間復(fù)雜度遞推式2T(n/2)+O(n)(n>1)O(1)(n=1)T(n)=

解上述遞推式，得：T(n)=O(nlogn)

合并排序是漸近意義下的最優(yōu)算法二路合并所需比較left與right及取中點(diǎn)需常數(shù)時(shí)間兩組歸并算法作用：將兩組有序文件合并成一組有序文件。voidMerge(Typec[],Typed[],intl,intm,intr){/*c[l]到c[m]、c[m+1]到c[r]是兩有序文件合并到d*/inti,j,k;i=l;j=m+1;k=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j]) d[k++]=c[i++];/*從兩個(gè)有序文件中的第一個(gè)記錄中選出小的記錄*/ elsed[k++]=c[j++];}while(i<=m)d[k++]=c[i++];/*復(fù)制第一個(gè)文件的剩余記錄*/while(j<=r)d[k++]=c[j++];/*復(fù)制第二個(gè)文件的剩余記錄*/}合并排序算法實(shí)現(xiàn)-無(wú)遞歸形式無(wú)遞歸的自然合并排序舉例給定數(shù)列7151310420198[7][15][13][10][4][20][19][8]排序過(guò)程：[7][15][10][13][4][20][8][19][7][10][13][15][4][8][19][20][4][7][8][10][13][15][19][20]目的：消去遞歸過(guò)程無(wú)遞歸的合并排序算法作用：消去遞歸、歸并排序voidMergeSort(Typea[],intn){Type*b=newType[n];ints=1;while(s<n){MergePass(a,b,s,n);/*一趟歸并結(jié)果放在b中*/ s*=2; MergePass(b,a,s,n);/*一趟歸并結(jié)果放在a中*/ s+=s}}上述算法用二趟歸并MergePass是一趟歸并算法，見(jiàn)下頁(yè)一趟歸并算法MergePass作用：調(diào)用兩組歸并算法，對(duì)數(shù)組進(jìn)行一趟歸并，將長(zhǎng)為n的有序文件歸并成長(zhǎng)為2n的有序數(shù)組。/*對(duì)x做一趟歸并，結(jié)果放在y中*/voidMergePass(Typex[],Typey[],ints,intn){ inti=0,j;/*n為本趟歸并的有序子數(shù)組的長(zhǎng)度*/while(i+2*s-1<n){Merge(x,y,i,i+s-1,i+2*s-1);/*歸并長(zhǎng)度為s的兩子數(shù)組*/ i=i+2*s;}if(i+s<n)/*剩下兩個(gè)子數(shù)組，其中一個(gè)長(zhǎng)度小于s*/Merge(x,y,i,i+s-1,n-1);else for(j=i;j<n;j++)/*將最后一個(gè)子數(shù)組復(fù)制到數(shù)組y中*/ y[j]=x[j];}合并排序最好、最壞復(fù)雜性最好情況：長(zhǎng)為n/2的兩已排序的段，左邊段元素總小于右邊段元素12…2s-1-12s-12s-1+12s+1+22s+2+3…2sT(n)=2T(n/2)+n/2T(1)=0，T(2)=1,T(4)=4最壞情況：長(zhǎng)為n/2的兩已排序的段，左邊段元素與右邊段元素需比較n-1次：T(n)=2T(n/2)+n-1,T(1)=0,T(2)=1,T(4)=5合并排序小結(jié)最壞時(shí)間復(fù)雜度：O(nlogn)最好時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)2.8快速排序-自學(xué)

快速排序是對(duì)起泡排序的改進(jìn)，由C.A.RHoar提出基本思想∶在待排序的n個(gè)元素中任取一個(gè)元素(如取第一個(gè)元素)，把所有小于該元素的元素移到其左邊，把所有大于該元素的元素移到其右邊，所選元素正好處在其應(yīng)在的位置，且把原有序列劃分成兩個(gè)子序列。然后，對(duì)兩個(gè)子序列分別重復(fù)上述過(guò)程，直到所有元素都排好序?？焖倥判蚍ㄅ判蚺e例初始序列為3,9,1,6,5,4,8,2,10,7

一次分區(qū)：設(shè)2個(gè)指針i，j，以第1個(gè)元素為基準(zhǔn)39165482107↑i↑j29165483107↑i↑j23165489107↑i↑j23165489107↑i↑j21365489107i↑j各趟排序之后的狀態(tài)假設(shè)每次分區(qū)后，都先對(duì)前一區(qū)的記錄進(jìn)行快速排序,如65489107↑i↑j65489107↑i↑j45689107↑i↑j45689107i↑j算法實(shí)現(xiàn)與復(fù)雜性（1）算法實(shí)現(xiàn)復(fù)雜性分析：對(duì)于輸入序列a[p：r]，Partition的計(jì)算時(shí)間顯然為O(r-p-1)最壞情況：嚴(yán)重不對(duì)稱時(shí)，2段分別包含n-1個(gè)元素和1個(gè)元素,T(1)=0,T(2)=1

，則T(n-1)+O(n)(n>1)O(1)(n=1)T(n)=求得T(n)=n(n-1)/2=O(n2)算法實(shí)現(xiàn)與復(fù)雜性（2）最好情況：完全對(duì)稱，2段分別包含n/2個(gè)元素2T(n/2)+O(n)(n>1)O(1)(n=1)T(n)=求得T(n)=O(nlogn)T(2)=1平均情況：設(shè)分劃的數(shù)x=a[p]在最后排序的第k位，第1輪比較n-1次，前有k-1個(gè)元素，后有n-k個(gè)元素。元素<x的段x元素>x的段k-1個(gè)n-k個(gè)平均情況復(fù)雜性T(n)==得:(n+1)T(n+1)=(n+2)T(n)+2n求得：T(n)=(2n+2)logn+Θ(1)=Θ(nlogn)(n+1)T(n+1)=(n+2)T(n)+2n

即：T(n)=T(n-1)+n+11n12(n-1)n(n+1)(1)

令：Q(n)=T(n),有：Q(n-1)=T(n-1)n+11n1求解細(xì)節(jié)（可略過(guò)）

代入(1)式：Q(n)=Q(n-1)+n(n+1)2(n-1)Q(n-1)=Q(n-2)+(n-1)n2(n-2)Q(n-2)=Q(n-3)+(n-2)(n-1)2(n-3)………Q(2)=Q(1)+2?12?3+)Q(n)-Q(1)=nk=2k(k+1)2(k-1)k=2n=k+14-k2=n+14-1+2k=3nk1遞推：

因?yàn)椋簁=3nk13n1xdx=lnn-ln3

由：Q(n)=T(n),及：T(1)=b,知：Q(1)=1/2bn+11T(n)=(n+1)Q(n)

2(n+1)lnn+(b/2-1-2ln3)(n+1)+4=O(nlnn)快速排序小結(jié)最壞時(shí)間復(fù)雜度：O(n2)最好時(shí)間復(fù)雜度：O(nlogn)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)一個(gè)可以采納的算法：隨機(jī)選擇策略快速排序算法的性能取決于劃分的對(duì)稱性。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，可使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。Lmhmax1max2max1?分別找出最大元的位置確定最大元的最后位置max2?練習(xí)：在無(wú)序數(shù)組中找最大元intmax(L,h){if(L==h)returnL;else{m=(L+h)/2;max1=max(L,m);max2=max(m+1,h);intmax0=max1;if(a[max2]>a[max1])max0=max2;returnmax0;}}找最大元算法設(shè)計(jì)T(n/2)+T(n/2)+1(n>1)0(n=1)T(n)=

解之，得：T(n)=n-1找最大元算法復(fù)雜性2.9線性時(shí)間選擇問(wèn)題：給定線性序集中n個(gè)元素和一個(gè)整數(shù)k，1<=k<=n，要求找出這n個(gè)元素中第k小的元素。即從a[1]~a[n]找出第k小元素。特殊情況：1、當(dāng)k=1時(shí)，找最小元素；2、當(dāng)k=n時(shí)，找最大元素；3、當(dāng)k=（n＋1）/2時(shí)，找中位數(shù)。結(jié)論：一般的選擇問(wèn)題可以在O(n)時(shí)間內(nèi)得到解決一個(gè)初步思路隨機(jī)選一個(gè)元素x，按x大小將數(shù)組分為左、右三部分xj個(gè)<x>x如k<=j，第k小元素在左邊部分；如k>j，第k小元素在右邊部分；復(fù)雜性是O(n2)的求第k小元素的隨機(jī)化算法求第k小的隨機(jī)化算法#include"stdafx.h"#include<iostream.h>template<classType>TypeRandomizedSelect(Typea[],intL,intR,intk){//隨機(jī)選擇，并分劃

if(L==R)returna[p]; inti=RandomizedPartition(a,L,R); intj=i-L+1; if(k<=j)returnRandomizedSelect(a,L,i,k); else returnRandomizedSelect(a,i+1,R,k-j);}template<classType>TypeRandomizedPartition(Typea[],intL,intR){…//如先分劃，返回分解點(diǎn);}voidmain(){ intnum,i,k;inta[20]; cout<<"請(qǐng)輸入元素的個(gè)數(shù)："<<endl; cin>>num; cout<<"請(qǐng)依次輸入元素："<<endl; for(i=0;i<num;i++) cin>>a[i]; cout<<"要查找第k小個(gè)元素，請(qǐng)輸和k值:"<<endl;cin>>k;intn=RandomizedSelect(a,0,num-1,k); cout<<n<<endl;}隨機(jī)化算法的復(fù)雜性一般，對(duì)輸入數(shù)組的劃分可隨機(jī)產(chǎn)生，在最壞情況下分成1個(gè)和n-1個(gè)。故仿照快速排序，推得復(fù)雜性為O(n2)

一、算法思想：模仿快速排序算法，找到劃分基準(zhǔn)，對(duì)輸入數(shù)組進(jìn)行遞歸劃分，使劃分出的2個(gè)子數(shù)組長(zhǎng)度都至少為原數(shù)組長(zhǎng)度比較?。ㄈ绫?0<ε<1)）。

遞歸，找中間元素m

！按m對(duì)a劃分！M:a:a:S1S2S3一般選擇問(wèn)題的分治算法分相同長(zhǎng)度的組找每組中間元素，構(gòu)成MintSelect(k,a,n){if(n<=r)//對(duì)某“足夠”小正整數(shù)r,例如：r=5。

{對(duì)a排序，并返回a[k];}else{(1)把a(bǔ)劃分為n/r個(gè)、長(zhǎng)度為r的“子數(shù)組”，并對(duì)各“子數(shù)組”分別排序；（最多多4個(gè)元素，不用排）(2)用上述排序后的各“子數(shù)組”的“中間”元素，構(gòu)造數(shù)組M；(4)再以m為“基準(zhǔn)”，把a(bǔ)數(shù)組劃分為小于、等于、大于m的三個(gè)“子數(shù)組”(假設(shè)它們記為S1,S2,S3);

算法描述(3)遞歸求出數(shù)組M的“中間”值元素m,即：m(Select(

n/r/2,M,n/r);(5)if(k<=S1){returnSelect(k,S1,S1)；}elseif(k<=S1+S2)returnm;elsereturn(Select(k-S1-S2,S3,S3));}}

M:小大大小T(n)T(n)+T(n)+cn(n>>n0)5143cn(n5)(設(shè)：r=5)復(fù)雜性分析注意：兩個(gè)子數(shù)組S1、S2分別至多有3n/4個(gè)元素n0可以調(diào)整對(duì)各“子表”分別排序構(gòu)造“中間”元素表M求M表的“中間”值元素m<m>m令：a=1/5,b=3/4有：T(n)T(an)+T(bn)+cn

[T(a2n)+T(abn)+can]+[T(abn)+T(b2n)+cbn]+cn

T(a2n)+2T(abn)+T(b2n)+(a+b)cn+cn

T(a3n)+3T(a2bn)+3T(ab2n)+T(b3n)+(a+b)2cn+(a+b)cn+cn……T(amn)+()T(am-1bn)+()T(am-2b2n)+()T(am-kbkn)+…+T(bmn)+(a+b)m-1cn+(a+b)m-2cn+…+(a+b)cn+cnm1m2mk求解過(guò)程：

因?yàn)椋?<a<b<1,am<am-1b<…<am-kbk<…<bm

對(duì)于T(bmn),當(dāng)mlog25|log2b|log2blog2n+時(shí)，bmn5成立T(bmn)bmcnT(n)(a+b)mcn+(a+b)m-1cn+…+(a+b)cn+cn(a+b)kcnk=0m1-(a+b)m+11-(a+b)cncn1-(a+b)120cn(續(xù))結(jié)論：T(n)=O(n)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ì)間的距離最小。粗略計(jì)算：任取兩點(diǎn)求距離復(fù)雜性：O(C)=O(n2),效率太低2n精確計(jì)算：?jiǎn)栴}的計(jì)算時(shí)間下界為(nlogn)計(jì)算時(shí)間下界為(nlogn)思想方法：將所給的平面上

n個(gè)點(diǎn)的集合

S分成兩個(gè)子集

S1和

S2，每個(gè)子集中約有

n/2個(gè)點(diǎn)在每個(gè)子集中遞歸地求其最接近的點(diǎn)對(duì)求整體集合S的最接近的點(diǎn)對(duì)從一維的情形開(kāi)始

S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù)x1，x2，…，xn將x1，x2

，…，xn排序，需O(nlogn)

一維點(diǎn)集S={x1，x2

，…，xn}

求相差最小的兩個(gè)實(shí)數(shù)

分治法：S劃分為兩個(gè)集合S1和S2，S1={xS：x<=m}，S2={xS：x>m}

再分別對(duì)S1、S2作分治處理如何選擇m？此方法無(wú)法推廣到二維情形m的選擇m=(max(S)+min(S))/2---取最大最小的平均最壞情況：子集S1和S2不平衡，其中一個(gè)有n-1個(gè)元素T(n)=T(n-1)+O(n)=>T(n)=O(n2)2T(n/2)+O(n)(n>4)O(1)(n=4)T(n)=求得T(n)=O(nlogn)

取中位數(shù)，兩組元素個(gè)數(shù)大致相同一維情形取中位數(shù)可行！二維點(diǎn)集S={p1，p2

，…，pn}作一條垂直線l:x=m將平面分為兩部分S劃分為兩個(gè)集合S1和S2，|S1|和|S2|大致相同

S1={pS：x<=m}S2={pS：x>m}

記Sx={xR:有(x,y)S}，

m為Sx的中位數(shù)，S1S2d1d2l:x=m求各部分最小距離

d1=min_distance(S1)d2=min_distance(S2)d=min(d1,d2)S1S2P1P2ddd1d2設(shè)(p,q)為S的最接近點(diǎn)對(duì)情況：1、p,qS12、p,qS23、pS1，qS2l:x=m容易處理，分治P1表示直線l左邊寬d的長(zhǎng)條pS1，qS2的情形候選點(diǎn)對(duì)數(shù)最壞時(shí)：

n2/4---二次函數(shù)極值S1S2P1P2ddd1d2pq但P1、P2有稀疏性質(zhì)：

對(duì)P1中任意一點(diǎn)p，在P2中最多只有6個(gè)S中的點(diǎn)使與p的距離不超過(guò)d

S2P1P2ddpq目前候選的點(diǎn)對(duì)數(shù)最多為

6×n/2=3n為什么？？

抽屜原理3n個(gè)點(diǎn)的考察方法將P1和P2中所有S中點(diǎn)按y坐標(biāo)排序按y序，對(duì)P1中所有點(diǎn)p作一次掃描，再按y序找出P2中所有至多6個(gè)最接近點(diǎn)對(duì)的候選者算法boolCpair2(S,d){n＝|S|；if(n＜2){d=;returnfalse;}1．m=S中各點(diǎn)x間坐標(biāo)的中位數(shù)；構(gòu)造S1和S2;2．Cpair2(S1,d1);Cpair2(S2，d2);3．dm=min(d1,d2);4．設(shè)P1是S1中距垂直分割線l距離在dm之內(nèi)的所有點(diǎn)組成的集合；P2是S中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合；P1和P2中點(diǎn)依其y坐標(biāo)值排序；(在未處理前，先對(duì)S以y值排序)

并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列；5．通過(guò)掃描X以及對(duì)于X中每個(gè)點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)（最多6個(gè)）可以完成合并；當(dāng)X中的掃描指針逐次向上移動(dòng)時(shí)，Y中的掃描指針可在寬為2dm的一個(gè)區(qū)間內(nèi)移動(dòng)；設(shè)dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離；

6．d＝min(dm,dl)；

returntrue；}Cpair2(S,d)的時(shí)間復(fù)雜性第1步和第5步用O(n)時(shí)間第3步和第6步用常數(shù)時(shí)間第2步用2T(n/2)時(shí)間使用分治法之前，先將S中n個(gè)點(diǎn)依y坐標(biāo)值排好序，需O(nlogn)。設(shè)排好序的點(diǎn)列為P*第4步只作一次線性掃描，抽取所需的排好序的點(diǎn)列X和Y;在第5步中再對(duì)X作一次線性掃描，求得dl。第4步和第5步的兩遍掃描合在一起只要用O(n)時(shí)間最接近點(diǎn)對(duì)問(wèn)題時(shí)間復(fù)雜性程序：略2T(n/2)+O(n)(n>4)O(1)(n<=4)T(n)=求得T(n)=O(nlogn)

分治法不僅可以用來(lái)設(shè)計(jì)算法,而且在其他方面也有廣泛應(yīng)用。如可用分治思想來(lái)設(shè)計(jì)電路、構(gòu)造數(shù)學(xué)證明等。2.11循環(huán)賽日程表循環(huán)賽日程表設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽。現(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次；（2）每個(gè)選手一天只能賽一次；（3）循環(huán)賽一共進(jìn)行n-1天。循環(huán)賽日程表設(shè)計(jì)按要求可將比賽日程表設(shè)計(jì)成有n行和n-l列的一個(gè)表。在表中第i行和第j列處填入第i個(gè)選手在第j天所遇到的選手。

天人1234567123456782345678思想方法：將所有選手對(duì)分為兩組，n個(gè)選手的比賽日程表可通過(guò)為n/2個(gè)選手設(shè)計(jì)的比賽日程表來(lái)決定。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行分割，直到只剩下2個(gè)選手時(shí)，比賽日程表的制定就變得很簡(jiǎn)單。這時(shí)只要讓這2個(gè)選手進(jìn)行比賽即可。分治策略

圖所列出的正方形表是4個(gè)選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手2和選手3至選手4第1天的比賽日程。據(jù)此，將左上角小塊中的所有數(shù)字按其相對(duì)位置抄到右下角，將左下角小塊中的所有數(shù)字按其相對(duì)位置抄到右上角，就分別安排好了選手1至選手2和選手3至選手4在后2天的比賽日程。這種安排是符合要求的。4個(gè)選手的比賽日程表12342143341243218個(gè)選手的比賽日程表

天人12345671234567821436587341278564321876556781234658721437856341287654321第四版教材課后作業(yè)習(xí)題：分