最有效的方法来计算Javascript中的斐波那契数列

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

我把下面的函数放在一起来计算第n个斐波那契数。 这有效（对于相当高的输入）。 我的问题是，我该如何改进这个功能？ 用这种方法计算斐波纳契数列有什么缺点？

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）。 它是否正确？

---

如果您没有阵列，则可以节省内存和.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;
}

---

表现斐波纳契：

    var memo = {};
    var countInteration = 0;
    var fib = function (n) {
        if (memo.hasOwnProperty(n)) {
            return memo[n];
        }
        countInteration++;
        console.log("Interation = " + n);
        if (n == 1 || n == 2) {
            result = 1;
        } else {
            result = fib(n - 1) + fib(n - 2);
        }
        memo[n] = result;
        return result;
    }
    //output `countInteration` = parameter `n`

链接地址: http://www.djcxy.com/p/39917.html

上一篇: Most efficient way to calculate Fibonacci sequence in Javascript

下一篇: Fibonacci sequence generation