如何找到以下算法的复杂性：
int f(int n)
{
if(n<=1) { return 1; }
return f(n-1) + f(n-1);
}
它是正确的递归方程吗？怎么解决？
最佳答案
我认为你的递归方程是正确的。
但是这个具体的例子很简单，只需“想一想”就可以了，而不必深入到“如何解决一般的递归”。
让我们看看f（3）
f(3)
f(2) + f(2)
f(1) + f(1) + f(1) + f(1)
那么，我们有多少电话？
1+2+4
隐马尔可夫模型。。f（4）怎么样？
f(4)
f(3) + f(3)
f(2) + f(2) + f(2) + f(2)
f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1) + f(1)
那么，我们有多少电话？
1+2+4+8
所以我们可以对n=5:1+2+4+8+16做出一个合理的猜测如果你考虑一下，它也有意义，因为：numcalls（f（5））=2*numcalls（f（4））+1（1源于对f（5）本身的调用）。
我们可以把这个概括为
T(n) = sum(2^i) for i in (0, n-1)
现在，如果我们用这个事实
sum(2^i) for i in (0, n-1) == 2^n - 1
很明显
T(n) = 2^n - 1
在
O(2^n)作为练习：
通过归纳证明
T(n) = 2*T(n-1) + 1 <=> T(n) = 2^n - 1
或者更一般一点：
T(n) = 2*T(n-1) + c <=> T(n) = c*(2^n - 1)
正如评论中建议的那样：使用memoization
关于algorithm - 如何找到递归算法的时间复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37440630/