文档介绍：算法设计与分析递归式
第一页，课件共25页
第四章 递归式
假设归纳法
迭代方法
主方法
第二页，课件共25页
概念及求解方法
概念：T(n)=f(T(g(n))) (一般g(n) < n)
三种求解方法
假设归纳法
迭代方法
主方法
求解方式 — 忽略细节
假定式中n为整数（略去底、顶函数）
假定对小的n值T(n)为常量（略去边界条件）
求解后再检查这些忽略的细节是否会影响结果
第三页，课件共25页
假设归纳法
先猜测解的形式，再用归纳法证明。
猜测技巧：
类比猜测
如：T(n) = 2T(n/2 + 17) + n
逐步求精猜测
O(1)<O(lg n)<O(n)<O(n lg n)<O(n2)<O(2n)
第四页，课件共25页
假设归纳法
归纳法证明时的技巧：
根据界的形式定义，边界条件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
第五页，课件共25页
假设归纳法
归纳法证明时的技巧（续）：
解中减一个低阶项（做一个更强的假设）。
例：求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)
对小的值作更强的假设，可证明给定值更强的结论
第六页，课件共25页
假设归纳法
归纳法证明时的技巧（续）：
变量代换。
例：
变量代换：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).
第七页，课件共25页
假设归纳法
避免陷阱：
例：T(n) ≤ 2(c n/2 ) + n
≤ cn + n
= O(n) -- 错误
此处未证明归纳假设的准确形式：
T(n) ≤ cn
第八页，课件共25页
迭代方法
扩展递归式，然后进行和式求解(计算复杂)。
例：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时，扩展达到边界。故：
第九页，课件共25页
迭代方法
要点：
什么时候达到边界;
迭代过程的每一层中各项的和;
若迭代过程中已能估计出界的形式，则可以改用假设归纳法。
第十页，课件共25页