第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章减治法