递归算法的复杂性

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 ⁿ).