递归算法的复杂性

本文介绍了递归算法的复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个递归算法，如：

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(2n). Actually, it is Θ(2n).