文档介绍：算法设计与分析
第四章递归式
假设归纳法
迭代方法
主方法
概念及求解方法
概念:T(n)=f(T(g(n))) (一般g(n) < n)
三种求解方法
假设归纳法
迭代方法
主方法
求解方式—忽略细节
假定式中n为整数(略去底、顶函数)
假定对小的n值T(n)为常量(略去边界条件)
求解后再检查这些忽略的细节是否会影响结果
假设归纳法
先猜测解的形式,再用归纳法证明。
猜测技巧:
类比猜测
如:T(n) = 2T(n/2+ 17) + n
逐步求精猜测
O(1)<O(lg n)<O(n)<O(n lg n)<O(n2)<O(2n)
假设归纳法
归纳法证明时的技巧:
根据界的形式定义,边界条件n0可选大一点的值。
例:求T(n) = 2T( n/2) + n 的界
猜测为O(n lg n),即证明存在c>0的常数,满足T(n) ≤ cn lg n 。
证明:设对n/2满足,则
T(n) ≤ 2(c n/2 1g ( n/2)) + n
≤ cn lg(n/2) + n
= cn lg n - cn lg 2 + n
= cn lg n - cn + n
≤ cn lg n,
只需c ≥ 1 即可。但该解对边界条件T(1)=1不成立,但可选n0=2
假设归纳法
归纳法证明时的技巧(续):
解中减一个低阶项(做一个更强的假设)。
例:求T(n) = T( n/2) + T ( n/2) + 1的界
猜测为O(n),即证明存在c>0的常数,满足T(n)≤ cn。
证明:设对n/2满足,则
T(n) ≤ c n/2+ c n/2 + 1
= cn + 1
得不到满足条件的c。
但猜测为T(n)≤ cn – b,有
T(n) ≤(c n/2- b) + (c n/2 - b) + 1
= cn - 2b + 1
≤ cn - b (只要b≥1)
对小的值作更强的假设,可证明给定值更强的结论
假设归纳法
归纳法证明时的技巧(续):
变量代换。
例:
变量代换:m = 1g n ,得:
T(2m) = 2T(2m/2) + m
再次变量代换:S(m) = T(2m) ,得:
S(m) = 2S(m/2) + m
则得S(m)=O(m lg m)
得:
T(n)=T(2m)=S(m)=O(m lg m)=O(lg n lg lg n).
假设归纳法
避免陷阱:
例:T(n) ≤ 2(c n/2) + n
≤ cn + n
= O(n) -- 错误
此处未证明归纳假设的准确形式:
T(n) ≤ cn
迭代方法
扩展递归式,然后进行和式求解(计算复杂)。
例:T(n) = 3T(n/4) + n.
T(n) = n + 3T(n/4)
= n + 3 (n/4+ 3T(n/16))
= n + 3(n/4+ 3(n/16+ 3T(n/64)))
= n + 3 n/4+ 9 n/16+ 27T(n/64)
当n/4i =1即i超过log4n时,扩展达到边界。故:
迭代方法
要点:
什么时候达到边界;
迭代过程的每一层中各项的和;
若迭代过程中已能估计出界的形式,则可以改用假设归纳法。