1 / 25
文档名称:

算法设计与分析递归式.ppt

格式:ppt   大小:1,283KB   页数:25页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法设计与分析递归式.ppt

上传人:文库新人 2021/11/23 文件大小:1.25 MB

下载得到文件列表

算法设计与分析递归式.ppt

相关文档

文档介绍

文档介绍:算法设计与分析递归式
第一页,课件共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页