运用代入法求递归式的时间复杂度不解 - 数据结构与算法

编程论坛 → 开发语言 → 『数据结构与算法』 → 运用代入法求递归式的时间复杂度不解

标题：运用代入法求递归式的时间复杂度不解

只看楼主

软件猿

来　自：南方
等　级：论坛游民
帖　子：21
专家分：20
注　册：2013-5-24
结帖率：100%

已结贴√ 问题点数：20 回复次数：2

运用代入法求递归式的时间复杂度不解

1.猜测
2.用数学归纳法求出解中的常数,并证明解是正确的
例题T(n)=2T(n/2)+n
到底该怎么证,哪用到数学归纳法了

搜索更多相关主题的帖子: 数学归纳法　

2013-11-20 22:04

yuccn

来　自：何方
等　级：版主
威　望：167
帖　子：6809
专家分：42393
注　册：2010-12-16

得分:20

先证明对于前面的数字成立，比如 1 、2
再假定T(k)=2T(k/2)+k 成立，并且通过它。去证明T(k+1)=2T(（k+1）/2)+（k+1）也成立即可

我行我乐
我的博客：
http://blog.yuccn. net

2013-11-21 11:53

软件猿

来　自：南方
等　级：论坛游民
帖　子：21
专家分：20
注　册：2013-5-24

得分:0

理解，原先以为是通过数学归纳法来确定常数c的，曲解了书上的意思，谢谢。

2013-11-21 15:06