第2章分治策略.ppt

syzhanglily,第2章递归与分治策略,syzhanglily,本章主要内容,递归分治法基本思想二分搜索算法合并排序快速排序,syzhanglily,2.1分治法的基本思想,例:找伪币问题给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。,syzhanglily,一种方式两两对比，找到轻者，最差比较8次另外一种1)将16个硬币分成A、B两半；2)将A放仪器的一边，B放另一边，如果A袋轻，则表明伪币在A，解子问题A即可，否则，解子问题B。,2.1分治法基本思想,syzhanglily,例25金块问题,有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。,2.1分治法基本思想,syzhanglily,假设袋中有n个金块。通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。n2时，识别出最重和最轻的金块，做一次比较。n2时，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。HA与LA，HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。,2.1分治法基本思想,syzhanglily,复杂度,设c(n)为比较次数。假设n是2的幂。当n=2时，c(n)=1；当n2时，c(n)=2c(n/2)+2。当n是2的幂时，可知c(n)=3n/2-2。使用分而治之方法比逐个比较的方法少用了25的比较次数。,2.1分治法基本思想,syzhanglily,2.1分治法的基本思想,分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：把它分成两个或多个更小的问题；分别解决每个小问题；把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,2.1分治法基本思想,syzhanglily,原问题,子问题1,子问题2,子问题k,子问题1,子问题2,子问题3,相同类型,不可再分，直接求解,2.1分治法基本思想,syzhanglily,分治法流程,用P表示问题的输入。Divide-and-Conquer(P)if(|P|=n0)Adhoc(P);dividePintosmallersubinstancesP1,P2,Pk;for(i=1;i=k;i+)yi=Divide-and-Conquer(Pi);returnMerge(y1,yk);,2.1分治法基本思想,判断输入规模p是否足够的小,解该规模问题的函数,分割函数,分治解决,合并得到最后结果,syzhanglily,2.2二分搜索技术,给定已排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x，找到则将其位置赋于变量j中，否则j置-1。,如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。,问题提出,syzhanglily,1线性搜索,线性搜索二元比较树如下：,2.1二分搜索技术,任何以比较为基础的搜索算法的执行过程都可以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点与之对应。,An-1xAn,syzhanglily,线性算法复杂度,该方法没有很好利用已经排好序这个条件，顺序搜索方法平均需要O(n)次比较。,2.2二分搜索技术,syzhanglily,2二分搜索方法,基本思想取一个中间元素做比较元素，如果x等于它，则结束，如果小于，去左半部查找，否则去右半部搜索将问题表示为：I=(n,a1,an,x)选取一个下标k，可得到三个子问题：I1=(k-1,a1,ak-1,x)I2=(1,ak,x)I3=(n-k,ak+1,an,x),2.2二分搜索技术,ak,syzhanglily,二元比较树,含9个元素的情况,2.2二分搜索技术,syzhanglily,例2-6在9,12,15,27,39中分别查找27，12，14,mid=(left+right)/2=(0+4)/2=2,mid=(3+4)/2=3,mid,查找27成功返回3，leftright,syzhanglily,templateintBinarySearch(Ta,constT/未找到x,2.2二分搜索技术,n-1,0,left=right,(left+right)/2,middle+1,middle1,syzhanglily,二分搜索所需的空间和时间,所需空间存放数组a的地址，还有left，right，middle，及x的地址需要存储，共10字节计算时间成功检索的最好情况和不成功检索的最好情况成功检索的平均情况和不成功检索的平均情况成功检索的最坏情况和不成功检索的最坏情况,2.2二分搜索技术,syzhanglily,成功检索最好情况和不成功检索最好情况,成功检索共有n种不成功检索共有n+1种,2.2二分搜索技术,syzhanglily,由图可见，当x在数组A中时，算法在圆形顶点结束；不在A中时，算法在方形顶点结束。因为2391时，Tw(n)=Tw(n/2)+1,T(1)=1Tw(n)=Tw(n/2)+1=Tw(n/4)+1+1=Tw(1)+1+.+1=1+k=1+logn,syzhanglily,二分搜索的时间复杂度,最坏情况下的成功检索计算时间(logn)最坏情况下的不成功检索计算时间(logn)最好情况下的成功检索计算时间(1)最好情况下的不成功检索计算时间(logn)每种不成功的检索时间都为(logn),2.2二分搜索技术,syzhanglily,二分检索在各种情况下的检索时间,2.2二分搜索技术,syzhanglily,一般方法(插入法),templateINSERTIONSORT(TypeA,intn)Typeitem;inti;for(intj=1;j-1)doAi+1=Ai;i=i-1;Ai+1=item;,数组元素的移动,插入排好序的值,可能执行0j次(j=1,2n-1)最坏情况的计算时间：2+n=(n(n+1)/2)-1=(n2)，最好情况(n),2.4合并排序,syzhanglily,一般方法(插入法)计算时间,插入算法的while循环中的语句可能执行0j次(j=1,2n-1)。所以，最坏情况的计算时间为：2+n=(n(n+1)/2)-1=(n2)。如果输入数据本来就是按非降次序排列的，则根本不会进入while循环，这就是最好情况，计算时间是(n)。,syzhanglily,分治策略求解,若n为1，算法终止；否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序。然后将排好序的子集合归并为一个集合。,性能最佳的方式就是分成两个元素个数相近的集合，这就是2路归并,2.4合并排序,syzhanglily,归并排序过程,VoidMergeSort(typea,intleft,intright)ifleftright/至少有两个元素找到数组的中间元素下标mid递归调用算法本身对从left到mid的数组元素排序递归调用算法本身对从mid到right的数组元素排序合并两段排好序的数组,2.4合并排序,syzhanglily,归并排序主程序伪代码,templatevoidMergeSort(Typea,intleft,intright)/Aleft:right是一个全程数组，含有right-left+1个待排序的元素。if()/至少有2个元素intmid=(left+right)/2;/求当前数组的分割点MergeSort(a，left,mid);MergeSort(a，mid+1,right);Merge(a，b，left,mid,right);copy（a，b，left，right）；排序树,leftright,递归调用，分别对分解出来的两个子问题排序,合并两个排好序的子问题，放入另一个数组b中,2.4合并排序,syzhanglily,合并过程Merge(a,b,left,mid,right),前提是待合并的两段数据已经排好序,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,数组a的两部分,数组b,1,2,3,4,5,6,2,4,5,8,1,3,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,8,2.4合并排序,syzhanglily,考虑数组a的两段为1,7,8,9和2,3,4,5,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,数组a的两部分,数组b,1,2,3,4,5,7,1,2,3,4,5,7,8,1,2,3,4,5,7,8,9,在移动扫描指针的同时，要判断其是否已经到达数组的尾部，如到达，则停止扫描，把未参加排序的数全部放入备用数组中,2.4合并排序,syzhanglily,合并函数MERGE的实现,数组A,已分类序列A,已分类序列B,辅助数组B,A(0),A(n-1)/2+1),考虑函数需要的参数原数组a目标数组ba前段的起始位置la前段的终止位置m，则后段起始位置为m+1a后段的终止位置r,2.4合并排序,syzhanglily,合并函数,templatevoidMerge(Typea,Typeb,intl,intm,intr)/合并al:m和am+1:r到bl:rinti=l;j=m+1,k=l;while(),把al:m和am+1:r中的数据进行比较，按顺序放入b中,如果前一段数据小于后一段的多，则先排完，把后段剩余数付给bn,否则将前段数据付给bn,前半段指针,后半段指针,数组b的下标指针,i=m,j=r,2.4合并排序,syzhanglily,归并分类算法实例,310285179652351423861254450520,2.4合并排序,syzhanglily,归并分类算法实例,179254285310351423450520652861,2.4合并排序,syzhanglily,MERGESORT调用树,0,9,5,9,0,4,0,2,3,4,5,7,8,9,7,7,8,8,9,9,4,4,3,3,2,2,0,1,5,6,0,0,1,1,6,6,5,5,表示一次调用时的low和high的值,只含单个元素的子集合,2.4合并排序,syzhanglily,MERGE调用树,0，0，1,3，3，4,5，5，6,0，1，2,8，8，9,5，6，7,5，7，9,0，2，4,0，4，9,表示一次MERGE调用时的low,mid,high值,表示A(0:2)和A(3:4)中的元素归并,2.4合并排序,syzhanglily,算法分析,如果用T(n)表示归并排序所用的时间，Merge和Copy所用时间可在O(n)时间内完成，即与n成正比：cn，其中c是一个正数，则有,2.4合并排序,syzhanglily,其中，是一个常数。若n是2的方幂：直接推导可得,2.4合并排序,syzhanglily,由于排序问题的计算时间下界为所以归并排序算法是渐进最优算法,2.4合并排序,syzhanglily,缺点:,该算法需要线形的额外空间,虽然合并也能做到”在位”,但会导致算法过于复杂,而且，因为它的增长次数具有一个很大的常系数,所以在位的合并排序算法只有理论上的意义,2.4合并排序,syzhanglily,消除递归的归并排序,2.4合并排序,syzhanglily,排序20,25,50,25*,90,60,70,10,30,15,55,待合并长度s为1,S为2,S为4,10202525*50607090153055,S为8,1020152525*305055607090,考虑以下问题：待合并长度如何变化每趟合并停止的条件图中紫色元素有何特别，分几种情况，都如何处理,合并长度每次翻倍,当剩余元素个数小于等于s时，直接放入下次排序。当其大于s小于2s时，合并,当剩余待合并元素2s时不在合并，而需要单独处理剩下的元素,55,153055,153055,153055,syzhanglily,消去递归的合并描述,2.4合并排序,输入:待排序数组a，数组长度n输出:排好序的数组as=1/s为记录每次合并的数组长度while(sn)两两合并a中排好序的长度为s的数组段并处理不能参加合并的元素；s+=s,输入:待排序数组x，存储结果数组y,子数组的长度s，x的长度输出:数组yi0/i为记合并数组的起点位置while()找到要合并的两段数组的起止位置分别为,i,i+s-1,i+s,i+2s-1；调用merge函数排序两段数组ii2s/待合并数组段起始位置改变；/处理剩下的小于2s的元素if(i+sn)合并i,i+s-1,i+s,n-1的数组/剩下的元素大于s小于2selse将未参加合并的元素直接赋给y,i=n-2*s,syzhanglily,2.4合并排序,templatevoidMergeSort(Typea,intn)type*b=newTypen;ints=1;while(sn)MergePass(a,b,s,n);s+=s;MergePass(b,a,s,n);s+=s;,templatevoidMergePass(Typex,Typey,ints,intn)/合并大小为s的相邻子数组inti=0;while(i=n-2*s)Merge(x,y,I,i+s-1,i+2*s-1);i=i+2*s;/剩下的元素个数大于s，而小于2s时if(i+sn)Merge(x,y,I,i+s-1,n-1);/剩下的元素个数不到s个时elsefor(intj=i;j=n-1;j+)yj=xj;,syzhanglily,合并函数,TemplatevoidMerge(Typec,Typed,intl,intm,intr)/合并cl:m和cm+1:r到dl:rinti=l;j=m+1,k=l;while(im)for(intq=j;q=r;q+)dk+=cq;elsefor(intq=I;q=m;q+)dk+=cq;,把cl:m和cm+1:r中的数据进行比较，按顺序放入dn中,如果前一段数据小于后一段的多，则先排完，把后段剩余数付给dn,否则将前段数据付给dn,2.4合并排序,syzhanglily,该归并排序的缺点,归并排序有两个地方值得商榷：一是分解直到只有一个元素。事实上，当元素比较少时，直接进行排序，比如用插入排序算法，比起进一步分拆、合并排序要快得多。因为，在这种情况下，大量的时间都花在调用分解、合并函数上。所以，在归并排序算法中，对于归并起点的规模应该有适当的限制，即加Small(p,q)判断。二是辅助数组B的借用，虽然不可避免，但可以采用另一种方式，以避免数组A中的元素的频繁换位。,2.4合并排序,syzhanglily,作业,应用合并排序对序列E,X,A,M,P,L,E按照字母顺序排序，写出排序的过程分析merge函数最好与最坏的键值比较次数。,syzhanglily,2.5快速排序问题,由著名计算机科学家霍尔(C.A.R.Hoare)给出。把原序列分成两个子问题，在被分成的两个子问题以后不再需要归并。被分成的两个子问题必须满足一子问题中的所有元素都小于或等于另一子问题的任何一个元素。,syzhanglily,2.5快速排序问题,基本策略是：,将数组A1:n分解成两个子数组B1:p和Bp+1:n，使得B1:p中的元素均不大于Bp+1:n中的元素，然后分别对这里两个数组中的元素进行排序（非降的），最后再把两个排好序的数组接起来即可。,syzhanglily,选取A的某个元素t=A(s)，然后将其他元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。,划分元素,每个元素都小于或等于t,每个元素都大于或等于t,快速排序问题,syzhanglily,算法步骤,分解(Divide):以ap为基准元素将ap:r划分成3段ap:q-1,aq和aq+1:r,使得ap:q-1中任何一个小于等于aq,下标q在划分过程中确定。递归求解(conquer):通过递归调用快速排序算法分别对ap:q-1和aq+1:r进行排序。合并(Merge):由于对ap:q-1和aq+1:r的排序是就地进行的，所以在ap:q-1和aq+1:r都已排好的序后步需执行任何计算ap:r就已排好序。,快速排序问题,syzhanglily,快速排序,TemplatevoidQuickSort(Typea,intp,intr)if(p=j,aj,x,左侧扫描指针起始,右侧扫描指针起始,中轴元素,移动左侧扫描指针,移动右侧扫描指针,syzhanglily,快速排序问题,例：排列5，3，1，9，8，2，4，7,01234567,ij53198247,ij53198247,ij531482