首页 > 试题广场 >

计算以下递归方程：初始值T(1)=1。 T (n) = T

[问答题]

计算以下递归方程：初始值T(1)=1。
T (n) = T (n/2) + 1
T (n) = 2T (n/2) + n

Kabutoo

T (n) = T (n/2) + 1

令n=2^k

T (2^k) = T (2^{k -1}) + 1
=T (2^{k -2}) +1+1

= T (2^{k -3}) +1+1+1

= ...

=T (2^{k -i}) +i

=...

=T (1) +k (这是令2^{k -i} =1， k就等于i）

=1+k

=log₂ⁿ +1

T (n) = 2T (n/2) + n

令n=2^k

T (2^k) =2T (2^{k -1}) + 2^k

= 2[2T (2^{k -2}) +2^{k -1}] + 2^k

=2² T (2^{k -2}) +2^k +2^k

=2³ T (2^{k -3}) +2^k +2^k+2^k

=...

=2ⁱ T (2^{k -i}) +i2^k

=...

=2^k T(1)+k2^k

=(k+1)2^k

=(log₂ⁿ+1)n

编辑于 2019-02-19 15:25:26 回复(0)

Abel312

题错了吧

发表于 2018-03-16 00:02:04 回复(0)

提交观点

问题信息

递归

上传者：蜡蜡

难度：

2条回答 2收藏 2143浏览

扫一扫，把题目装进口袋