计算Fibonacci数

Question

以下问题目前需要超过8秒才能执行。请帮助我修改程序，以便减少执行时间。

var yourself = {
fibonacci : function(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    else {
        return this.fibonacci(n - 1) +
            this.fibonacci(n - 2);
    }
}
};

Answer 1

这是算法复杂性的标准例子之一。这个算法很容易理解，因为它很好地符合数学定义，但是执行起来很糟糕，因为它试图通过将0和1s相加来计算一个指数增长的数字。

关键的观察是，要计算，比方说，fibonacci(5)，它必须递归计算fibonacci(4)和fibonacci(3)。然后，要计算fibonacci(4)，必须再次计算fibonacci(3)，这是完全浪费的。为了加快速度，我们可以做几件事：

• 从下往上建。启动两个变量a=0和b=1，然后运行一个设置a=b和b=a+b的循环(注意不要在使用它们时爆炸值)。这就是你用手做的。
• 使用递归解决方案，但是缓存结果，这样就不会重复工作。这叫做回忆录。
• 使用封闭形式的公式。

Answer 2

我对javascript不太熟悉，但现在开始了。

首先介绍一下背景。您所发现的计算斐波纳契数的方法称为动态规划。

动态规划的好处在于它强化了构建解决方案的想法。也就是说，你首先要解决一个与你想要解决的问题类似的问题，但首先你要专注于它的最小方面，这样你就可以在这个解决方案的基础上解决一个更复杂的问题。

我的闲谈有什么意义？我注意到您正在使用动态编程来解决这个问题，但是您忽略了一件事，那就是重用您已经得到的其他解决方案。不重用您的解决方案会导致一种指数时间算法，这种算法在较大的输入下不能很好地扩展。

溶液

存储以前解决方案的结果，并使用它们来解决较大的问题。

fibonacci = function (n) {
    var fib = [0, 1]
    return function memoizedFib(n) {
        if (!fib[n]) {
            fib[n] = memoizedFib(n - 1) + memoizedFib(n - 2);
        }
        return fib[n];
    }(n);
};

有关计算fibonacci的另一种方法，请参见这个职位

Answer 3

另一种方法是做一些更接近这一点的事情。请注意，我不知道这段代码是否正常，但是当我将它作为一个独立的函数时，它在Google中有效。

var yourself = {
fibonacci : function(n) {
    var n0 = 0;
    var n1 = 1;
    var n2;
    for (var l = 2; l <= n; l++) {
        n2 = n0 + n1;
        n0 = n1;
        n1 = n2;
    }
    return n2;
}
}

这个方法让您从0向上工作到n (而不是向下从n到0)，并在运行时将结果存储在三个变量中。它使事情变得更快，因为你不需要找到fibbonacci(n-1)两次，fibbonacci(n-2)三次，等等。