复发时间复杂度T（n）= 2T（n-1）+ 4 [英] What is the time complexity of the recurrence T(n) = 2T(n-1) + 4

问题描述

复发时间复杂度T（n）= 2T（n-1）+ 4？

我有严重的问题。
我试过：

T（n）= 2T（n-1）+4 = 2（2T（n-2）+4）+4 = 4T（n-2）+12 = 4（2T（n-3）+4）+4 = 8T（n-3）+20 = 8（2T（n-4）+4）+4 =
16T（n-4）+36 = ...

T（n）= 2 ^ kT（nk）+（4 + 2 ^（k + 1） p>

所以看起来像T（n）= 2 ^ n +（4 + 2 ^（n + 1）），但似乎不对...请帮助： （

解决方案

您的计算错误，我假设这里 T（0）= 0

  T（n）= 2T（n-1）+ 4 
 = 2T（n-2）+4）+ 4 = 4T（n-2）+ 12 
 = 4（2T（n-3）+4）+12 = 8T（n-3）+28 
 = 8（2T（n-4）+4）+28 = 16T（n-4）+ 60 
 = 16（2T（n-5）+4）+60 = 32T（n-5）+ 124 
 = 32（2T（n-6）+4）+124 = 64T（n-6）+252 
  

然后现在看看序列

  0,4,12,28,60,124,252,508,1020， 2044，... 
  

添加4到所有这些数字是非常诱人的：

  4,8,16,32,64,128,256,512 ，1024,2048，... 
  

你认识吗？所以猜测显然是

  T（n）= 2 ^（n + 2） -  4 
  

现在，您可以很容易地通过归纳来证明它。

顺便说一下如果 T（0）不等于 0 公式是

  T（n）= 2 ^（n + 2） -  4 + T（0）* 2 ^ n 
  

What is the time complexity of the recurrence T(n) = 2T(n-1) + 4 ?

I'm having serious problems with this. I tried:

T(n) = 2T(n-1)+4 = 2(2T(n-2)+4)+4 = 4T(n-2)+12= 4(2T(n-3)+4)+4 = 8T(n-3)+20 = 8(2T(n-4)+4)+4 = 16T(n-4)+36 =…

T(n) = 2^kT(n-k) + (4+2^(k+1))

so it looks like T(n) = 2^n + (4+2^(n+1)) but it doesn't seem right... please help :(

解决方案

Your computation are wrong. I'm assuming here that T(0)=0

T(n) =                       2T(n-1)+  4 
     =   2(2T(n-2)+4)+  4 =  4T(n-2)+ 12
     =   4(2T(n-3)+4)+ 12 =  8T(n-3)+ 28 
     =   8(2T(n-4)+4)+ 28 = 16T(n-4)+ 60
     =  16(2T(n-5)+4)+ 60 = 32T(n-5)+124
     =  32(2T(n-6)+4)+124 = 64T(n-6)+252

Then now: look at the sequence

0,4,12,28,60,124,252,508,1020,2044,...

It is very tempting to add 4 to all these numbers:

4,8,16,32,64,128,256,512,1024,2048,...

Do you recognize it ? So the guess is clearly

T(n) = 2^(n+2) - 4

Now, you can easily prove it by induction.

By the way if T(0) is not equal to 0 the formula is

T(n) = 2^(n+2) - 4 + T(0)*2^n

这篇关于复发时间复杂度T（n）= 2T（n-1）+ 4的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！