递归算法的复杂性 [英] 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(2n). Actually, it is Θ(2n).
这篇关于递归算法的复杂性的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文