《分治策略》PPT课件

2020/5/14,1,第4讲分治策略,2020/5/14,2,主要内容,分治法基本思想二分搜索算法合并排序算法快速排序算法线性时间选择,2020/5/14,3,4.1分治法的基本思想,例:找伪币问题给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。,2020/5/14,4,一种方式两两对比，找到轻者，最差比较8次另外一种1)将16个硬币分成A、B两半；2)将A放仪器的一边，B放另一边，如果A袋轻，则表明伪币在A，解子问题A即可，否则，解子问题B。,2020/5/14,5,例25金块问题,有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。,2020/5/14,6,假设袋中有n个金块。通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。n2时，识别出最重和最轻的金块，做一次比较。n2时，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。HA与LA，HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。,2020/5/14,7,复杂度,设c(n)为比较次数。假设n是2的幂。当n=2时，c(n)=1；当n2时，c(n)=2c(n/2)+2。当n是2的幂时，可知c(n)=3n/2-2。使用分而治之方法比逐个比较的方法少用了25的比较次数。,2020/5/14,8,4.1分治法的基本思想,分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：把它分成两个或多个更小的问题；分别解决每个小问题；把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,2020/5/14,9,原问题,子问题1,子问题2,子问题k,子问题1,子问题2,子问题3,相同类型,不可再分，直接求解,2020/5/14,10,分治法流程,用P表示问题的输入。Divide-and-Conquer(P)if(|P|=n0)Adhoc(P);dividePintosmallersubinstancesP1,P2,Pk;for(i=1;i1解上式得到,2020/5/14,14,4.2二分搜索技术,给定已排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x，找到则将其位置赋于变量j中，否则j置-1。,如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。,问题提出,2020/5/14,15,1线性搜索,线性搜索二元比较树如下：,任何以比较为基础的搜索算法的执行过程都可以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点与之对应。,An-1xAn,2020/5/14,16,线性算法复杂度,该方法没有很好利用已经排好序这个条件，顺序搜索方法平均需要O(n)次比较。,2020/5/14,17,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),ak,2020/5/14,18,二元比较树,含9个元素的情况,2020/5/14,19,二元比较树,2020/5/14,20,例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,2020/5/14,21,templateintBinarySearch(Ta,constT/未找到x,n-1,0,left=right,(left+right)/2,middle+1,middle1,2020/5/14,22,例:-15,-6,0,7,9,23,54,82,101中查找101，-14，82,X=101Lowhighmid084586787888OK,X=-14Lowhighmid0840310000NO,X=82Lowhighmid084586787OK,2020/5/14,23,二分搜索所需的空间和时间,所需空间存放数组a的地址，还有left，right，middle，及x的地址需要存储，共10字节计算时间成功检索的最好情况和不成功检索的最好情况成功检索的平均情况和不成功检索的平均情况成功检索的最坏情况和不成功检索的最坏情况,2020/5/14,24,成功检索最好情况和不成功检索最好情况,成功检索共有n种不成功检索共有n+1种,2020/5/14,25,由图可见，当x在数组A中时，算法在圆形顶点结束；不在A中时，算法在方形顶点结束。因为23924，所以比较树的叶顶点都在4或5级上出现。因而元素比较的最多次数为4。一般地有：当时，一次成功的折半搜索至多做k次比较，而一次不成功的折半搜索或者做k-1次比较，或者做k次比较。,2020/5/14,26,二分搜索的时间复杂度,