这种斐波那契数列算法的内存复杂度是多少? [英] What is the MEMORY complexity of this fibonacci sequence algorithm?

问题描述

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

I recently did a technical interview and was asked for the memory complexity of the following algorithm that I wrote on the whiteboard. To be more specific, if I remember correctly, he was referring to "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];
}

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

Because he said "heap space", it sounds like he was giving me a clue that he wanted me to give the complexity of the following line of code:

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

我想我记得在学校时曾学习过Java中的new类似于C语言中的malloc，其中malloc从堆中分配存储空间.假设我的记忆正确地为我服务，现在让我们回到我的问题:这的记忆复杂度是多少?我应该说O(1000)吗?在)?还有吗?

I think I remember learning in school that new in Java is like malloc in C, where malloc allocates storage off the heap. Assuming that my memory serves me correctly, let's now go back to my question: what is the memory complexity of this? Was I supposed to say O(1000)? O(n)? Something else?

谢谢！

推荐答案

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

I think your interviewer wanted to know how well you understood the consequences of the code you wrote. The usual potential memory problem with non-tail-call recursive code is that each recursive call takes up a stack frame, which can't be garbage collected until the call (including all its recursive subcalls) is completed. The stack frames are allocated from the heap, so the recursion can deplete the heap.

没有用于保存和检索已经计算出的斐波那契数的记忆快捷方式，则内存复杂度将为O(n ² ):计算第n个斐波那契数将创建一个与框架成比例的递归树n的平方，因为它为树的不同分支重新计算了相同的数字.

Without the memoization shortcut that saves and retrieves the already-calculated fibonacci numbers, the memory complexity would be O(n²): calculating the nth fibonacci number would create a recursive tree of stackframes proportionate to the square of n, as it recalculated the same numbers for different branches of the tree.

但是发布的代码不必计算一次以上的斐波那契数，并且堆栈帧的总数不会以相同的方式爆炸，在最坏的情况下，它将降至O(n)，在这种情况下，该数组最初为空.一旦填充了数组，它就会是O(1)，因为在那一点上，它等于一次数组查找.

But the posted code shouldn't have to calculate any one fibonacci number more than once, and the total number of stackframes will not explode the same way, it would be kept down to O(n) for the worst case, where the array is initially empty. It would be O(1) once the array is populated, since at that point it amounts to a single array lookup.

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