算法设计与分析第三章 分治法

计算机算法设计与分析NorthChinaElectricPowerUniversityComputerAlgorithmsDesign&Analysis华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第三章分治法★分治法的基本思想★二分搜索技术★第K小元素问题NorthChinaElectricPowerUniversity★合并排序★大整数乘法★Strassen矩阵乘法§1分治法的基本思想NorthChinaElectricPowerUniversity分治法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：1)把它分成两个或多个更小的问题；2)分别解决每个小问题；3)把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。分治法所能解决的问题一般具有以下几个特征(适用条件)1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题；即该问题具有最优子结构性质；3.利用该问题分解出的子问题的解可以合并为该问题的解；4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。if问题规模小到可以直接解决直接解决该问题else将问题分解成ｋ个规模较小的子问题for(i=1;i=k;i++)递归调用该分治算法，分别解决每一个子问题将各子问题的解合并为原问题的解分治的具体过程：NorthChinaElectricPowerUniversityDivide_and_Conquer（P）if|P|≤n0thenreturn（ADHOC（P））将P分解为较小的子问题P1、P2、...、Pkfori←1tokdoyi←Divide_and_Conquer（Pi）△递归解决PiT←MERGE（y1，y2，...，yk）△合并子问题Return（T）一般的算法设计模式如下：NorthChinaElectricPowerUniversity根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。分治策略算法的复杂度分析T(n)=af(n/b)+d(n)他的复杂度分析采用递归算法提到的Master定理NorthChinaElectricPowerUniversity例[伪币问题]：给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。给你一台没有砝码的天平，试用较少的测量次数找出这个伪币。X1-8:X9-16X1-4:X5-8X9-12:X13-16X1-2:X3-4X5-6:X7-8X9-10:X11-12X13-14:X15-16X1X1:X2X3:X4X5:X6X7:X8X9:X10X11:X12X13:X14X15:X16X2X3X4X5X6X7X8X9X10X11X12X13X14X15X16§2二分搜索技术NorthChinaElectricPowerUniversity问题描述：给定已排序好的n个元素a[1:n],现在要在这n个元素中找出一特定元素x。二分搜索法的基本思想：将n个元素分成大致相同的两半，取a[n/2]与x做比较，如果x=a[n/2]则，则找到x，算法终止；如果x≤a[n/2]，则只要在a的左半部继续搜索；如果xa[n/2]，则只要在a的右半部继续搜索。templateclassTypeintBinary_Search(Typea[],intleft,intright,constType&x){if(leftright)return(-1);else{m=(left+right)/2;if(x==a[m])thenreturn(m);elseif(xa[m])return(Binary_Search(a,m+1,right,x));elsereturn(Binary_Search(a,left,m-1,x));}}NorthChinaElectricPowerUniversity设在n个元素的数组中查找x需要的比较次数为T(n)，如果每次比较x和a[m]时，总有xa[m]，即x根本不在L中，则：T(n)=2+T(n/2),T(1)=1该方程的解为T(n)=O(logn)。所以在最坏情况下二分查找法的复杂度为O(logn)。T(n)2T(n/2)2……T(1)2222……2logn=Θ(logn)问题：n个元素的排序问题，即将n个元素按一定规则排列成一个有序序列。§3分治-归并排序简单选择排序的思想：将这n个元素存储在一个数组中，首先通过n-1次比较找出这个数组中的最小元素，并将这个元素与数组中的第一个交换。如果挑选出的元素恰好占交换后应占的元素位置，则交换不必进行。第i次在剩余的n-i+1个元素中找出最小元素与第i个元素交换。重复这一步骤，直到i=n-1。T(n)=T(n-1)+n-1其时间复杂性为：T(n)n-1T(n-1)n-2……T(1)0T(n)=n-1+n-2+…+2+1+0=n(n-1)/2NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity分治-归并排序算法是用分治策略实现对n个元素进行排序的算法。基本思想：当n=1时终止排序，否则将待排序元素分成大小大致相同的两个子集，分别对两个子集进行排序，最终将排序好的子集合并成为所要求的排序好的集合。templateclassTypevoidMsort(Typer[],Typer1[],ints,intt);{if(s=t)r1[s]=r[s]else{m=(s+t)/2;//将r[s..t]平分为r[s..m]和r[m+1..t]Msort(r,r1,s,m);Msort(r,r1,m+1,t);Merge(r,r1,s,m,t);Copy(r1,r,s,t);}}templateclassTypevoidMerge_sort(Typer[],Typer1[],intn){MSort(r,r1,1,n);//对记录序列r[1..t]作2-路归并排序}NorthChinaElectricPowerUniversityMerge和Copy可以在O(n)时间内完成，因此分治归并排序算法所需的时间T(n)满足：T(n)=O(1)n=22T(n/2)+O(n)n2解此递归方程可得T(n)=O(nlogn)templateclassTypevoidMerge(Typer[],Typer1[],ints,intm,intt){i=s;k=s;j=m+1;while((i=m)&&(j=t)){if(r[i]=r[j]){[r1[k]=r[i];i=i+1;}else{r1[k]=r[j];j=j+1;}k=k+1;}if(im)Copy(r,j,t,r1);elseCopy(r,i,m,r1);}T(n)nT(n/2)n/2T(n/2)n/2T(n/2)n/2T(n/2)n/2T(n/2)n/2T(n/2)n/2nnnn……Θ(nlogn)NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity例：[金块问题]老板有一袋金块(共n块，n是2的幂（n=2）)，将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。也就是这样一个问题,同时求n个数中的最大值和最小值，n为2的整数次幂。templateclassTypevoidMaxmin(Typex[],intl,intr,Type&max,Type&min){if(r-l==0){max=x[l];min=x[l];return;}if(r-l==1){if(x[l]=x[r]){max=x[r];min=x[l];}else{max=x[l];min=x[r];}return;}intm=(l+r)/2;Typea,b,c,d;Maxmin(x,l,m,a,b);Maxmin(x,m+1,r,c,d);if(a=c)max=a;elsemax=c;if(b=d)min=b;elsemin=d;return;}NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity问题描述:设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。§4大整数乘法分析：按正常的乘法规则要做n2次一位数的乘法，计算步骤太多。下面用分治法来解决此问题。将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图所示。由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD(1)NorthChinaElectricPowerUniversity上述算法的时间复杂性为：设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，有:解得T(n)=O(n2)。由此可见，仍需要n2次乘法。将(1)改写为下面的形式：XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD(3)虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。由此可得:其解为T(n)=O(nlog3)=O(n1.59)NorthChinaElectricPowerUniversity大整数相乘的完整算法Mult如下:intMult(X，Y，n);{S=SIGN(X)*SIGN(Y);//S为X和Y的符号乘积X=abs(X);Y=abs(Y);//X和Y分别取绝对值if(n==1){if((X==1)&&(Y==1))return(S);elsereturn(0)；}else{A=X的左边n/2位;B=X的右边n/2位;C=Y的左边n/2位;D=Y的右边n/2位;ml=Mult(A,C,n/2);m2=Mult(A-B,D-C,n/2);m3=Mult(B,D,n/2);S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);return(S);}}NorthChinaElectricPowerUniversity设X=314l,Y=5327，用上述算法计算XY的计算过程可列表如下，其中带'号的数值是在计算完成AC，BD，和(A-B)(D-C)之后才填入的。X=3141A=31B=41A-B=-10Y=5327C=53D=27D-C=-26AC=(1643)'BD=(1107)'(A-B)(D-C)=(260)'XY=(1643)'104+[(1643)'+(260)'+(1107)']102+(1107)'=(16732107)'A=31A1=3B1=1A1-B1=2C=53C1=5D1=3D1-C1=-2A1C1=15B1D1=3(A1-B1)(D1-C1)=-4AC=1500+(15+3-4)10+3=1643NorthChinaElectricPowerUniversityB=41A2=4B2=1A2-B2=3D=27C2=2D2=7D2-C2=5A2C2=8B2D2=7(A2-B2)(D2-C2)=15BD=800+(8+7+15)10+7=1107|A-B|=10A3=1B3=0A3-B3=1|D-C|=26C3=2D3=6D3-C3=4A3C3=2B3D3=0(A3-B3)(D3-C3)=4(