algorithm - 如何找到递归算法的时间复杂度？

Question

如何找到以下算法的复杂度:

int f(int n)
{
  if(n<=1) { return 1; }
  return f(n-1) + f(n-1);
}

递归方程 T(n) = 2*T(N-1) + c 是否正确？如何解决？

Answer 1

我认为你的递归方程是正确的。

但是这个特定的案例很简单，“只是想”一下，而不是进一步研究“如何解决一般的递归问题”。

---

让我们看看 f(3)

            f(3)           

     f(2)    +    f(2)         

 f(1) + f(1) + f(1) + f(1)  

那么，我们有多少个电话？1 + 2 + 4

嗯.. f(4) 怎么样？

                           f(4)

             f(3)           +            f(3)

     f(2)    +    f(2)      +     f(2)     +   f(2)

 f(1) + f(1) + f(1) + f(1)  +  f(1) + f(1) + f(1) + f(1)

那么，我们有多少个电话？1 + 2 + 4 + 8

因此我们可以对 n=5 做出有根据的猜测:1+2+4+8+16。如果您考虑一下，它也是有道理的，因为:numCalls(f(5)) = 2*numCalls(f(4)) + 1(+ 1 源于对 f(5) 本身的调用)。

我们可以将其概括为

T(n) = sum(2^i) for i in (0, n-1)

现在，如果我们使用这个事实

sum(2^i) for i in (0, n-1) == 2^n - 1

很明显

T(n) = 2^n - 1 

O(2^n)

---

留作练习:

归纳证明

T(n) = 2*T(n-1) + 1   <=>  T(n)  = 2^n - 1

或者更一般一点:

T(n) = 2*T(n-1) + c   <=>  T(n)  = c*(2^n - 1)

---

正如评论中建议的旁注:您可以通过使用 memoization 显着提高性能