第四讲分治策略

1、第4讲 分治策略7/23/20221主要内容分治法基本思想二分搜索算法合并排序算法快速排序算法线性时间选择7/23/202224.1 分治法的基本思想例:找伪币问题给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。7/23/20223一种方式 两两对比，找到轻者，最差比较8次另外一种1)将16个硬币分成A、B两半；2)将A放仪器的一边，B放另一边，如果A袋轻，则表明伪币在A，解子问题A即可，否则，解子问题B

2、。7/23/20224例25 金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩，排名第一的雇员将得到袋中最重的金块，排名第二的雇员将得到袋中最轻的金块。根据这种方式，除非有新的金块加入袋中，否则第一名雇员所得到的金块总是比第二名雇员所得到的金块重。如果有新的金块周期性的加入袋中，则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最轻和最重的金块。7/23/20225假设袋中有n 个金块。通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似的方法通过n-2次比较找出最轻的金块。这样，

3、比较的总次数为2n-3。n2时，识别出最重和最轻的金块，做一次比较。 n2时， 第一步，把这袋金块平分成两个小袋A和B。 第二步，分别找出在A和B中最重和最轻的金块。HA 与LA，HB 和LB。 第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。7/23/20226复杂度设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的比较次数。7/23/202274.1 分治法的基本思

4、想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 把它分成两个或多个更小的问题； 分别解决每个小问题； 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。7/23/20228原问题子问题1子问题2子问题k子问题1子问题2子问题3相同类型不可再分，直接求解7/23/20229分治法流程用P表示问题的输入。Divide-and-Conquer(P) if (|P|=n0) Adhoc(P); divide P into smaller subinstances P1,P2,Pk; for(i=1;i1解上式得到7/2

5、3/2022134.2 二分搜索技术 给定已排好序的n个元素a0:n-1，现要在这n个 元素中找出一特定元素x，找到则将其位置赋于变 量j中，否则j置-1。如果只允许进行元素间的比较而不允许对它们进行其它的运算，则所设计的算法称为以比较为基础的算法。问题提出7/23/2022141 线性搜索 线性搜索二元比较树如下： x:A2x:An不成功不成功不成功x:A1不成功任何以比较为基础的搜索算法的执行过程都可以用一棵二元比较树来描述。每次可能的比较用一个内顶点表示，对应于不成功的结果有一个外顶点与之对应。 An-1xAn7/23/202215线性算法复杂度该方法没有很好利用已经排好序这个条件，顺序

6、搜索方法平均需要 O(n)次比较。7/23/2022162 二分搜索方法基本思想 取一个中间元素做比较元素，如果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)ak7/23/202217二元比较树含9个元素的情况4650287137/23/202218二元比较树x:A(n-1)/2x:A(n-3)/4x:A(3n-1)/4x:A(n-1)/2-1x:A(n-1)/2+1x:A0 x:An-1不成功不成功不成功不成功

7、不成功不成功不成功不成功7/23/202219例2-6 在9,12,15,27,39中分别查找27，12，149 12 15 27 390 1 2 3 4 left right midmid = (left+right)/2=(0+4)/2=2mid =(3+4)/2=39 12 15 27 39leftrightmid查找27成功返回3，leftrightmid9 12 15 27 39leftright7/23/202220template int BinarySearch( T a, const T& x, int n) /在a0=a1=amiddle) left= ; else rig

8、ht= ; return 1; /未找到xn-10left=right(left+right)/2middle+1middle 17/23/202221例:-15,-6,0,7,9,23,54,82,101中查找101，-14，82X=101Low high mid0 8 45 8 67 8 78 8 8 OKX=-14Low high mid0 8 40 3 10 0 0 0 NOX=82Low high mid0 8 45 8 67 8 7 OK7/23/202222二分搜索所需的空间和时间所需空间存放数组a的地址，还有left，right，middle，及x的地址需要存储，共10字节计算

9、时间成功检索的最好情况和不成功检索的最好情况成功检索的平均情况和不成功检索的平均情况成功检索的最坏情况和不成功检索的最坏情况7/23/202223成功检索最好情况和不成功检索最好情况成功检索共有n种不成功检索共有n+1种元素 2 5 6 7 9 23 54 82 101 a 0 1 2 3 4 5 6 7 8 3 3 3 4 4 3 3 3 4 4比较次数 3 2 3 4 1 3 2 3 4 成功比较次数不成功比较次数4650287137/23/202224由图可见，当x在数组A中时，算法在圆形顶点结束；不在A中时，算法在方形顶点结束。因为23924，所以比较树的叶顶点都在4或5级上出现。因而元素比较的最多次数为4。一般地有：当 时，一次成功的折半搜索至多做k次比较，而一次不成功的折半搜索或者做k-1次比较，或者做k次比较。7/23/202225二分搜