《算法设计与分析》第05章

1第5章分治法

25.1

分治法的基本思想5.2

求最大最小元 5.3

二分搜索5.4

排序问题5.5选择问题5.6斯特拉森矩阵乘法

35.1.1分治法的基本思想

分治法顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。

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算法分析

采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：T(n)=aT(n/b)+cnk，T(1)=c

a个规模为n/b的子问题问题分解与解的合并7定理5-1设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则，

89设r=bk/a，下面分三种情况计算。（1）若r<1，则

所以（2）若r=1，则

所以（3）若r>1，则

所以105.1.3

数据结构【程序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

设有n个元素的表，假定n是2的幂，即n=2k，k是正整数，程序5－5在最好、平均和最坏情况下的比较次数都为3n/2–2。185.3二分搜索19问题在有序表（已按关键字值非减排序）中搜索给定元素的问题。205.3.1

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

在范围为[left,right]的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回－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

对半搜索

对半搜索对半搜索是一种二分搜索。设当前搜索的子表为（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的对半搜索递归函数BSearch是正确的。255.3.3

二叉判定树

二分搜索过程的算法行为可以用一棵二叉树来描述。通常称这棵描述搜索算法执行过程的二叉树为二叉判定树(binarydecisiontree)。2627性质5－1

具有n个内结点的对半搜索二叉判定树的左子树上有(n-1)/2个内结点，右子树上有n/2个内结点。

性质5－2

具有n(n>0）个内结点的二叉判定树的高度为logn+1

（不计外结点）。

28性质5－3

若n=2h-1，则对半搜索二叉判定树是满二叉树。

性质5－4

若n=2h-1，则对半搜索二叉判定树的外结点均在h+1层上，否则，在第h或h+1层上，h=logn+1。

29定理5－4

对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过logn+1。对于不成功的搜索，算法需要作logn或logn+1次比较。定理5－5

对半搜索算法在搜索成功时的平均时间复杂度为(logn)。

305.3.4搜索算法的时间下界

定理5－6

在一个有n个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作log

n+1次比较。315.4排序问题

32

问题排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。335.4.1

合并排序

合并两个有序序列

两路合并排序的基本运算是把两个有序序列合并成一个有序序列。

34【程序5－9】Merge函数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

分治法求解将待排序的元素序列一分为二分，得到两个长度基本相等的子序列，如同对半搜索的做法；然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过1为止；当分解所得的子序列已排列有序，可以采用上面介绍的将两个有序子序列，合并成一个有序子序列的方法，实现将子问题的解组合成原问题解，这是分治法不可缺少的一步。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

性能分析合并排序递归算法的时间复杂度为O(nlog

n)。405.4.2

快速排序快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列(K0,K1,…,Kn-1)中选择一个元素作为分划元素，也称为主元（pivot）。不妨假定选择K为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都不小于主元。41

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

分划函数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

任何一个通过关键字值比较对n个元素进行排序的算法，在最坏情况下，至少需作（n/4）log

n次比较。49505.5选择问题

51问题选择问题（selectproblem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。

525.5.1

分治法求解

设原表长度为n，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为p，右子表是主元右边元素的子表。那么，若k=p，则主元就是第k小元素；否则若k<p，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若k>p，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。535.5.2

随机选择主元

随机选主元算法

假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。54

【程序5－13】Select函数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)。算法的最坏情况时间复杂度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为主元，经过一趟分划，左、右两个子表的大小均至多为：

nn/r/2

r/2

设T(n)为当表长为n时执行程序5－14所需的时间。T(n)由三部分时间组成：

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

用归纳法容易证明，T(n)20cn，n1是线性时间的。

625.5.5允许重复元素的选择算法由于允许包含相同元素，左子表中除了小于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的幂。使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：由此可得：复杂度分析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)为了降低时间复杂度，必须减少乘法的次数。而其关键在于计算2个2阶方阵的乘积时所用乘法次数能否少于8次。为此，Strassen提出了一种只用7次乘法运算计算2阶方阵乘积的方法（但增加了加/减法次数）：68C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)=(nlog7)(n2.81)

做了这7次乘法后，在做若干次加/减法就可以得到：较大的改进69更快的方法Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究3×3或5×5矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.376)，最好下界是(n2)。是否能找到O(n2)的算法？目前为止还没有结果。70补充：大整数的乘法设计一个有效的算法，可以进行两个n位大整数的乘法运算小学的方法：O(n2)效率太低分治法:X=a2n/2+bY=c2n/2+dXY=ac2n+(ad+bc)2n/2+bd复杂度分析

T(n)=O(n2)没有改进

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

Y=ABCD71算法改进为了降低时间复杂度，必须减少乘法的次数。为此，我们把XY写成另外的形式：XY=ac2n+((a-c)(b-d)+ac+bd)2n/2+bd或XY=ac2n+((a+c)(b+d)-ac-bd)2n/2+bd复杂性：这两个算式看起来更复杂一些，但它们仅需要3次n/2位乘法[ac、bd和(a±c)(b±d)]，于是

T(n)=O(nlog3)=O(n1.59)较大的改进细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。72更快的方法小学的方法：O(n2)——效率太低分治法:O(n1.59)——较大的改进更快的方法？如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(FastFourierTransform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。73棋盘覆盖问题在一个2k×2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，覆盖任意一个2k×2k的特殊棋盘，用到的骨牌数恰好为(4k-1)/3。74分治策略求解当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1

子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。75说明：整形二维数组Board表示棋盘，Borad[0][0]是棋盘的左上角方格。tile是一个全局整形变量，用来表示L形骨牌的编号，初始值为0。tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号；dr：特殊方格所在的行号；dc：特殊方格所在的列号；size：size=2k，棋盘规格为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复杂度分析复杂度分析：

T(k)=4k-1=O(4k)渐进意义下的最优算法78最接近点对问题问题描述：给定平面上n个点，找其中的一对点，使得在n个点所组成的所有点对中，该点对间的距离最小。说明：严格来讲，最接近点对可能多于一对，为简便起见，我们只找其中的一对作为问题的解。一个简单的做法是将每一个点与其他n-1个点的距离算出，找出最小距离的点对即可。该方法的时间复杂性是T(n)=n(n-1)/2+n=O(n2)，效率较低。已经证明，该算法的计算时间下界是Ω(nlogn)。79一维空间中的情形先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。一个简单的办法是先把x1,x2,…,xn排好序，再进行一次线性扫描就可以找出最接近点对，T(n)=O(nlogn)。然而这种方法无法推广到二维情形。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。能否在线性时间内找到p3,q3？80如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈[m,m+d)。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m]和[m,m+d)中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。分割点m的选取不当，会造成|Si|=1，|Sj|=n-1的情形，使得T(n)=T(n-1)+O(n)=O(n2)。这种情形可以通过“平衡子问题”方法加以解决：选取各点坐标的中位数作分割点。一维空间中的情形81算法描述及复杂性算法描述：boolCPair1(S,d){n=|S|;if(n<2){d=∞;returnfalse;}m=Blum(S);//S各点坐标中位数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;}复杂性分析：

T(n)=O(nlogn)该算法可推广到二维的情形中去。82二维空间的最接近点对问题下面来考虑二维的情形。选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2，如图所示。能否在线性时间内找到p,q？考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中，如图所示。由d的意义可知，P2中任何2