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

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

space-complexity recursion algorithm

1

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 年前

1

2

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) .

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

推荐文章

kiki · 确定递归函数的时间和空间复杂度

7 年前

Oscar · 如何确定这两个双链表算法的空间和时间复杂度?

8 年前

committedandroider · 枚举子集的空间复杂性是什么?

9 年前

subham soni · 确定给定代码的时间和空间复杂性

10 年前