《算法設(shè)計與分析》第05章

1第5章分治法

25.1

分治法的基本思想5.2

求最大最小元 5.3

二分搜索5.4

排序問題5.5選擇問題5.6斯特拉森矩陣乘法

35.1.1分治法的基本思想

分治法顧名思義就是分而治之。一個問題能夠用分治法求解的要素是：第一，問題能夠按照某種方式分解成若干個規(guī)模較小、相互獨立且與原問題類型相同的子問題；第二，子問題足夠小時可以直接求解；第三，能夠?qū)⒆訂栴}的解組合成原問題的解。由于分治法要求分解成同類子問題，并允許不斷分解，使問題規(guī)模逐步減小，最終可用已知的方法求解足夠小的問題，因此，分治法求解很自然導(dǎo)致一個遞歸算法。

4【程序5-1】

分治法SolutionTypeDandC(ProblemTypeP){ ProblemTypeP1，P2，，Pk; if(Small(P))returnS(P); else{ Divide(P，P1，P2，，Pk); ReturnCombine(DandC(P1)，

DandC(P2)，…，DandC(Pk)); }}5【程序5-2】

一分為二的分治法SolutionTypeDandC(intleft，intright){ if(Small(left,right))returnS(left,right); else{ intm=Divide(left，right); ReturnCombine(DandC(left，m)，

DandC(m+1，right)); }}65.1.2算法分析

采用分治法求解問題通常得到一個遞歸算法。如果較大的問題被分解成同樣大小的幾部分，那么分析相應(yīng)算法的執(zhí)行時間，往往可得到如下的遞推關(guān)系式：T(n)=aT(n/b)+cnk，T(1)=c

a個規(guī)模為n/b的子問題問題分解與解的合并7定理5-1設(shè)a,b,c和k為常數(shù)，T(n)=aT(n/b)+cnk，T(1)=c，則，

89設(shè)r=bk/a，下面分三種情況計算。（1）若r<1，則

所以（2）若r=1，則

所以（3）若r>1，則

所以105.1.3

數(shù)據(jù)結(jié)構(gòu)【程序5－3】可排序表類template<classK,classD>structE{//可排序表中元素的類型

operatorK()const{returnkey;}Kkey;Ddata;};11template<classT>classSortableList{//可排序表類public:SortableList(intmSize);~SortableList();

private:

T*l;intmaxSize;intn;};125.2求最大最小元

13

問題在一個元素集合中尋找最大元素和最小元素的問題。145.2.1

分治法求解【程序5－4】求最大最小元template<classT>voidSortableList<T>::MaxMin(T&max,T&min)const{ if(n==0)return; max=min=l[0]; for(inti=1;i<n;i++){ if(l[i]>max)max=l[i]; if(l[i]<min)min=l[i]; }}15【程序5－5】分治法求最大最小元template<classT>voidSortableList<T>::MaxMin(inti,intj,T&max,T&min)const{ Tmin1,max1; if(i==j)max=min=l[i];elseif(i==j-1) if(l[i]<l[j]){ max=l[j];min=l[i]; } else{ max=l[i];min=l[j]; } 16 else{ intm=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if(max<max1)max=max1; if(min>min1)min=min1; }}

175.2.2時間分析定理5－2

設(shè)有n個元素的表，假定n是2的冪，即n=2k，k是正整數(shù)，程序5－5在最好、平均和最壞情況下的比較次數(shù)都為3n/2–2。185.3二分搜索19問題在有序表（已按關(guān)鍵字值非減排序）中搜索給定元素的問題。205.3.1

分治法求解intSortableList<T>::BSearch(constT&x,intleft,intright)const后置條件:

在范圍為[left,right]的表中搜索與x有相同關(guān)鍵字值的元素；如果存在該元素，則函數(shù)返回該元素在表中的位置，否則函數(shù)返回－1，表示搜索失敗。21【程序5－6】二分搜索算法框架template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{ if(left<=right){intm=Divide(left+right);if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right); elsereturnm;}return-1;}225.3.2

對半搜索

對半搜索對半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表為（aleft,aleft+1,…,aright），令

m=(left+right)/2

23【程序5－7】對半搜索遞歸算法template<classT>intSortableList<T>::BSearch(constT&x,intleft,intright)const{if(left<=right){intm=(left+right)/2;if(x<l[m])returnBSearch(x,left,m-1); elseif(x>l[m])returnBSearch(x,m+1,right);elsereturnm;}return-1;}24定理5－3對于n0，程序5－7的對半搜索遞歸函數(shù)BSearch是正確的。255.3.3

二叉判定樹

二分搜索過程的算法行為可以用一棵二叉樹來描述。通常稱這棵描述搜索算法執(zhí)行過程的二叉樹為二叉判定樹(binarydecisiontree)。2627性質(zhì)5－1

具有n個內(nèi)結(jié)點的對半搜索二叉判定樹的左子樹上有(n-1)/2個內(nèi)結(jié)點，右子樹上有n/2個內(nèi)結(jié)點。

性質(zhì)5－2

具有n(n>0）個內(nèi)結(jié)點的二叉判定樹的高度為logn+1

（不計外結(jié)點）。

28性質(zhì)5－3

若n=2h-1，則對半搜索二叉判定樹是滿二叉樹。

性質(zhì)5－4

若n=2h-1，則對半搜索二叉判定樹的外結(jié)點均在h+1層上，否則，在第h或h+1層上，h=logn+1。

29定理5－4

對半搜索算法在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過logn+1。對于不成功的搜索，算法需要作logn或logn+1次比較。定理5－5

對半搜索算法在搜索成功時的平均時間復(fù)雜度為(logn)。

305.3.4搜索算法的時間下界

定理5－6

在一個有n個元素的集合中，通過關(guān)鍵字值之間的比較，搜索指定關(guān)鍵字值的元素，任意這樣的算法在最壞情況下至少需要作log

n+1次比較。315.4排序問題

32

問題排序是將一個元素序列調(diào)整為按指定關(guān)鍵字值的遞增（或遞減）次序排列的有序序列。335.4.1

合并排序

合并兩個有序序列

兩路合并排序的基本運算是把兩個有序序列合并成一個有序序列。

34【程序5－9】Merge函數(shù)template<classT>voidSortableList<T>::Merge(intleft,intmid,intright){ T*temp=newT[right-left+1];inti=left,j=mid+1,k=0;while((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++];elsetemp[k++]=l[j++];while(i<=mid)temp[k++]=l[i++];while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++];}3536

分治法求解將待排序的元素序列一分為二分，得到兩個長度基本相等的子序列，如同對半搜索的做法；然后對兩個子序列分別排序，如果子序列較長，還可繼續(xù)細(xì)分，直到子序列的長度不超過1為止；當(dāng)分解所得的子序列已排列有序，可以采用上面介紹的將兩個有序子序列，合并成一個有序子序列的方法，實現(xiàn)將子問題的解組合成原問題解，這是分治法不可缺少的一步。37【程序5－10】兩路合并排序template<classT>voidSortableList<T>::MergeSort(intleft,intright){if(left<right){intmid=(left+right)/2;MergeSort(left,mid);MergeSort(mid+1,right);Merge(left,mid,right);}}3839

性能分析合并排序遞歸算法的時間復(fù)雜度為O(nlog

n)。405.4.2

快速排序快速排序采用一種特殊的分劃操作對排序問題進行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中選擇一個元素作為分劃元素，也稱為主元（pivot）。不妨假定選擇K為主元。經(jīng)過一趟特殊的分劃處理將原序列中的元素重新排列，使得以主元為軸心，將序列分成左右兩個子序列。主元左測子序列中所有元素都不大于主元，主元右測子序列中所有元素都不小于主元。41

分劃操作42【程序5－11】

分劃函數(shù)template<classT>intSortableList<T>::Partition(intleft,intright){//前置條件：leftright inti=left,j=right+1;do{doi++;while(l[i]<l[left]);doj--;while(l[j]>l[left]);if(i<j)Swap(i,j);}while(i<j); Swap(left,j); returnj;}43快速排序算法44【程序5－12】快速排序template<classT>voidSortableList<T>::QuickSort(){QuickSort(0,n-1);}template<classT>voidSortableList<T>::QuickSort(intleft,intright){ if(left<right){intj=Partition(left,right);QuickSort(left,j-1); QuickSort(j+1,right); }}45

時間分析最壞情況時間

W(n)W(n-1)+n+1

W(n-2)+(n+1)+n

W(1)+(n+1)++3=O(n2)

46平均情況時間

47485.4.3排序算法的時間下界定理5－7

任何一個通過關(guān)鍵字值比較對n個元素進行排序的算法，在最壞情況下，至少需作（n/4）log

n次比較。49505.5選擇問題

51問題選擇問題（selectproblem）是指在n個元素的集合中，選出某個元素值大小在集合中處于第k位的元素，即所謂的求第k小元素問題(kth-smallest)。

525.5.1

分治法求解

設(shè)原表長度為n，假定經(jīng)過一趟分劃，分成兩個左右子表，其中左子表是主元及其左邊元素的子表，設(shè)其長度為p，右子表是主元右邊元素的子表。那么，若k=p，則主元就是第k小元素；否則若k<p，第k小元素必定在左子表中，需求解的子問題成為在左子表中求第k小元素；若k>p，則第k小元素必定在右子表中，需求解的子問題成為在右子表中求第k-p小元素。535.5.2

隨機選擇主元

隨機選主元算法

假定表中元素各不相同，并且隨機選擇主元，即在下標(biāo)區(qū)間[left,right]中隨機選擇一個下標(biāo)r，以該下標(biāo)處的元素為主元。54

【程序5－13】Select函數(shù)template<classT>ResultCodeSortableList<T>::Select1(T&x,intk){if(n<=0||k>n||k<=0)returnOutOfBounds;intleft=0,right=n;l[n]=INFTY;do{ intj=rand()%(right-left+1)+left; Swap(left,j); j=Partition(left,right); if(k==j+1){x=l[j];returnSuccess;} elseif(k<j+1)right=j; elseleft=j+1; }while(true);}55定理5－8

程序5－13的Select算法的平均時間A(n)=O(n)。算法的最壞情況時間復(fù)雜度O(n2)。565.5.3

線性時間選擇算法改進的選擇算法采用二次取中法(medianofmediansrule)確定主元

5758

【程序5－14】線性時間選擇算法ResultCodeSortableList<T>::Select(T&x,intk){ if(n<=0||k>n||k<=0)returnOutOfBounds; intj=Select(k,0,n-1,5); x=l[j];returnSuccess;}

59template<classT>intSortableList<T>::Select(intk,intleft,intright,intr){intn=right-left+1;if(n<=r){InsertSort(left,right);returnleft+k-1;

}60for(inti=1;i<=n/r;i++){InsertSort(left+(i-1)*r,left+i*r-1);Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);}intj=Select(Ceil(n/r,2),left,left+(n/r)-1,r);Swap(left,j);j=Partition(left,right);if(k==j-left+1)returnj;elseif(k<j-left+1)returnSelect(k,left,j-1,r);elsereturnSelect(k-(j-left+1),j+1,right,r);}615.5.4時間分析

以二次取中的中間值mm為主元，經(jīng)過一趟分劃，左、右兩個子表的大小均至多為：

nn/r/2

r/2

設(shè)T(n)為當(dāng)表長為n時執(zhí)行程序5－14所需的時間。T(n)由三部分時間組成：

T(n)T(n/5)+T(3n/4)+cn

用歸納法容易證明，T(n)20cn，n1是線性時間的。

625.5.5允許重復(fù)元素的選擇算法由于允許包含相同元素，左子表中除了小于mm的元素外，還包含與mm相同值的元素。因此，左子表的大小至多可達

nn/r/2

r/2+1/2n/r/2

r/2

=n-1/2n/r/2

r/2

容易用歸納法證明對于所有n90，

T(n)T(n/9)+T(7n/8)+cn72cn，n90635.6斯特拉森(Strassen)矩陣乘法

64問題矩陣相乘

65n×n矩陣A和B的乘積矩陣C中的元素C[i,j]定義為：若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的n2個元素所需的計算時間為O(n3)66簡單分治法求矩陣乘首先假定n是2的冪。使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：由此可得：復(fù)雜度分析T(n)=O(n3)

沒有改進675.6.2

斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。而其關(guān)鍵在于計算2個2階方陣的乘積時所用乘法次數(shù)能否少于8次。為此，Strassen提出了一種只用7次乘法運算計算2階方陣乘積的方法（但增加了加/減法次數(shù)）：68C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)=(nlog7)(n2.81)

做了這7次乘法后，在做若干次加/減法就可以得到：較大的改進69更快的方法Hopcroft和Kerr已經(jīng)證明(1971)，計算2個２×２矩陣的乘積，7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復(fù)雜性，就不能再基于計算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究3×3或5×5矩陣的更好算法。在Strassen之后又有許多算法改進了矩陣乘法的計算時間復(fù)雜性。目前最好的計算時間上界是O(n2.376)，最好下界是(n2)。是否能找到O(n2)的算法？目前為止還沒有結(jié)果。70補充：大整數(shù)的乘法設(shè)計一個有效的算法，可以進行兩個n位大整數(shù)的乘法運算小學(xué)的方法：O(n2)效率太低分治法:X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd復(fù)雜度分析

T(n)=O(n2)沒有改進

n/2位n/2位n/2位n/2位X=

Y=ABCD71算法改進為了降低時間復(fù)雜度，必須減少乘法的次數(shù)。為此，我們把XY寫成另外的形式：XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd或XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd復(fù)雜性：這兩個算式看起來更復(fù)雜一些，但它們僅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是

T(n)=O(nlog3)=O(n1.59)較大的改進細(xì)節(jié)問題：兩個XY的復(fù)雜度都是O(nlog3)，但考慮到a+c,b+d可能得到m+1位的結(jié)果，使問題的規(guī)模變大，故不選擇第2種方案。72更快的方法小學(xué)的方法：O(n2)——效率太低分治法:O(n1.59)——較大的改進更快的方法？如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來，將有可能得到更優(yōu)的算法。最終的，這個思想導(dǎo)致了快速傅利葉變換(FastFourierTransform)的產(chǎn)生。該方法也可以看作是一個復(fù)雜的分治算法，對于大整數(shù)乘法，它能在O(nlogn)時間內(nèi)解決。是否能找到線性時間的算法？目前為止還沒有結(jié)果。73棋盤覆蓋問題在一個2k×2k個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。易知，覆蓋任意一個2k×2k的特殊棋盤，用到的骨牌數(shù)恰好為(4k-1)/3。74分治策略求解當(dāng)k>0時，將2k×2k棋盤分割為4個2k-1×2k-1

子棋盤(a)所示。特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如(b)所示，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。75說明：整形二維數(shù)組Board表示棋盤，Borad[0][0]是棋盤的左上角方格。tile是一個全局整形變量，用來表示L形骨牌的編號，初始值為0。tr：棋盤左上角方格的行號；tc：棋盤左上角方格的列號；dr：特殊方格所在的行號；dc：特殊方格所在的列號；size：size=2k，棋盤規(guī)格為2k×2k。76算法描述voidCB(inttr,tc,dr,dc,size){ if(size==1)return;intt=tile++;//L型骨牌號s=size/2;//分割棋盤//覆蓋左上角子棋盤if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盤中CB(tr,tc,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋右下角board[tr+s-1][tc+s-1]=t;//覆蓋其余方格CB(tr,tc,tr+s-1,tc+s-1,s);}//覆蓋右上角子棋盤if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盤中CB(tr,tc+s,dr,dc,s);else{//此棋盤中無特殊方格//用t號L型骨牌覆蓋左下角board[tr+s-1][tc+s]=t;//覆蓋其余方格CB(tr,tc+s,tr+s-1,tc+s,s);}//覆蓋左下角子棋盤if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盤中CB(tr+s,tc,dr,dc,s);else{//用t號L型骨牌覆蓋右上角board[tr+s][tc+s-1]=t;//覆蓋其余方格CB(tr+s,tc,tr+s,tc+s-1,s);}//覆蓋右下角子棋盤if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盤中CB(tr+s,tc+s,dr,dc,s);else{//用t號L型骨牌覆蓋左上角board[tr+s][tc+s]=t;//覆蓋其余方格CB(tr+s,tc+s,tr+s,tc+s,s);}}77復(fù)雜度分析復(fù)雜度分析：

T(k)=4k-1=O(4k)漸進意義下的最優(yōu)算法78最接近點對問題問題描述：給定平面上n個點，找其中的一對點，使得在n個點所組成的所有點對中，該點對間的距離最小。說明：嚴(yán)格來講，最接近點對可能多于一對，為簡便起見，我們只找其中的一對作為問題的解。一個簡單的做法是將每一個點與其他n-1個點的距離算出，找出最小距離的點對即可。該方法的時間復(fù)雜性是T(n)=n(n-1)/2+n=O(n2)，效率較低。已經(jīng)證明，該算法的計算時間下界是Ω(nlogn)。79一維空間中的情形先來考慮一維的情形。此時，S中的n個點退化為x軸上的n個實數(shù)x1,x2,…,xn。最接近點對即為這n個實數(shù)中相差最小的2個實數(shù)。一個簡單的辦法是先把x1,x2,…,xn排好序，再進行一次線性掃描就可以找出最接近點對，T(n)=O(nlogn)。然而這種方法無法推廣到二維情形。假設(shè)我們用x軸上某個點m將S劃分為2個子集S1和S2，基于平衡子問題的思想，用S中各點坐標(biāo)的中位數(shù)來作分割點。遞歸地在S1和S2上找出其最接近點對{p1,p2}和{q1,q2}，并設(shè)d=min{|p1-p2|,|q1-q2|}，S中的最接近點對或者是{p1,p2}，或者是{q1,q2}，或者是某個{p3,q3}，其中p3∈S1且q3∈S2。能否在線性時間內(nèi)找到p3,q3？80如果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的解。分割點m的選取不當(dāng)，會造成|Si|=1，|Sj|=n-1的情形，使得T(n)=T(n-1)+O(n)=O(n2)。這種情形可以通過“平衡子問題”方法加以解決：選取各點坐標(biāo)的中位數(shù)作分割點。一維空間中的情形81算法描述及復(fù)雜性算法描述：boolCPair1(S,d){n=|S|;if(n<2){d=∞;returnfalse;}m=Blum(S);//S各點坐標(biāo)中位數(shù)S=>S1+S2;//S1={x|x<=m}S2={x|x>m}CPair1(S1,d1);CPair1(S2,d2);p=max(S1);q=min(S2);d=min(d1,d2,q-p);returnture;}復(fù)雜性分析：

T(n)=O(nlogn)該算法可推廣到二維的情形中去。82二維空間的最接近點對問題下面來考慮二維的情形。選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=min{d1,d2}，S中的最接近點對或者是d，或者是某個{p,q}，其中p∈P1且q∈P2，如圖所示。能否在線性時間內(nèi)找到p,q？考慮P1中任意一點p，它若與P2中的點q構(gòu)成最接近點對的候選者，則必有distance(p，q)＜d。滿足這個條件的P2中的點一定落在一個d×2d的矩形R中，如圖所示。由d的意義可知，P2中任何2