资源描述：
《《分治策略》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4讲分治策略7/20/20211主要内容分治法基本思想二分搜索算法合并排序算法快速排序算法线性时间选择7/20/202124.1分治法的基本思想例:[找伪币问题]给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。7/20/20213一种方式两两对比，找到轻者，最差比较8次另外一种1)将16个硬币分成A、B两半；2)将A放仪器的一边，B放另一边，如果A袋轻，则表明伪币在A，解子问题
2、A即可，否则，解子问题B。7/20/20214例2－5金块问题有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。7/20/20215假设袋中有n个金块。通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中
3、用类似的方法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。n≤2时，识别出最重和最轻的金块，做一次比较。n＞2时，第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。HA与LA，HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB，可以找到所有金块中最轻的。7/20/20216复杂度设c(n)为比较次数。假设n是2的幂。当n=2时，c(n)=1；当n>2时，c(n)=2c(n/2)+2。当n是2的幂时，可知c(n)=3n/2-2。使用分而治之方法比逐个比较的方法少用了25％的比较次数。
4、7/20/202174.1分治法的基本思想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：把它分成两个或多个更小的问题；分别解决每个小问题；把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。7/20/20218原问题子问题1子问题2子问题k子问题1‘子问题2’子问题3‘相同类型不可再分，直接求解7/20/20219分治法流程用P表示问题的输入。Divide-and-Conquer(P){if(
5、P
6、<=n0)Adhoc(P);dividePintosmallersubinstances
7、P1,P2,···,Pk;for(i=1;i<=k;i++)yi=Divide-and-Conquer(Pi);returnMerge(y1,···,yk);}判断输入规模p是否足够的小解该规模问题的函数分割函数分治解决合并得到最后结果7/20/202110问题应把原问题分为多少个子问题才较适宜？每个子问题是否规模相同或怎样才为适当？7/20/202111分治法计算效率原问题规模——n分成k个子问题，每个规模——n/m设分解阈值n0＝1，Adhoc解规模为1的问题耗费1个单位时间设分解原问题及用Merge将k个子问题的解合并需要f(n)个单位时间T(n)表示分治法
8、的解规模为
9、P
10、=n的问题所需的计算时间7/20/202112计算时间分析由上可得O(1)n=1T(n)=kT(n/m)+f(n)n>1解上式得到7/20/2021134.2二分搜索技术给定已排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，找到则将其位置赋于变量j中，否则j置-1。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。问题提出7/20/2021141线性搜索线性搜索二元比较树如下：x:A[2]x:A[n]不成功不成功不成功x:A[1]不成功任何以比较为基础的搜索算法的执行过程都可以用一棵
11、二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点与之对应。A[n-1]A[n]7/20/202115线性算法复杂度该方法没有很好利用已经排好序这个条件，顺序搜索方法平均需要O(n)次比较。7/20/2021162二分搜索方法基本思想取一个中间元素做比较元素，如果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)a[k]7/20/2
12、02117
