算法导论-递归式-数学归纳法求证
在看算法导论,其中一段话,百思不解:
代换法可用来确定一个递归式的上界或下界,作为例子,让我们确定递归式 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成立就完事了么
这两个是一回事