递归斐波那契算法的空间复杂度是多少？ [英] What is the space complexity of a recursive fibonacci algorithm?

问题描述

这是Craning the Coding Interview（第5版）中Fibonacci序列的递归实现

This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition)

int fibonacci(int i) {
       if(i == 0) return 0;
       if(i == 1) return 1;
       return fibonacci(i-1) + fibonaci(i-2);
}

观看有关此算法时间复杂度的视频后，Fibonacci时间复杂度，我现在明白为什么这个算法在O中运行（2 ⁿ ）。然而，我正在努力分析空间复杂性。

After watching the video on the time complexity of this algorithm, Fibonacci Time Complexity, I now understand why this algorithm runs in O(2ⁿ). However I am struggling with analyzing the space complexity.

我在线查看并对此有疑问。

I looked online and had a question on this.

在这个Quora线程中，作者声明在你的情况下，你有n个堆栈帧f（n），f（n-1），f（n-2），...，f（1）和O（1 ）。你不会有2n堆栈帧吗？说f（n-2）一帧将用于实际呼叫f（n-2），但是不会有来自f（n-1）的呼叫f（n-2）？

In this Quora thread, the author states that "In your case, you have n stack frames f(n), f(n-1), f(n-2), ..., f(1) and O(1)" . Wouldn't you have 2n stack frames? Say for f(n-2) One frame will be for the actual call f(n-2) but wouldn't there also be a call f(n-2) from f(n-1)?

推荐答案

如果其他人仍然感到困惑，请务必查看此Youtube视频，该视频讨论了生成Fibonacci序列的空间复杂性。 Fibonacci Space Complexity

If anyone else is still confused, be sure to check out this Youtube video that discusses the space complexity of generating the Fibonacci Sequence. Fibonacci Space Complexity

演示者非常清楚为什么空间复杂度为O（n），递归树的高度为n。

The presenter made it really clear why the space complexity was O(n), the height of the recursive tree is n.

这篇关于递归斐波那契算法的空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！