第5章_减治法.ppt

第5章减治法
减治法的设计思想
查找问题中的减治法
排序问题中的减治法
组合问题中的减治法
减治法的设计思想
规模为n的原问题的解与较小规模(通常是n/2)的子问题的解之间具有关系:
(1)原问题的解只存在于其中一个较小规模的子问题中;
(2)原问题的解与其中一个较小规模的解之间存在某种对应关系。
由于原问题的解与较小规模的子问题的解之间存在这种关系,所以,只需求解其中一个较小规模的子问题就可以得到原问题的解。
子问题
的规模是n/2
子问题的解
原问题的解
原问题
的规模是n
减治法的设计思想
例:计算an的值,应用减治技术得到如下计算方法:
应用分治法得到an的计算方法是:
O (log2n)
O (nlog2n)
ï
î
ï
í
ì
>
´
>
=
=
-
且是奇数
且是偶数
1
)
(
1
)
(
1
2
2
)
1
(
2
2
n
a
a
n
a
n
a
a
n
n
n
所以,通常来说,应用减治法处理问题的效率是很高的,一般是O(log2n)数量级。
减治法只对一个子问题求解,并且不需要进行解的合并。应用减治法(例如减半法)得到的算法通常具有如下递推式:
查找问题中的减治法
折半查找
二叉查找树
基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。
折半查找
[ r1 ……… rmid-1 ] rmid [ rmid+1 ……… rn ] (mid=(1+n)/2)
如果k<rmid查找这里如果k>rmid查找这里
k
例:查找值为14的记录的过程:
0 1 2 3 4 5 6 7 8 9 10 11 12 13
7 14 18 21 23 29 31 35 38 42 46 49 52
low=1
high=13
mid=7
high=6
mid=3
high=2
mid=1
31>14
18>14
7<14
low=2
mid=2
14=14
——折半查找
1. low=1;high=n; //设置初始查找区间
2. 测试查找区间[low,high]是否存在,若不存在,则查找失败;
否则
3. 取中间点mid=(low+high)/2; 比较k与r[mid],有以下三种情况:
若k<r[mid],则high=mid-1;查找在左半区进行,转2;
若k>r[mid],则low=mid+1;查找在右半区进行,转2;
若k=r[mid],则查找成功,返回记录在表中位置mid;
伪代码
判定树——描述折半查找的判定过程。
长度为n的判定树的构造方法为:
(1)当n=0时,判定树为空;
(2)当n>0时,判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的判定树,根结点的右子树是与r[mid+1] ~ r[n]相对应的判定树。