5.1 层治法的设计思想.ppt

5.1 层治法的设计思想 2017-11-16 第5章 层治法 Page 2 规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。 5.1 层治法的设计思想 2017-11-16 第5章 层治法 Page 4 例：计算an的值，应用层治技术得到如下计算方法： 应用分治法得到an的计算方法是： O (log2n) O (nlog2n) 5.1 层治法的设计思想 2017-11-16 第5章 层治法 Page 5 所以，通常来说，应用层治法处理问题的效率是很高的，一般是O(log2n)数量级。 层治法只对一个子问题求解，并且不需要进行解的合并。应用层治法（例如层半法）得到的算法通常具有如下递推式： 5.1 层治法的设计思想 对比分治法： 2017-11-16 第5章 层治法 Page 6 5.1 层治法的设计思想 一个简单的例子—两个序列的中位数 问题描述：一个长度为n（n≥1）的升序序列S，处在第n/2个位置的数称为序列S的中位数 。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。 A={11, 13, 15, 17, 19}, B={2, 4, 10, 15, 20}，则中位数为13 想法：分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况： ① a = b：则a即为两个序列的中位数； ② a b：则中位数只能出现在a和b之间，在序列A中舍弃a之前的元素得到序列A1，在序列B中舍弃b之后的元素得到序列B1； ③ a b：则中位数只能出现在b和a之间，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1； 在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。 步骤 操作说明 序列A 序列B 1 初始序列 {11, 13, 15, 17, 19} {2, 4, 10, 15, 20} 2 分别求中位数 {11, 13, 15, 17, 19} {2, 4, 10, 15, 20} 3 1510，结果在[10, 15]之间 舍弃15之后元素，{11,13,15} 舍弃10之前元素，{10,15,20} 4 分别求中位数 {11,13,15} {10,15,20} 5 1315，结果在[11, 15]之间 舍弃13之前元素，{13,15} 舍弃15之后元素，{10,15} 6 分别求中位数 {13,15} {10,15} 7 1013，结果在[10, 13]之间 舍弃13之后元素，{13} 舍弃10之前元素，{15} 8 长度为1，较小者为所求 {13} {15} 1. 循环直到序列A和序列B均只有一个元素 1.1 a = 序列A的中位数； 1.2 b = 序列B的中位数； 1.3 比较a和b，执行下面三种情况之一： 1.3.1 若a=b，则返回a，算法结束； 1.3.2 若ab，则在序列A中舍弃a之前的元素，在序列B中舍弃b之后的元素，转步骤1； 1.3.3 若ab，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1； 2. 序列A和序列B均只有一个元素，返回较小者； 判定树——描述折半查找的判定过程。 长度为n的判定树的构造方法为： （1）当n=0时，判定树为空； （2）当n＞0时，判定树的根结点是有序表中序号为mid=(n+1)/2（取地板）的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的判定树。