在Javascript中计算斐波纳契数列的最有效方法

Question

我正在尝试通过优化算法和理解big-o等方面做得更好.

我把下面的函数汇总在一起来计算第n个斐波纳契数.这是有效的(对于相当高的输入).我的问题是,我该如何改进这个功能？以这种方式计算Fibonacci序列有什么缺点？

function fibo(n) {  

    var i;
    var resultsArray = [];  

    for (i = 0; i <= n; i++) {
        if (i === 0) {
            resultsArray.push(0);
        } else if (i === 1) {
            resultsArray.push(1);
        } else {
            resultsArray.push(resultsArray[i - 2] + resultsArray[i - 1]);
        }
    }

    return resultsArray[n];
}

我相信我的大时间是O(n),但由于我创建的数组,我的空间大o是O(n ^ 2).它是否正确？

Answer 1

如果您没有阵列,那么您可以节省内存和.push呼叫

function fib(n) {
    var a = 0, b = 1, c;
    if (n < 3) {
        if (n < 0) return fib(-n);
        if (n === 0) return 0;
        return 1;
    }
    while (--n)
        c = a + b, a = b, b = c;
    return c;
}