分治與遞歸策略課件

1第2講分治與遞歸策略2.1分治算法的基本思想2.2遞歸概念2.3典型分治算法舉例第一頁，共八十四頁。2算法總體思想

將一個難以直接解決的規(guī)模較大的問題分解為若干個規(guī)模較小的子問題，并各個擊破，分而治之。n/16nn/4n/4n/4n/4n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16n/16第二頁，共八十四頁。3將求出的較小規(guī)模的問題解合并成一個較大規(guī)模的問題解，并自底向上地求出原問題的解。最頂層問題a為分解的子問題數(shù)量；n/b為每個子問題的數(shù)據(jù)規(guī)模；f(n)為合并子問題解所消耗的時間。第三頁，共八十四頁。42.1分治算法的基本思想

分治算法的基本思想是將一個規(guī)模為n的問題分解為a個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。第四頁，共八十四頁。5分治算法所能解決問題一般具有以下幾個特征：縮小問題規(guī)?？梢越档徒鉀Q問題的難度；可以將子問題的解合并為原問題解；問題分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。第五頁，共八十四頁。6分治算法的算法框架divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決規(guī)模小的問題//將問題P分解為子問題P1,P2,...,Pa；for(i=1,i<=a,i++)yi=divide-and-conquer(Pi);//遞歸的求解各子問題returnmerge(y1,...,ya);//合并為原問題的解}第六頁，共八十四頁。7

一個分治算法將規(guī)模為n的問題分成a個規(guī)模為n／b的子問題。設分解閾值n0=1，且adhoc解規(guī)模為1的問題耗費1個單位時間。再設將原問題分解為a個子問題以及用merge將a個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治算法解規(guī)模為|P|=n的問題所需的計算時間，則有下列遞歸方程：通過求解遞歸方程得到遞歸算法的時間復雜性。分治算法的復雜性分析第七頁，共八十四頁。8替換方法遞歸樹方法公式法求解遞歸方程的三種方法：第八頁，共八十四頁。9替換方法替換方法的主要思想是首先推測出遞歸方程的解，然后代入遞歸方程，查看是否滿足條件。適用比較容易猜出遞歸解的情形。①猜測出遞歸解的形式②用數(shù)學歸納法找出使解真正有效的常數(shù)替換方法解遞歸方程的基本步驟：第九頁，共八十四頁。10例：T(n)=2T(n/2)+n（2路歸并)假設解對n/2成立，即T(n/2)≤c(n/2)lg(n/2)將其對遞歸方程進行替換，得：T(n)=2T(n/2)+n≤2(c(n/2)lg(n/2))+n≤cnlg(n/2)+n≤cnlgn-cnlg2+n=cnlgn-cn+n當c≥1時，顯然cnlgn-cn+n≤cnlgn根據(jù)O符號定義，證明猜測正確。數(shù)學歸納法：猜測出解為T(n)=O(nlgn)證明存在某個常數(shù)c，使得T(n)≤cnlgn第十頁，共八十四頁。11遞歸樹方法構(gòu)造遞歸樹的方法就是展開遞歸方程，然后將樹中每層的時間求和，最終獲得算法的時間復雜性。用遞歸樹方法求解遞歸方程的基本步驟:遞歸樹可以方便地推測遞歸方程的解，是描述分治算法的運行時間復雜性的有效手段。①利用遞歸樹推測出一個解②利用替換方法進行證明第十一頁，共八十四頁。12例：T(n)=3T(n/4)+cn2

T(n)→第十二頁，共八十四頁。13log4n+1nlog43O(nlog43)第十三頁，共八十四頁?，F(xiàn)在，我們來計算一下，有多少個葉節(jié)點。第1層有3個節(jié)點，第2層有32個節(jié)點，依次類推，第k層有3k個節(jié)點，當k=log4n，即為葉節(jié)點，因此，葉節(jié)點的個數(shù)為，而每個葉節(jié)點需要的時間為T(1),因此，整個葉節(jié)點的時間為。14遞歸樹總共有多少層？當遞歸樹展開一層，其規(guī)模為n/4，當遞歸樹展開到第2層時，其規(guī)模為n/16=n/42，依次類推，當展開到第k層時，其規(guī)模為n/4k=1時，不再展開，由此可以求得遞歸樹的層數(shù)為k=log4n。第十四頁，共八十四頁。15將遞歸樹每一層的時間累加，可得：

i=0所以，由遞歸樹猜測T(n)=O(n2)隨后，再利用數(shù)學歸納法證明。第十五頁，共八十四頁。16其中，a≥1，b>1是常數(shù)，f(n)是一個漸進函數(shù)，描述劃分問題與合并解的時間復雜性。n/b可以是，也可以是

公式法上述方程描述了如下算法的運行時間：將一個規(guī)模為n的問題劃分為a個規(guī)模為n/b的子問題，其中a和b為正常數(shù)。分別遞歸地解決a個子問題，解每個子問題所需時間為T(n/b)。劃分原問題和合并子問題的解所需要的時間由f(n)決定第十六頁，共八十四頁。17定理：上述遞歸方程含有三種情形的漸進界：（1）對于某個常數(shù)如果則（2）如果則（3）對某個常數(shù)如果且對某個常數(shù)c<1以及任意足夠大的n,有af(n/b)≤cf(n),則

第十七頁，共八十四頁。18定理含義將f(n)與進行比較，當較大時，相等時當較小時，

結(jié)論：可以通過盡量減少子問題的個數(shù)或者減少f(n)的數(shù)量級來增強分治算法的有效性。從定理中可以看出，公式法只要記住三種情形，就可以很容易地確定許多遞歸方程的解。第十八頁，共八十四頁。19例1：T(n)=9T(n/3)+n由上式可知，a=9，b=3，f(n)=n,且又因為對于有滿足定理（1），因此，第十九頁，共八十四頁。20例2：T(n)=T(2n/3)+1由上式可知a=1,b=3/2,f(n)=1，且又因為滿足定理（2），因此第二十頁，共八十四頁。212.2遞歸概念

分治算法遞歸技術(shù)直接或間接地調(diào)用自身的算法稱為遞歸算法。在定義函數(shù)時調(diào)用到函數(shù)自身稱為遞歸函數(shù)。分治算法遞歸技術(shù)

分治與遞歸像一對孿生兄弟分治算法的特征：將較大規(guī)模的問題分解為若干個較小規(guī)模的子問題，每個子問題的求解過程與原問題一樣，并利用自底向上的求解策略得到最終的解。第二十一頁，共八十四頁。22遞歸應用舉例1:Fibonacci數(shù)列邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二要素。無窮2階數(shù)列1，1，2，3，5，8，13，21，34，55，…，被稱為Fibonacci數(shù)列。遞歸定義為：第二十二頁，共八十四頁。23A(1,0)=2A(0,m)=1m≥0A(n,0)=n+2n≥2A(n,m)=A(A(n-1,m),m-1)n,m≥1遞歸應用舉例2:Ackerman函數(shù)第二十三頁，共八十四頁。24m=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)=2n。m=3時，類似的可以推出A(1,0)=2A(0,m)=1m≥0A(n,0)=n+2n≥2A(n,m)=A(A(n-1,m),m-1)n,m≥1Ackerman函數(shù)的特征：A(n，m)的自變量m的每一個值都定義了一個單變量函數(shù)。m=0時，A(n,0)=n+2m=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2可以得出A(n,1)=2*n第二十四頁，共八十四頁。25遞歸應用舉例3:排列問題求解n個元素{r1,r2,…,rn}的全排列。n個元素的全排列有n!種可能。解題基本方法：（1）固定位置放元素（2）固定元素找位置第二十五頁，共八十四頁。26假設R={r1,r2,…,rn}是待排列的n個元素，Ri=R-{ri}。假設集合Ri中元素的全排列記為perm(Ri)。(ri)perm(Ri)表示在全排列perm(Ri)的每一個排列的第一個位置加前綴ri得到的排列。當n=1時，perm(R)=(r)其中r是集合R中唯一的元素；當n>1時，perm(R)的全排列為：(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)方法1：固定位置找元素第二十六頁，共八十四頁。27遞歸公式第二十七頁，共八十四頁。28第二十八頁，共八十四頁。29將每個元素交換到固定位置上，并求解其余位置元素的全排列。舉例，0~3共4個數(shù)值的全排列思路？第二十九頁，共八十四頁。30假設:要求P[m]、P[m+1]、…P[n]的全排列:值得注意的是，將P[m]和某個P[k]交換，求出剩余元素的所有排列后，為了避免重復，發(fā)生混亂，必須將P[m]和P[k]交換回去，然后才能繼續(xù)P[m]和P[K+1]的交換。當問題規(guī)模降為求一個元素P[m]的全排列時，問題就極為簡單，可作為遞歸出口。3.然后依次考慮P[m+3]，…,P[n]。2.然后考慮P[m+1]，通過交換P[m]和P[m+1]，這樣我們?nèi)匀恢灰紤]求剩余元素P[m+1]、P[m+2],…P[n]的所有排列即可。1.需要先考慮P[m]，如果能夠求出剩余元P[m+1]、P[m+2]、…，P[n]的所有排列，我們只需將P[m]放到每個排列的開頭。第三十頁，共八十四頁。31第三十一頁，共八十四頁。32voidperm(int[]r,inti,intn){//r存放R集合元素，r[0]~r[n]//i,n表示目前求解的全排列起始與終止位置if（只有一個元素）{//遞歸邊界條件顯示當前排列；}else{依次將i~n之間的每個元素交換

//遞歸到第i個位置，并用同樣的方法（遞歸）求解i+1~n之間的全排列}}第三十二頁，共八十四頁。33voidperm(intr[],inti,intn){if(i==n){//只有一個數(shù)值for(intj=0;j<=n;j++){

//輸出結(jié)果cout<<r[j];}cout<<endl;}else{for(intj=i;j<=n;j++){

swap(r,i,j);//交換r[i]與r[j]

perm(r,i+1,n);//計算i+1~n全排列

swap(r,i,j);

//交換r[i]與r[j]}}}第三十三頁，共八十四頁。34③將n放在p[3]位置上，并用p[1..2]和p[4..n]產(chǎn)生n-1個元素的全排列；方法2：固定元素找位置

元素放置位置：p[1]~p[n]直到將n放在p[n]位置上，并用p[1..n-1]產(chǎn)生n-1個元素的全排列。...........①將n放在p[1]位置上，并用p[2..n]產(chǎn)生n-1個元素的全排列；

基本過程：在n-1個元素的全排列基礎上，將某個元素插入到每個位置上，進而得出n個元素的全排列。②將n放在p[2]位置上，并用p[1]和p[3..n]產(chǎn)生n-1個元素的全排列；第三十四頁，共八十四頁。35321,312,231,132,213,123第三十五頁，共八十四頁。36voidperm2(intp[],intn){

//n=NUM-1//p[1]~p[n]放置元素，初始為0，//n為當前參與排列的元素數(shù)量,1,2,3,……,nif(參與排列的數(shù)據(jù)數(shù)量為0){輸出結(jié)果}else{依次將n放在每個位置，并采用同樣的方法求解另外n-1元素的全排列；}}第三十六頁，共八十四頁。37voidperm2(intp[],intn){if(n==0){//元素集合為空for(inti=1;i<=NUM;i++){

//輸出結(jié)果cout<<p[i];}cout<<endl;}else{for(inti=1;i<=NUM;i++){if(p[i]==0){p[i]=n;perm2(p,n-1);p[i]=0;}}}}初始：p[1..n]=0;perm(p,n);NUM為n+1例如：n=3，NUM=4第三十七頁，共八十四頁。38實現(xiàn)過程注意：在n放定一個位置p[K]，找到剩下n-1個元素的所有排列后，在找n的下一個可放置位置時，即把n放到位置P[k+1]前，原來放n的位置p[K]一定要置0。否則，將有某些元素找不到位置。依次遞歸下去，直到數(shù)組沒有為0的元素為止。我們初始化數(shù)組p[1..n]的值為0，對于元素n，可以依次把它放到數(shù)組的p[1],p[2],….,p[n]位置，在n放定一個位置后p[K]后，剩下的n-1個元素可以放在那些值為0的數(shù)組元素p[1..k-1]和p[k+1..n]上。第三十八頁，共八十四頁。39遞歸小結(jié)遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞歸算法要多。結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學歸納法來證明算法的正確性，因此它為設計算法、調(diào)試程序帶來很大方便。優(yōu)點：缺點：第三十九頁，共八十四頁。40給定已按升序排列的n個元素a[0:n-1]，現(xiàn)要在這n個元素中找出一個特定元素x。分析：搜索范圍越小，越容易確定解；該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解就是原問題的解；分解出的各個子問題是相互獨立的。2.3節(jié)分治算法舉例1：二分搜索技術(shù)分析：

此問題分解出的子問題相互獨立，即在a[i]的前面或后面查找x是獨立的子問題，因此滿足分治算法的基本條件。第四十頁，共八十四頁。41templat<classT>intbinarySearch(Ta[],intx,intn){intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//未找到x}算法復雜性分析：每執(zhí)行一次while循環(huán)，搜索范圍縮小一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(lgn)次。循環(huán)體內(nèi)運算需要O(1)時間，因此整個算法在最壞情況下的計算時間復雜性為O(lgn)第四十一頁，共八十四頁。兩個n位二進制大整數(shù)乘法運算的基本方法:(1)小學的方法：時間復雜性

效率太低42分治算法舉例2：大整數(shù)的乘法第四十二頁，共八十四頁。43X=A2n/2+BY=C2n/2+DABCDX=Y=(2)分治算法:注意：乘以2n表示向左位移n位，這個運算耗時復雜性分析XY=(A2n/2+B)(C

2n/2+D)=AC2n+(AD+BC)2n/2+BD乘法4次，加法3次，位移2次第四十三頁，共八十四頁。44將公式：XY=AC2n+(AD+BC)2n/2+BD變換為：XY=AC2n+((A-B)(D-C)+AC+BD)2n/2+BD乘法：3次；加減法：6次；位移：2次第四十四頁，共八十四頁。45for(inti=0;i<n;i++){for(intj=0;j<n;j++){C[i][j]=0;for(intk=0;k<n;k++)C[i][j]+=A[i][k]*B[k][j];}}分治算法舉例3：Strassen矩陣乘法兩個n×n的方矩An×n,Bn×n相乘的傳統(tǒng)方法：時間復雜性：O(n3)第四十五頁，共八十四頁。46

分治算法：分別將矩陣A，B和C分解為4個大小相等的子矩陣,假設n=2r。C=AB可以寫為：可以得出：第四十六頁，共八十四頁。47降低時間復雜性的思路：減少乘法的次數(shù)。第四十七頁，共八十四頁。48Strassen矩陣乘法算法實現(xiàn)voidstrassen(inta[N][],intb[N][], intc[N][],inttopX,inttopY,intn){if(n==2){直接相乘結(jié)果存放在c中；返回；}分塊（a11,a12,a21,a22,b11,b12,b21,b22）計算m1,m2,m3,m4,m5,m6,m7；計算c11,c12,c21,c22；將結(jié)果拷貝到c中。}結(jié)論：較少乘法次數(shù)是優(yōu)化算法的重要途徑。第四十八頁，共八十四頁。49分治算法舉例4：棋盤覆蓋在一個2k×2k個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。第四十九頁，共八十四頁。50殘缺棋盤第五十頁，共八十四頁。51第五十一頁，共八十四頁。52放置一個三格板后，棋盤中間區(qū)域已經(jīng)放置好。如果把這個三格板看成三個殘缺格，原來的殘缺棋盤就可以分成4個殘缺棋盤。雖然這個三個棋盤與原來棋盤不相似，但是通過放置一個三格板，可以將原來不相似的三個棋盤構(gòu)造成殘缺棋盤，這樣這三個棋盤的放置方法可以采用類似原來殘缺棋盤的放置方法。當殘缺棋盤的規(guī)模降為2*2時，這時棋盤不再分解，遞歸終止，因為這時殘缺棋盤只要放置一個三格板就可以鋪滿。第五十二頁，共八十四頁。53當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤,即k=0,1×1。第五十三頁，共八十四頁。54棋盤覆蓋分治算法偽語言if(size==0)return;//覆蓋左上角子棋盤if(特殊方塊在左上角)

覆蓋左上角;else{在右下角放一小方塊;覆蓋左上角;}//覆蓋右上角子棋盤if(特殊方塊在右上角)覆蓋右上角;else{在左下角放一小方塊;覆蓋右上角;}//覆蓋左下角子棋盤if(特殊方塊在左下角)覆蓋左下角;else{在右上角放一小方塊;覆蓋左下角;}//覆蓋右下角子棋盤if(特殊方塊在右下角)覆蓋右下角;else{在左上角放一小方塊;覆蓋右下角;}}voidchessBoard(inttr,inttc,intdr,intdc,intsize){第五十四頁，共八十四頁。55voidchessBoard(inttr,inttc,intdr,intdc,intsize){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);}第五十五頁，共八十四頁。56第五十六頁，共八十四頁。57voidchessBoard(intboard[N][N],inttr,inttc,intdr,intdc,intsize,int&tile){if(size==1)return;ints=size/2;intt=tile++;//左上角if(dr<tr+s&&dc<tc+s)chessBoard(board,tr,tc,dr,dc,s,tile);else{board[tr+s-1][tc+s-1]=t;chessBoard(board,tr,tc,tr+s-1,tc+s-1,s,tile);}//右上角if(dr<tr+s&&dc>=tc+s)chessBoard(board,tr,tc+s,dr,dc,s,tile);else{board[tr+s-1][tc+s]=t;chessBoard(board,tr,tc+s,tr+s-1,tc+s,s,tile);}//左下角if(dr>=tr+s&&dc<tc+s)chessBoard(board,tr+s,tc,dr,dc,s,tile);else{board[tr+s][tc+s-1]=t;chessBoard(board,tr+s,tc,tr+s,tc+s-1,s,tile);}//右下角if(dr>=tr+s&&dc>=tc+s)chessBoard(board,tr+s,tc+s,dr,dc,s,tile);else{board[tr+s][tc+s]=t;chessBoard(board,tr+s,tc+s,tr+s,tc+s,s,tile);}}第五十七頁，共八十四頁。58第五十八頁，共八十四頁。59分治算法舉例5：歸并排序voidmergeSort(Ta[],intleft,intright){if(含有2個以上元素){計算中點位置；歸并排序前半部分；

//分解歸并排序后半部分；

//分解將兩個有序段合并到b；

//合并結(jié)果將b中的結(jié)果復制回a；}}

基本思想:將待排序元素分成大小大致相同的兩個子集合，分別對兩個子集合進行排序，然后將兩個排好序的子集合歸并成一個有序的集合。

第五十九頁，共八十四頁。60template<classT>voidmergeSort(Ta[],intleft,intright){if(left<right){mid=(left+right)/2;//計算中點mergeSort(a,left,mid);//歸并排序前后兩部分mergeSort(a,mid+1,right);merge(a,b,left,mid,right);//將兩個有序段合并到bcopy(a,b,left,right);//將結(jié)果復制到數(shù)組a}}第六十頁，共八十四頁。61第六十一頁，共八十四頁。62第六十二頁，共八十四頁。63（2）成對處理輸入值，用其中較小者與當前最小值比較，用較大值與當前最大值比較，每對數(shù)據(jù)比較3次，共比較次。分治算法舉例6：線性時間選擇在有n個元素的集合中找最小值或最大值需比較n-1次。如果利用錦標賽樹，其他元素需要比較次。（1）分別找出最大值和最小值，比較次數(shù)為2（n-1）同時找到最大值和最小值方法：第六十三頁，共八十四頁。64TrandomizedSelect(Ta[],intp,intr,intk){如果只有一個元素，將其返回；inti=隨機將線性序列分解為兩部分(前小后大）；j=計算前段元素個數(shù);if(第k個小的元素位于前段)采用同樣的方法在前段找第k個小元素；else采用同樣的方法在后段找k-j個小元素;}pirja問題：給定線性序集中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素。第六十四頁，共八十四頁。65Template<classT>TrandomizedSelect(Ta[],intp,intr,intk){if(p==r)returna[p];inti=randomizedPartition(a,p,r);j=i–p+1;if(k<=j)returnrandomizedSelect(a,p,i,k);elsereturnrandomizedSelect(a,i+1,r,k-j);}pirja第六十五頁，共八十四頁。66一種選擇支點元素的方法是使用“中間的中間（median-of-median）”首先將數(shù)組a中的n個元素分成n/r組，r為某一整常數(shù)，除了最后一組外，每組都有r個元素。然后通過在每組中對r個元素進行排序來尋找每組中位于中間位置的元素。最后對所得到的n/r個中間元素，遞歸使用選擇算法，求得”中間之中間”作為支點元素。規(guī)則：第六十六頁，共八十四頁。67如果能在線性時間內(nèi)找到一個劃分基準，使得按這個基準所劃分出的2個子數(shù)組的長度都至多為原數(shù)組長度的ε倍(0<ε<1是某個正常數(shù))，就可以在最壞情況下用O(n)時間完成選擇任務。在最壞情況下，算法randomizedSelect需要O(n2)計算時間。可以證明，算法randomizedSelect可以在O(n)時間內(nèi)找出n個輸入元素中的第k小元素。例如，若ε=9/10，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短1/10。所以，在最壞情況下，算法所需的計算時間T(n)滿足遞歸式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。第六十七頁，共八十四頁。68P={8,17,4,11,3,13,6,19,16,5,7,23,22}Q={25}R={31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}按遞增順序，找出下面29個元素的第18個元素：8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,54,16,5,41,7,23,22,46,29.舉例(1)把前面25個元素分為5(=floor(29/5))組：(8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7).(2)提取每一組的中值元素，構(gòu)成集合{31,49,13,25,16}；(3)遞歸地使用算法求取該集合的中值，得到m=25；(4)根據(jù)m=25,把29個元素劃分為3個子數(shù)組：第六十八頁，共八十四頁。69(7)求取這3組元素的中值元素分別為：{51,43,41}，這個集合的中值元素是43;例子（續(xù)）(5)由于|P|=13,|Q|=1,k=18，所以放棄P,Q，使k=18-13-1=4，對R遞歸地執(zhí)行本算法；(6)將R劃分成3(floor(15/5))組：{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29}(8)根據(jù)43將R劃分成3組：{31,33,35,37,32,41,29},{43},{60,51,57,49,52,54,46}第六十九頁，共八十四頁。70(12)因為k=4,而第一、第二個子數(shù)組的元素個數(shù)為3，所以33即為所求取的第18個小元素。例子（續(xù)）(9)因為k=4，第一個子數(shù)組的元素個數(shù)大于k，所以放棄后面兩個子數(shù)組，以k=4對第一個子數(shù)組遞歸調(diào)用本算法；(10)將這個子數(shù)組分成5個元素的一組：{31,33,35,37,32}，取其中值元素為33；(11)根據(jù)33，把第一個子數(shù)組劃分成{31,32,29},{33},{35,37,41};第七十頁，共八十四頁。71找出這個元素的中位數(shù)。如果是偶數(shù)，就找它的2個中位數(shù)中較大的一個。以這個元素作為劃分基準。將n個輸入元素劃分成個組，每組5個元素，只可能有一個組不是5個元素。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共個。設所有元素不相同。在這種情況下，基準x至少比3個元素大，因為在每一組中有2個元素小于本組的中位數(shù)，而個中位數(shù)中又有個小于基準x。同理，基準x也至少比3個元素小。當n≥75時，3(n-5)/10≥n/4。所以按此基準劃分所得的2個子數(shù)組的長度都至少縮短1/4。第七十一頁，共八十四頁。72Tselect(Ta[],intp,intr,intk){if(少于或等于5個數(shù)值){直接排序;returna[p+k-1];}分組排序，并將中位數(shù)交換到前面;intx=確定中位數(shù)的中位數(shù);inti=partition(p,r,x),j=計算前半?yún)^(qū)個數(shù);if(k<=j)returnselect(a,p,i,k);elsereturnselect(a,i+1,r,k-j);}{if(r-p<5){bubbleSort(p,r);returna[p+k-1];}for(inti=0;i<(r-p+1)/5;i++){ints=p+5*i,intt=s+4;bubbleSort(s,t);swap(a,p+i,s+2);}intx=select(a,p,p+(r-p+1)/5-1,(r-p)/10);inti=partition(p,r,x);j=i-p+1;if(k<=j)returnselect(a,p,i,k);elsereturnselect(a,i+1,r,k-j);}第七十二頁，共八十四頁。73T(n/5)：在n/5個組中找中位數(shù)的中位數(shù)。T(3n/4)：劃分的子序列最多為3n/4。結(jié)論：在這里，將75作為遞歸界限條件，5作為分組大小，可以保證：n/5+3n/4=19n/20=εn，0<ε<1,這是關(guān)鍵。第七十三頁，共八十四頁。74給定平面上n個點的集合S，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。解決方法：將每個點與其余n-1個點的距離計算出來，最小距離者即為最接近點對。時間復雜性O(n2)。(1)一維情形:S中的n個點退化為x軸上的n個實數(shù)x1,x2,…,xn。最接近點對為其中相差最小的2個實數(shù)。分治算法舉例7：最接近點對問題第七十四頁，共八十四頁。75優(yōu)化最接近點對問題算法問題：無法應用于二維點對。解決方法：對所有點進行排序，需要O(n㏒n)。再掃描一遍即可以得出最接近點對。證明得知，該問題的時間下界為Ω(n㏒n)第七十五頁，共八十四頁。76優(yōu)化最接近點對問題算法假設用x軸上某個點m將S劃分為2個子集S1和S2，基于平衡子問題的思想，用S中各點坐標的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對{p1,p2}和{q1,q2}，并設d=min{|p1-p2|,|q1-q2|}，S中的最接近點對或者是{p1,p2}，或是{q1,q2}，或是某個{p3,q3}，其中p3∈S1且q3∈S2。思考：能否在線性時間內(nèi)找到p3,q3？第七十六頁，共八十四頁。77如果S的最接近點對是{p3,q3}，即|p3-q3|<d，則p3和q3兩者與m的距離不超過d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每個長度為d的半閉區(qū)間至多包含一個點（否則必有兩點距離小于d），并且m是S1和S2的分割點，因此(m-d,m]中至多包含S中的一個點。由圖可以看出，如果(m-d,m]中有S中的點，則此點就是S1中最大點。因此，用線性時間就能找到區(qū)間(m-d,m]和(m,m+d]中所有點，即p3和q3。從而用線性時間就可以將S1的解和S2的解合并成為S的解。第七十七頁，共八十四頁。78一維點集S的最接近點對的算法doublecpair1(S){//排序,Ω(n㏒n)n=|S|;if(n<2)return∞;m=S中各點坐標的中位數(shù)；//線性時間構(gòu)造S1和S2;//線性時間d1=cpair1(S1);//計算左側(cè)的最接近距離d2=cpair1(S2);//計算右側(cè)的最接近距離p=max(S1);//左側(cè)最大值,線性時間q=min(S2);//右側(cè)最小值,線性時間d=m