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

问题描述 投票:0回答:3

我最近做了一次技术面试,被问到我在白板上写的以下算法的内存复杂度。更具体地说,如果我没记错的话,他指的是“堆空间”:

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) 吗?在)?还有别的吗?

谢谢!

java big-o
3个回答
4
投票

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

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

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


0
投票

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

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


0
投票

我不确定你的面试官想从这个问题中得到什么。正如你所说,引用堆空间是指对象实例化。在这里,您创建了一个使用堆内存的包含 1000 个整数的数组。 无论您为变量选择什么值,该内存块仅被抓取一次并且不会增长,即。当然,您希望没有人会尝试使用大于 1000 的 i 值来调用它。因此,该堆空间的内存复杂度似乎是 O(1),即一个常量。 然而,如果你的面试官想了解堆栈空间的内存复杂性,即你的递归函数调用为每个函数帧(每次调用它们时)获取内存,那么也就是说,在最坏的情况下,O(n) 为记忆的复杂性。使用记忆化并不能摆脱 O(n) 的内存复杂性,因为必须至少遍历一次调用堆栈。 也许你的面试官还想听听你如何讨论堆栈和堆空间之间的内存权衡。这是另一种可能。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.