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