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

Question

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

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];
}

因为他说"堆空间"，听起来他给了我一个线索，他希望我给出以下代码行的复杂性：

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

我想我记得我在学校学到，Java 中的new就像 C 语言中的malloc，malloc从堆中分配存储。假设我的记忆正确为我服务，现在让我们回到我的问题：这是什么内存复杂性？我应该说O（1000）吗？O（n）？别的？

谢谢！

Answer 1

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

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

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

Answer 2

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

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