c++ - 递归算法的复杂性

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