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

软件猿发布于 2013-11-20 22:04， 840 次点击

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

2 回复

yuccn2013-11-21 11:53

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

软件猿2013-11-21 15:06

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