代码之家 › 专栏 › 技术社区 › Abhishek Bhatia

斐波那契序列递归空间复杂度[重复]

space-complexity recursion algorithm

Abhishek Bhatia · 技术社区 · 6 年前

这个问题已经有了答案:

public int fib(int n) {
if (n == 0) return 0; 
if (n == 1) return 1; 
return fib(n-1) + fib(n-2);
}

我很困惑为什么上面代码的空间复杂度是o(n)。现在,我知道递归的深度是 n ,也就是树的高度。

没有创建临时变量或最终结果变量。这里的空间复杂度是从函数调用堆栈计算出来的吗?

1 回复 | 直到 6 年前

Abhijith Asokan 6 年前

是的,本例中的空间复杂度取决于调用堆栈中使用的空间,这取决于活动函数调用的数量(已调用但未完成执行的函数)。

如果你注意到最后一句话

return fib(n-1) + fib(n-2)

什么时候? fib(n-1) 是经过计算的 O(n) 使用空间。一次 FIB(N-1) 完成执行堆栈空间可由 fib(n-2) .

因此,在这种情况下,调用 fib(n) 是 o(n) ,因此空间复杂性为 o(n) .

然而,值得注意的是,时间复杂度是指数级的。

推荐文章

jkfe · 为什么println会在这段递归代码中执行?

2 年前

Brian Patterson · Javascript自定义数组。原型方法日志“未定义”

2 年前

Jimmy · 这种算法怎么能按顺序遍历树“爬上”树呢?

2 年前

iRon · 匿名递归函数

2 年前

ProgrammingNoob321312 · 为什么这个Java代码会输出“3210123”?

2 年前

AvirukBasak · gcc中无return语句的尾部递归

2 年前

Dharmik Patel · 使用python递归完全可以整除

2 年前

W.tan · 一维最短距离递归算法

2 年前

ncarrawa · 将1添加到i(递归)时出现类型错误

3 年前

Eren · Python递归何时返回[duplicate]

3 年前