首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

算法导论-递归式-数学归纳法求证,该怎么解决

2013-11-18 
算法导论-递归式-数学归纳法求证在看算法导论,其中一段话,百思不解:代换法可用来确定一个递归式的上界或下

算法导论-递归式-数学归纳法求证
在看算法导论,其中一段话,百思不解:
代换法可用来确定一个递归式的上界或下界,作为例子,让我们确定递归式 T(n) = 2T(floor(n/2))+n的一个上界。猜测其解为T(n)=O(nlgn)。我们的方法是证明T(n)<=cnlgn,其中c>0是某个常数。先假设这个界对floor(n/2)成立,即T(floor(n/2))<=cfloor(n/2)lg(floor(n/2))。

我的问题是,数学归纳法是这样用的吗,不都是先对基本情况求证,再对n=m假设,最后证明n=m+1成立就完事了么,为什么这里是floor(n/2)啊?有木有大神给用这种传统的数学归纳法证明下这个题的?? 算法导论 递归式 证明
[解决办法]
归纳法是一种思想
本质是保质变量域内所有值都能推导 出条件成立
你说的只是最简单的一种归纳法

比如 n= 1、2 成立
     有 n=k-1、k成立可以推出n=k+1、k+2成立也是一种归纳

更复杂的 有2序列ab  a1成立 b1成立
ak可以推出bk成立 
bk可以推出ak+1成立 
也是一种归纳
因为 a1 b1 a2 b2 a3 b3

n = 1成立
假设n<k都成立 可以推导出n<2*k都成立 也是 一种归纳

如此种种

[解决办法]
>先假设这个界对floor(n/2)成立
>再对n=m假设,最后证明n=m+1成立就完事了么

这两个是一回事

热点排行