JS斐波那契数列O(n)

function fibonacci(n) {

    return fib(n)[n]

}

var fib=(function(n){

    var meo=[0,1]

    return function(n){

        for(var i=meo.length;i<=n;i++){

            meo[i]=meo[i-1]+meo[i-2]

        }

        return meo.slice(0,n+1)

    }

})()

以上空间复杂度：o(n)，时间复杂度：o(n)，最快 o(1)

2.运用大数加法：

var _fib = (function (n) {

    var memory = ['0', '1'];

    function add(a, b) {

        var res = '',

            c = 0;

        a = a.split('');

        b = b.split('');

        while (a.length || b.length || c) {

            c += ~~a.pop() + ~~b.pop();

            res = c % 10 + res;

            c = c > 9;

        }

        return res.replace(/^0+/, '');

    }

    return function (n) {

        for (var i = memory.length; i <= n; i++) {

            memory[i] = add(memory[i - 1], memory[i - 2]);

        }

        //console.log(memory.length + ' numbers saved.');

        return memory.slice(0, n + 1);

    };

})();

var fibonacci = function (n) {

    return _fib(n)[n];

}

巴特西

JS斐波那契数列O(n)

最新文章

热门文章