《算法分析与设计分治法ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计分治法ppt课件.ppt（63页珍藏版）》请在三一办公上搜索。
1、算法分析与设计,第二章 分治法,第二章 分治法,什么是分治法？二分检索找最大和最小元素归并分类快速分类选择问题斯特拉森矩阵乘法,2.1 分治法的一般方法,问题(N个输入),分治策略DANDC的抽象化控制,Procedure DANDC(p,q)global n,A(1:n);integer m,p,q;/1pqn/if SMALL(p,q)then return(G(p,q)else mDIVIDE(p,q)/pmq/return(COMBINE(DANDC(p,m),DANDC(m+1,q)endifEnd DANDC,分治策略DANDC的计算时间,倘若所分成的两个子问题的输入规模大致相等，
2、则分治策略DANDC的计算时间可表示为：T(n)=,g(n)n足够小,2T(n/2)+f(n)否则,说明：T(n)是输入规模为n的分治策略的计算时间 g(n)是对足够小的输入规模能直接计算出答案的时间 f(n)是COMBINE解合成原问题的计算时间,2.2 二分检索,问题描述已知一个按非降次序排列的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，若是，则找出该元素在表中的位置，并置于j，否则，置j为0。一般解决方法（从头到尾查找一遍）,x,成功和不成功的计算时间都是n,二分检索原理,将问题表示为：I=(n,a1,an,x)选取一个下标k，可得到三个子问题：I1=(k-1,a1,ak
3、-1,x)I2=(1,ak,x)I3=(n-k,ak+1,an,x)如果对所求解的问题（或子问题）所选的下标k都是中间元素的下标，k=(n+1)/2，则由此产生的算法就是二分检索算法。,二分检索算法,Procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highn if(n0)while（lowhigh）do mid(low+high)/2/*取中间值*/case xAmid:lowmid+1/*寻找后一半*/else:jmid;return/*检索成功*/endcase j0/*检索失败*/End BINSRCH,二分检索算法实例,假
4、设在数组A(1:9)中顺序放了以下9个元素：-15,-6,0,7,9,23,54,82,101要求检索的x分别为：101,-14,82,X=101Lowhighmid195697898999OK,X=-14Lowhighmid195142111 2 1NO,X=82Lowhighmid195697898OK,二分检索算法正确性的证明,用五个特性判断是否是一个算法根据算法的描述，满足五个特性的才是算法证明算法是否正确如果n=0，则不进入循环，j=0，算法终止否则就会进入循环与数组A中的元素进行比较如果x=Amid，则j=mid，检索成功，算法终止否则，若xA(mid)，则缩小到A(mid+1)和
5、A(n)之间检索按上述方式缩小检索区总可以在有限步内使lowhigh如果出现这种情况，说明x不在A中，j=0，算法终止,二分检索算法所需的空间和时间,所需空间用n个位置存放数组A，还有low,high,mid,x,j五个变量需要存储，共需空间n+5计算时间对于计算时间，需要分别考虑以下几种情况：成功检索的最好情况和不成功检索的最好情况成功检索的平均情况和不成功检索的平均情况成功检索的最坏情况和不成功检索的最坏情况,成功检索最好情况和不成功检索最好情况,成功的检索共有n种不成功的检索共有n+1种,二元比较树,5,7,2,1,3,4,6,8,9,内结点,表示一次元素的比较,存放已个mid值,外结点
6、,表示不成功检索的一种情况,9,-6,-15,0,54,7,23,82,101,二分检索的时间复杂度,定理2.2：若n在区域2k-1,2k)中，则对于一次成功的检索，二分检索至多作k次比较，至少作1次比较；而对于一次不成功的检索，或者作k-1次比较或者作k次比较。,证明 考察以n个结点描述BINSRCH执行过程的二元比较树，所有成功检索都在内部结点处结束，而所有不成功检索都在外部结点处结束。由于n在区域2k-1,2k)中，因此，所有的内部结点在1，2，k级，而所有的外部结点在k和k+1级（根在1级）。就是说，成功检索在i级终止所需要的元素比较数是i，而不成功检索在i级外部结点终止的元素比较数是
7、i-1。,二分检索的时间复杂度,最坏情况下的成功检索计算时间(logn)最坏情况下的不成功检索计算时间(logn)最好情况下的成功检索计算时间(1)最好情况下的不成功检索计算时间(logn)每种不成功的检索时间都为(logn),成功检索的平均比较次数,由根到所有内部结点的距离之和称为内部路径长度I;由根到所有外部结点的距离之和称为外部路径长度E;E=I+2n令S(n)是成功检索的平均比较次数。找一个内部结点表示的元素所需的比较次数是由根到该结点的路径长度（即距离）加1。因此，S(n)=I/n+1到一个外部结点所需要的比较数是由根到该结点路径的长度。因此，U(n)=E/(n+1)由以上各公式可得
8、 S(n)=(1+1/n)U(n)-1由于U(n)=(logn)，所以成功检索的计算时间S(n)也为(logn),二分检索在各种情况下的检索时间,以比较为基础检索的时间下界,有n个如下关系的元素:A(1)A(2)A(n),检索一给定元素X是否在A中出现,二分检索,以比较为基础检索的时间下界,定理2.3：设A(1:n)含有n(n1)个不同的元素，排序为A(1)A(2)A(n)。又设以比较为基础去判断是否xA(1:n)的任何算法在最坏情况下所需的最小比较次数是FIND(n)，那么FIND(n)log(n+1)证明 若一棵二元树的所有内部结点所在的级数小于或等于级数k，则最多有2k-1个内结点。因此
9、，n 2k-1,即FIND(n)=k log(n+1)。定理表明，任何一种以比较为基础的算法，其最坏情况时间都不可能低于O(logn)，也就是不可能存在其最坏情况时间比二分检索数量级还低的算法。,2.3 找最大和最小元素,问题描述：在含有n个不同元素的集合中同时找出它的最大和最小元素一般解决方法,Procedure STRAITMAXMIN(A,n,max,min)integer i,n;maxminA(1)for i2 to n do if Aimax then maxAi endif if Aimin then minAi endif End STRAITMAXMIN,If Aimax t
10、hen maxAiElse if(Aimin then minAi endifendif,算法的时间复杂度,改进前：2(n-1)改进后：最好n-1，最坏2(n-1)，平均3(n-1)/2可考虑用分治策略来解决这个问题将任一实例I=(n,A(1),A(n)分成一些较小的实例来处理。,递归求取最大和最小元素,Procedure MAXMIN(i,j,fmax,fmin)integer i,j;global n,A(1:n)case:i=j:fmaxfminA(i):i=j-1:if A(i)A(j)then fmaxA(j);fminA(i)else fmaxA(i);fminA(j)endif:
11、else:mid(i+j)/2 call MAXMIN(i,mid,gmax,gmin)call MAXMIN(mid+1,j,hmax,hmin)fmaxmax(gmax,hmax)fminmin(gmin,hmin)endcaseEnd MAXMIN,只有一个或两个元素时,递归调用部分,求解答案的部分,过程MAXMIN模拟,1,9,22,13,-5,-5,22,-5,15,-8,22,-8,60,-8,60,17,60,17,47,31,一次递归调用,过程MAXMIN的时间复杂度,MAXMIN的元素比较次数T(n)=,0 n=1,1 n=2,2T(n/2)+2 n2,当n=2k(k是某个正
12、整数)时，有T(n)=3n/2-2,与直接算法的比较次数2(n-1)相比，比较次数减少了25%。,MAXMIN算法分析,由于递归的调用，MAXMIN所需要的存储空间较多，递归调用也消耗了部分时间。元素A(i)和A(j)的比较与i和j的比较时间相差不大时，过程MAXMIN不可取。如果设过程MAXMIN的频率计数为C(n)，n=2k，k是一个整数，并用i=j-1来代替i=j和i=j-1，有：,当n2时，C(n)=2C(n/2)+3=4C(n/4)+6+3=2k-1C(2)+3(1+2+22+2i+2k-2)=2k+3*2k-1-3=5n/2-3 当n较大时，比较次数会远远大于直接比较算法,结论：如
13、果数组A的元素间的比较远比整型变量的比较代价昂贵，则分治法产生效率较高的算法；反之，就得到一个效率较低的程序。,2.4 归并分类（排序）,问题描述 给定一个含有n个元素(或叫关键字)的集合，把它们按一定的次序分类(如非降次序排序)一般方法(插入法)For j2 to n do 将A(j)放到已分类集合A(1:j-1)的正确位置上Repeat,插入分类算法描述,Procedure INSERTIONSORT(A,n)A(0)-for j2 to n do itemA(j);ij-1 while itemA(i)do A(i+1)A(i);ii-1 repeat A(i+1)item repeat
14、End INSERTIONSORT,数组元素的移动,插入排好序的值,可能执行0j 次(j=2,3n)最坏情况的计算时间：2+n=(n(n+1)/2)-1=(n2)，最好情况(n),分治策略设计分类算法,I=(n,A(1),A(n),Procedure MERGESORT(low,high)interger low,high if lowhigh then mid(low+high)/2 call MERGESORT(low,mid)call MERGESORT(mid+1,high)call MERGE(low,mid,high)endifEnd MERGESORT,递归调用，分别对分解出来的
15、两个子问题分类,合并两个已分好类的序列，得到原问题的解,分治策略设计分类算法,合并函数MERGE的实现,数组A,已分类序列A,已分类序列B,辅助数组B,A(1),A(n/2+1),数组A,合并函数MERGE的实现思想,合并函数MERGE的算法描述,Procedure MERGE(low,mid,high)integer h,i,j,k,low,mid,high;global A(low:high);local B(low:high)hlow;ilow;jmid+1;while hmid and jhigh do if A(h)A(j)then B(i)A(h);hh+1 else B(i)A(
16、j);jj+1 endif ii+1 repeat if hmid then for kj to high do B(i)A(k);ii+1 repeat else for kh to mid do B(i)A(k);i i+1 repeat end if for klow to high do A(k)B(k)repeatEnd MERGE,处理两个已分类的序列,剩余元素的处理过程,将已分类的集合复制到A数组,归并分类算法实例,310 285 179 652 351 423 861 254 450 520,归并分类算法实例,179 254 285 310 351 423 450 520 65
17、2 861,MERGESORT调用树,1,10,6,10,1,5,1,3,4,5,6,8,9,10,8,8,9,9,10,10,5,5,4,4,3,3,1,2,6,7,1,1,2,2,7,7,6,6,表示一次调用时的low和high的值,只含单个元素的子集合,将问题不断分解成规模较小的子问题，使之更容易解决。,MERGE调用树,1，1，2,4，4，5,6，6，7,1，2，3,9，9，10,6，7，8,6，8，10,1，3，5,1，5，10,表示一次MERGE调用时的low,mid,high值,表示A(1:3)和A(4:5)中的元素归并,将处理好的子问题不断的合并，最终获得原问题的结果,归并分类
18、的计算时间,T(n)=,a n=1,a是常数,2T(n/2)+cn n1,c是常数,当n=2k时，可得T(n)=2(2T(n/4)+cn/2)+cn=22T(n/4)+2cn=4(2T(n/8)+cn/4)+2cn=23T(n/8)+3cn=2kT(1)+kcn=an+cnlogn如果2kn2k+1，有T(n)T(2k+1)，有T(n)=O(nlogn),改进的分类归并算法,procedure MERGESORT1(low,high,p)/利用辅助数组LINK(low:high)将全程数组A(low:high)按非降次序分类。LINK中值表示按分类次序给出A下标的表，并把p置于指示这表的开始处
19、/global A(low:high),LINK(low:high)if high-low+116then call INSERTIONSORT(A,LINK,low,high,p)else mid-(low+high)/2 call MERGESORT1(low,mid,q)call MERGESORT1(mid+1,high,r)call MERGE1(q,r,p)endifend MERGESORT1,任何以关键字比较为基础的分类算法，最坏情况下的时间下界都是(nlogn)，因此，从数量级的角度上来看，归并算法是最坏情况下的最优算法。下面用二元比较树给出以比较为基础的分类算法时间下界的证
20、明。,以比较为基础分类的时间下界,关键字分类的二元比较树,1:2,1:3,1:3,2:3,2:3,1,2,3,1,3,2,3,1,2,2,1,3,2,3,1,3,2,1,A(1)A(2),A(1)A(2),A(2)A(3),A(2A(3),A(1)A(3),A(1)A(3),A(2)A(3),A(2)A(3),A(1)A(3),A(1)A(3),表示一次比较,一种可能的分类序列,以比较为基础分类的时间下界,由于n个关键字有n!种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有n!个外结点，每个外结点表示一种可能的分类序列。对于任何一个以比较为基础的算法，在描述其执行的那棵比
21、较树中，由根到某外结点的路径长度表示生成该外结点中那个分类序列所需要的比较次数。从而，要求出所有以比较为基础的对n个关键字分类的算法最坏情况下界，只需求出这些算法对应的比较树的最小高度。据二元树的性质可知，如果一棵二元树的所有内结点的级数均小于或等于k，则该树至多有2k个外结点（比内结点数多1）。令T(n)=k，则n!1时有n!=n(n-1)(n/2)=(n/2)n/2因此，对于n=4有 T(n)=(n/2)log(n/2)=(n/4)logn。故以比较为基础的分类算法的最坏情况的时间下界为(nlogn),2.5快速分类（排序）,Procedure QUICKSORT(p,q)integer
22、p,q;global n,A(1:n)if pq then j=q+1 call PARTITION(p,j)call QUICKSORT(p,j-1)call QUICKSORT(j+1,q)endifEnd QUICKSORT,PARTITION算法,Procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1);V=A(m);i=m;Loop loop i=i+1 until A(i)=v repeat loop p=p-1 until A(p)=v repeat if ip then call INTERCHANGE(A(i),A(p)els
23、e exitRepeatA(m)=A(p);A(p)=vEnd PARTITION,PARTITION算法实例,(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)i p,65 45 50 55 60 85 80 75 70+6 5,65 45 75 80 85 60 55 50 70+3 8,65 45 50 80 85 60 55 75 70+4 7,65 45 50 55 85 60 80 75 70+5 6,65 70 75 80 85 60 55 50 45+2 9,60 45 50 55 65 85 80 75 70+,QUICKSORT算法分析,假设参加分类的n个元素各
24、不相同;PARTITION中的划分元v是随机选取的.要分析QUICKSORT,只需计算出它的元素比较次数C(n)即可.令C(n)在最坏情况下的值为CW(n),易知CW(n)=O(n2)令C(n)在平均情况下的值为CA(n),则CA(n)=n+1+1/ni k n(CA(k-1)+CA(n-k)CA(n)2(n+1)loge(n+1)=O(nlogn),QUICKSORT算法分析,最坏情况：O(n2)平均情况：O(nlogn),2.6 选择问题,2.6.1 选择问题算法(找第K小元素)Procedure SELECT(A,n,k)integer n,k,m,r,j;m=1;r=n+1;A(n+1
25、)=+;Loop j=r;call PARTITION(m,j)case:k=j:return:kj:r=j:else:m=j+1 endcaseEnd SELECT,最坏情况：O(n2)平均情况：O(n),2.6选择问题（续）,最坏情况时间是O(n)的选择算法采用二次取中值规则选取划分元素,二次取中值规则选取划分元素,例：设 n=35,r=7。分为n/r=5个元素组：B1，B2，B3，B4，B5；每组有7个元素。B1-B5按照各组的mi的非增次序排列。mm 为各 mi的中间值，1i5。,二次取中值规则选取划分元素,由于r个元素的中间值是第 小元素。则，至少有 个mi小于或等于mm；至少有 个
26、mi大于或等于mm。则，至少有 个元素小于或等于（或大于或等于）mm。当r=5，则使用两次取中间值规则来选择v=mm，可推出，至少有 个元素小于或等于选择元素v。至多有 个元素大于v。至多有 0.7n+1.2个元素小于v。故，这样的v可近似平均地划分A中的n个元素。,使用二次取中规则的选择算法,Procedure SELECT2(A,k,n)1 若n=r，则采用插入法直接对A分类并返回第K小元素。2 把A分成大小为r的n/r个子集合，忽略剩余的元素。3 设mm1,m2,mn/r是上面n/r个子集合的中间值的集合4 v=SELECT2(m,n/r/2,n/r)5 用PARTITION划分A，v作
27、为划分元素。6 假设v在位置j。7 case:k=j:return(v):kj:设S是A(1:j-1)中元素的集合，return(SELECT2(S,k,j-1):else:设R是A(j+1,n)中元素的集合，return(SELECT2(R,k-j,n-j)endcaseEnd SELECT2,SELECT2算法的分析(一),首先考虑r=5且A中各元素互不相同的情况设总的时间为T(n)Step1:O(1)Step3:每个mi为O(1),故总的为O(n)Step2,5,6:O(n)Step4:T(n/r)(由于r=5,所以T(n/r)=T(n/5)Step7:T(3n/4)当n=24时由此得：
28、T(n)=1时 T(n)=20cn故：最坏情况时间是O(n),SELECT2算法的分析(二),二次取中值法中，小于或等于v的元素个数至少为r/21/2n/r，故大于或等于v 的元素至多为n-r/21/2n/r。（注：为上取整）。Step7:r=5时，5/21/2n/531/2(n/5)=3n/10，则n-3n/10=7n/10由此，T(n)=T(n/5)+T(7n/10)+O(n)故r=5时，算法在最坏情况下可以用O(n)的时间执行完毕。,SELECT2算法的分析(二),T(n)=T(n/5)+T(7n/10)+O(n)用替换法:猜测T(n)=O(n)，则T(n)dn。T(n)=T(n/5)+
29、T(7n/10)+O(n)d*n/5+d*7n/10+cn=9/10*dn+cn dn(当d10c时成立)故T(n)=O(n),SELECT2算法的分析(续),其次考虑A中元素不是完全不同的情况在这种情况下，当在step5调用PARTITION时，由于所产生的S和R这两种集合中可能有一些等于v的元素。处理此问题的一种方法是把A分成三个集合U，S和R，使U由所有与v相同的元素组成，S是A中所有比v小的元素的集合，A中所有比v大的元素组成R。于是将Step7修改成：Case:|S|=k:return(SELECT2(S,k,|S|):|S|+|U|=k:return(v):else:return(
30、SELECT2(R,k-|S|-|U|,|R|)Endcase修改后的SELECT2 的时间复杂度仍是O(n),SELECT2的SPARKS的描述算法,procedure SEL(A,m,p,k)/返回一个i，使得im,p，且A(i)是A(m:p)中第k小元素，r是一个全程变量，其取值为大于1的整数 global r;integer n,i,j if p-m+1r then call INSERTIONSORT(A,m,p);return(m+k-1);endif loop np-m+1/元素数/for i1 to n/r do/计算中间值/call INSERTIONSORT(A,m+(i-
31、1)*r,m+i*r-1)/将中间值收集到A(m:p)的前部/call INTERCHANGE(A(m+i-1),A(m+(i-1)r+r/2-1)repeat jSEL(A,m,m+n/r-1,n/r/2)/mm/call INTERCHANGE(A(m),A(j)/产生划分元素/jp+1 call PARTITION(m,j)case:j-m+1=k:return(j):j-m+1k:pj-1:else:kk-(j-m+1);mj+1 endcase repeat end SEL,2.7斯特拉森矩阵乘法,令A和B为nn的矩阵，则：由矩阵加定义直接产生的矩阵加算法的时间为O(n2)由矩阵乘定
32、义直接产生的矩阵乘算法的时间为O(n3),用分治法解决矩阵相乘,令n=2k，按照分治法，可将A和B都分成四个(n/2)(n/2)矩阵，可得：A11 A12 B11 B12 C11 C12 A21 A22 B21 B22 C21 C22其中：C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22,分治算法的时间T(n),b n2 求解这个递归式得T(n)=O(n3)，与通常的矩阵算法计算时间具有相同的数量级。,Strassen矩阵乘法,P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A
33、11(B12-B22)S=A22(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22),C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+U,以上共用了7次乘法和18次加（减）法。,Strassen矩阵乘法分析,T(n)所得出的递归关系式是：b n2求解这个递归关系式，得T(n)O(n2.81),矩阵乘法的时间复杂性,有人曾列举了计算2个2阶矩阵乘法的36种不同方法。但所有的方法都要做7次乘法。除非能找到一种计算2阶方阵乘积的算法，使乘法的计算次数少于7次，按上述思路才有可能进一步改进矩阵乘积的计算时间
34、的上界。但是Hopcroft 和 Kerr(197l)已经证明，计算2个22矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再寄希望于计算22矩阵的乘法次数的减少。或许应当研究33或55矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是O(n2.367)。而目前所知道的矩阵乘法的最好下界仍是它的平凡下界(n2)。,课后思考题,给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法，并计算其时间复杂度。,
