递归的时间复杂度是T(n) = 2T(n-1) +4

Question

递归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(n-k) + (4+2^(k+1))

所以它看起来像T(n) = 2^n + (4+2^(n+1))，但它看起来不正确...请帮助我:(

Answer 1

你的计算是错的。我在这里假设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

然后现在:看看这个序列

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

Answer 2

通过求解递归关系，我发现：

​

​

Answer 3

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

那就让n = log m吧，我们得到了T(log m)=2T(log m - log 2) + 1

假设S(a) = 2S(a/2) + 1

应用马斯特定理，我们得到：n^logb^a = n^log2^2 = n。

n^log2^2-1 = 1，这里是€ = 1

通过第一种情况，我们得到：S(a) = O(a)

因此，T(n) = O(2^n)