递归算法的复杂性 [英] Complexity of a recursive algorithm

问题描述

我有一个递归算法，如：

I have a recursive algorithm like :

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

显然，ñ== 0 情况下是Θ（1）。但是我无法理解它到底是如何工作的。我的意思是它必须是这样的：

Obviously the n == 0 case is Θ(1). However I am having trouble understanding how it really works. I mean it must be something like :

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

然后，我们必须给 T（1），T（2），...，T（N-1）= XT（0）。我可以把它理解为去N = 0和n = 1的方式，但更大ñ它出了问题。

And then we have to give T(1), T(2), .., T(n-1) = xT(0). I can understand the way it goes for n=0 and n=1, but for bigger n it goes wrong.

推荐答案

您可以观察到：

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 ^N ）。其实，这是Θ（2 ^N ）。

At this point, we can conclude that the complexity is O(2ⁿ). Actually, it is Θ(2ⁿ).

这篇关于递归算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！