第5章减治法概要.ppt

排序问题中的减治法——堆排序 第五章 减治法 第五章 减 治 法 1 2 3 4 减治法的设计思想 排序问题中的减治法 组合问题中的减治法 5 查找问题中的减治法 小结 变治法分两个阶段工作，即“变”阶段和“治”阶段. 变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction) problem’s instance simpler instance or Another representation or another problem’s instance solution 变 治 法 概 述 减治是基于变治的思想。 逻辑等价 子问题 的规模是n/2 子问题的解 原问题的解 原问题 的规模是n （1） 原问题的解只存在于其中一个较小规模的子问题中; （2） 原问题的解与其中一个较小规模的解之间存在某种确定的对应关系。 1 减治法的设计思想 对于给定的整数a和非负整数n，计算an的值 应用减治技术得到如下计算方法： 应用分治技术得到如下计算方法： 应用分治法（例如二分法）得到的算法通常具有如下递推式： 分治法和减治法区别 应用减治法（例如减半法）得到的算法通常具有如下递推式： 2一个简单的例子—两个序列的中位数 问题描述：一个长度为n（n≥1）的升序序列S，处在第n/2个位置的数称为序列S的中位数 。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。 想法：分别求出两个序列的中位数，记为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中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。 2一个简单的例子—两个序列的中位数 对于两个给定的序列A={11, 13, 15, 17, 19}, B={2, 4, 10, 15, 20}，求序列A和B的中位数的过程。 {15} {13} 长度为1，较小者为所求 8 舍弃10之前元素，{15} 舍弃13之后元素，{13} 1013，结果在[10, 13]之间 7 {10,15} {13,15} 分别求中位数 6 舍弃15之后元素，{10,15} 舍弃13之前元素，{13,15} 1315，结果在[11, 15]之间 5 {10,15,20} {11,13,15} 分别求中位数 4 舍弃10之前元素，{10,15,20} 舍弃15之后元素，{11,13,15} 1510，结果在[10, 15]之间 3 {2, 4, 10, 15, 20} {11, 13, 15, 17, 19} 分别求中位数 2 {2, 4, 10, 15, 20} {11, 13, 15, 17, 19} 初始序列 1 序列B 序列A 操作说明 步骤 2一个简单的例子—两个序列的中位数 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均只有一个元素，返回较小者； 2一个简单的例子—两个序列的中位数 查找问题中的减治法——折半查找 问题描述：应用折半查找方法在一个有序序列中查找值为k的记录。若查找成功，返回记录k在序列中的位置，若查找失败，返回失败信息。 折半查找——想法 折半查找利用了记录序列有序的特点，其查找过程是：取有序序列的中间记录作为比较对象，若给定值与中间记录相等，则查找成功；若给定值小于中间记录，则在中间记录的左半区继续查找；若给定值大于中间记录，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 [ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] 如果krmid查找这里 如果krmid查找这里 k （mid=(1+n