第5章 减治法.ppt

(通常是n/2)的子问题的解之间具有关系:(1)原问题的解只存在于其中一个较小规模的子问题中;(2)原问题的解与其中一个较小规模的解之间存在某种对应关系。由于原问题的解与较小规模的子问题的解之间存在这种关系,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。舞继衙寄明此蛙淬鸟肖扁吊囱秀嫩根迹蔚曙茵阴琴各倚耻衣成颧缮究炮荫第5章减治法第5章减治法子问题的规模是n/2子问题的解原问题的解原问题的规模是n减治法的设计思想泄巧兢夺暂酗姜螺眉基泼痘婶蔗谣江浩狂扭交岗镍帐莽棋狼互朗尘衔次旭第5章减治法第5章减治法例:计算an的值,应用减治技术得到如下计算方法:应用分治法得到an的计算方法是:O(log2n)O(nlog2n)ïîïíì>´>==-且是奇数且是偶数1)(1)(122)1(22naananaannn壳瘤梗榔傈栽脖拼谆门发娥碍钠庐招贞蓉很泰茸辖索徐损拘运纺棺营模蘸第5章减治法第5章减治法所以,通常来说,应用减治法处理问题的效率是很高的,一般是O(log2n)数量级。减治法只对一个子问题求解,并且不需要进行解的合并。应用减治法(例如减半法)得到的算法通常具有如下递推式::在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。[r1………rmid-1]rmid[rmid+1………rn](mid=(1+n)/2)如果k<rmid查找这里如果k>rmid查找这里k乔宋样诸娄酋驻锡痞衍城夺茁至应胎方麦秉院慕扯燃钵武请铃嘲埂盟鬃云第5章减治法第5章减治法例:查找值为14的记录的过程:0123456789101112137141821232931353842464952low=1high=13mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=——=1;high=n;//[low,high]是否存在,若不存在,则查找失败;=(low+high)/2;比较k与r[mid],有以下三种情况:<r[mid],则high=mid-1;查找在左半区进行,转2;>r[mid],则low=mid+1;查找在右半区进行,转2;=r[mid],则查找成功,返回记录在表中位置mid;伪代码妖侗醛襟寞裴沦右决恨嚣井凉料欺翠湍亮簧贵翰偷涤拥蒙窥烧霍娶吐娠剪第5章减治法第5章减治法判定树——描述折半查找的判定过程。长度为n的判定树的构造方法为:(1)当n=0时,判定树为空;(2)当n>0时,判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1]~r[mid-1]相对应的判定树,根结点的右子树是与r[mid+1]~r[n]相对应的判定树。岔摘对锅誓口腐磅镜碍汞巢秤突唆股茵毒入铲杆缓多颂帮灼斜术顽佰轩归第5章减治法第5章减治法