第2章-遞歸與分治策略

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

理解遞歸的概念，掌握遞歸程序編寫方法。根據(jù)一些問題，求解較簡單的遞推方程。掌握分治算法的分析方法，能確定常見問題的復雜性的階通過典型范例，學習分治策略設計技巧。2.1遞歸的概念遞歸算法：一個直接或間接地調用自身的算法遞歸函數(shù)：使用函數(shù)自身給出定義的函數(shù)遞歸方程：對于遞歸算法，一般可把時間代價表示為一個遞歸方程解遞歸方程最常用的方法是進行遞歸擴展遞歸函數(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ù)的二個要素遞歸函數(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ù)：一個函數(shù)及它的一個變量由函數(shù)自身定義A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)Fm(n)

遞歸函數(shù)舉例(3)Ackerman函數(shù)的性狀m=0時，A(n,0)=n+2,n>=2；A(1,0)=2m=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ù)。遞歸函數(shù)舉例(3)單變量的Ackerman函數(shù)A(n)定義為

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

α(n)=min{k｜A(k)≥n}。α(n)：隨n的增長非常慢Ackerman函數(shù)的作用遞歸函數(shù)舉例(4)排列問題設R={r1，r2，…，rn}是要進行排列的n個元素，Ri=R－{ri}。集合X中元素的全排列記為Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一個排列前加上前綴ri得到的排列。R的全排列可歸納定義如下：當n＝l時，Perm(R)=（r），其中r是集合R中唯一的元素；當n>l時，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),…,(rn)Perm(Rn)構成。產生置換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]有多于一個置換，遞歸產生

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

n＝

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

n2…nk

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

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

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

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

一、分治法概述

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

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

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

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

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

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

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

2.二分搜索方法基本思想：將n個元素分成個數(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。

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

算法分析的一般方法2、算法工作量的度量方法用執(zhí)行時間來作為算法工作量的度量用算法程序中所執(zhí)行的指令條數(shù)或語句條數(shù)來度量從運算的執(zhí)行次數(shù)來度量（受問題性質、大小、輸入情況的影響），一般指計算所需的一些基本運算的次數(shù)。如比較次數(shù)，加法和乘法次數(shù)，待排序元素的“移動”次數(shù)。第①條因計算機而異，很難確定第②條與與所用的程序語言和程序員的習慣有關。第③條容易刻畫。需明確被分析算法的“關鍵操作”是什么nnlogn2nn512345543210nf(n)3.考察算法的“關鍵操作”數(shù)，隨“問題規(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通項表示

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

因為x1

x2

所以F(n)=c1x1n+c2x2n

由F(0)=1和F(1)=1知：“Hanoi塔”問題算法復雜性算法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

因為(R’)中，f(n)=k

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

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

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

方案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

遞推關系式：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)=

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

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

Cnn=Ann

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

算法之一：

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

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

令：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

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

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

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

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

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

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

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

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

//覆蓋左上角子棋盤

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

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

//用t號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{//此棋盤中無特殊方格

//用t號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號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號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合并排序-自學合并是將兩個或多個有序表合并成一個有序表二路歸并：對兩個已排好序的表進行合并下圖所示的兩個有序表經(jīng)合并運算后得到一個有序表。合并排序算法是用分治策略實現(xiàn)對n個元素進行排序的算法。71013154819204781013151920打擂臺合并排序思想合并排序是利用多次合并進行排序先將n個數(shù)據(jù)看成n個長度為1的表，將相鄰的表成對合并，得到長度為2的n/2個有序表；再將相鄰表成對合并，得到長度為4的n/4個有序表；……如此重復做下去，直至所有數(shù)據(jù)均合并到一個長度為n的有序表為止，即完成排序。合并排序圖示Lhm分別排序！二路合并兩個有序表合并排序算法實現(xiàn)-遞歸形式template<classType>voidMergeSort(Typea[],intleft,intright){if(left<right){//至少有

2個元素

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

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

bCopy(a,b,left,right);//復制回數(shù)組

a}}分治方法合并排序復雜性

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

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

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

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

一次分區(qū)：設2個指針i，j，以第1個元素為基準39165482107↑i↑j29165483107↑i↑j23165489107↑i↑j23165489107↑i↑j21365489107i↑j各趟排序之后的狀態(tài)假設每次分區(qū)后，都先對前一區(qū)的記錄進行快速排序,如65489107↑i↑j65489107↑i↑j45689107↑i↑j45689107i↑j算法實現(xiàn)與復雜性（1）算法實現(xiàn)復雜性分析：對于輸入序列a[p：r]，Partition的計算時間顯然為O(r-p-1)最壞情況：嚴重不對稱時，2段分別包含n-1個元素和1個元素,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)算法實現(xiàn)與復雜性（2）最好情況：完全對稱，2段分別包含n/2個元素2T(n/2)+O(n)(n>1)O(1)(n=1)T(n)=求得T(n)=O(nlogn)T(2)=1平均情況：設分劃的數(shù)x=a[p]在最后排序的第k位，第1輪比較n-1次，前有k-1個元素，后有n-k個元素。元素<x的段x元素>x的段k-1個n-k個平均情況復雜性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求解細節(jié)（可略過）

代入(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遞推：

因為：k=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)快速排序小結最壞時間復雜度：O(n2)最好時間復雜度：O(nlogn)平均時間復雜度：O(nlogn)輔助空間：O(n)或O(logn)一個可以采納的算法：隨機選擇策略快速排序算法的性能取決于劃分的對稱性。在快速排序算法的每一步中，當數(shù)組還沒有被劃分時，可以在a[p:r]中隨機選出一個元素作為劃分基準，可使劃分基準的選擇是隨機的，從而可以期望劃分是較對稱的。Lmhmax1max2max1?分別找出最大元的位置確定最大元的最后位置max2?練習：在無序數(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;}}找最大元算法設計T(n/2)+T(n/2)+1(n>1)0(n=1)T(n)=

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

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){…//如先分劃，返回分解點;}voidmain(){ intnum,i,k;inta[20]; cout<<"請輸入元素的個數(shù)："<<endl; cin>>num; cout<<"請依次輸入元素："<<endl; for(i=0;i<num;i++) cin>>a[i]; cout<<"要查找第k小個元素，請輸和k值:"<<endl;cin>>k;intn=RandomizedSelect(a,0,num-1,k); cout<<n<<endl;}隨機化算法的復雜性一般，對輸入數(shù)組的劃分可隨機產生，在最壞情況下分成1個和n-1個。故仿照快速排序，推得復雜性為O(n2)

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

遞歸，找中間元素m

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

{對a排序，并返回a[k];}else{(1)把a劃分為n/r個、長度為r的“子數(shù)組”，并對各“子數(shù)組”分別排序；（最多多4個元素，不用排）(2)用上述排序后的各“子數(shù)組”的“中間”元素，構造數(shù)組M；(4)再以m為“基準”，把a數(shù)組劃分為小于、等于、大于m的三個“子數(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)(設：r=5)復雜性分析注意：兩個子數(shù)組S1、S2分別至多有3n/4個元素n0可以調整對各“子表”分別排序構造“中間”元素表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求解過程：

因為：0<a<b<1,am<am-1b<…<am-kbk<…<bm

對于T(bmn),當mlog25|log2b|log2blog2n+時，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ù))結論：T(n)=O(n)2.10最接近點對問題問題：給定平面上n個點，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。粗略計算：任取兩點求距離復雜性：O(C)=O(n2),效率太低2n精確計算：問題的計算時間下界為(nlogn)計算時間下界為(nlogn)思想方法：將所給的平面上

n個點的集合

S分成兩個子集

S1和

S2，每個子集中約有

n/2個點在每個子集中遞歸地求其最接近的點對求整體集合S的最接近的點對從一維的情形開始

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

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

一維點集S={x1，x2

，…，xn}

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

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

再分別對S1、S2作分治處理如何選擇m？此方法無法推廣到二維情形m的選擇m=(max(S)+min(S))/2---取最大最小的平均最壞情況：子集S1和S2不平衡，其中一個有n-1個元素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ù)，兩組元素個數(shù)大致相同一維情形取中位數(shù)可行！二維點集S={p1，p2

，…，pn}作一條垂直線l:x=m將平面分為兩部分S劃分為兩個集合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設(p,q)為S的最接近點對情況：1、p,qS12、p,qS23、pS1，qS2l:x=m容易處理，分治P1表示直線l左邊寬d的長條pS1，qS2的情形候選點對數(shù)最壞時：

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

對P1中任意一點p，在P2中最多只有6個S中的點使與p的距離不超過d

S2P1P2ddpq目前候選的點對數(shù)最多為

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

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

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

6．d＝min(dm,dl)；

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

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

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

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

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