递归算法的复杂度

Question

我有一个递归算法:

int alg(int n) {
  if (n == 0)
    return 2;
  for (int i = 0; i<= n-1; ++i)
    alg(i);
}

显然n == 0就是Θ(1)。然而，我很难理解它是如何真正工作的。我的意思是它必须是这样的:

T(n) = T(0) + T(1) + ... + T(n-1).

然后我们要给T(1), T(2), .., T(n-1) = xT(0)。我能理解n=0和n=1时的情况，但对于更大的n，情况就不一样了。

Answer 1

您可以观察到:

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

因此,

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

此时，我们可以得出复杂性为O(2ⁿ)。实际上，它是Θ(2ⁿ)。