前端之家收集整理的这篇文章主要介绍了
这段代码的空间复杂度是多少？，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
int f(int n)
{
if (n <= 1)
{
return 1;
}
return f(n - 1) + f(n - 1);
}
我知道时间复杂度是O(2 ^ n),我明白为什么.
但是我不明白为什么空间复杂度是O(n).
我被告知,这是因为在任何给定的时间只有n个节点,但对我来说没有意义.
因为第二个f(n-1)不能运行,直到第一个完成(反之亦然 – 它是一样的).第一次
调用会递归n次,然后所有这些将返回,这样将总共推出n个堆栈帧.那么第二个电话会做同样的事情.
所以它在递归中永远不会超过n个级别,这是空间复杂性的唯一贡献者.
原文链接：https://www.f2er.com/c/115775.html
