这个斐波那契数列算法的内存复杂度是多少？

Question

我最近做了一个技术面试，被问到我在白板上写的以下算法的内存复杂度。更具体地说，如果我没记错的话，他指的是"heap space":

public int[] fib = new int[1000];
public int fibonacci(int i) {
    if (i == 0) return 0;
    if (i == 1) return 1;
    if (fib[i] != 0) return fib[i];
    fib[i] = fibonacci(i - 1) + fibonacci(i - 2);
    return fib[i];
}

因为他说"heap space"，听起来他是在给我一个线索，他想让我给出下面这行代码的复杂度：

public int[] fib = new int[1000];

我想我记得在学校学习过 Java 中的 new 就像 C 中的 malloc，其中 malloc 从堆中分配存储空间。假设我的记忆没有错，现在让我们回到我的问题：这个的记忆复杂度是多少？我应该说 O(1000) 吗？在）？还有别的吗？

谢谢！

Answer 1

O(n) 对我来说似乎是正确的。您不会在 O 表示法中包含常量（如 O(1000)）。

顺便说一下，这是递归函数的问题，它的开放式内存复杂性。除非我可以限制输入大小，否则我无法使用这样的递归函数。

Answer 2

我认为您的面试官想知道您对所编写代码的后果的理解程度。非尾调用递归代码通常潜在的内存问题是每个递归调用占用一个堆栈帧，直到调用（包括其所有递归子调用）完成后才能进行垃圾回收。堆栈帧是从堆中分配的，因此递归会耗尽堆。

如果没有保存和检索已计算的斐波那契数的记忆快捷方式，内存复杂度将为 O(n²)：计算第 n 个斐波那契数将创建递归stackframes 树与 n 的平方成正比，因为它为树的不同分支重新计算了相同的数字。

但是发布的代码不必多次计算任何一个斐波那契数，堆栈帧的总数不会以同样的方式爆炸，最坏情况下它会保持在 O(n) ，其中数组最初为空。一旦数组被填充，它将是 O(1)，因为此时它相当于单个数组查找。

这个斐波那契数列算法的内存复杂度是多少？

What is the MEMORY complexity of this fibonacci sequence algorithm?

java

big-o