为什么这个js代码这么慢？

Question

此代码在Chrome上为3秒,在Firefox上为6秒.如果我用Java编写代码并在Java 7.0下运行它只需要10ms.Chrome的JS引擎通常非常快.为什么这么慢？顺便说一句.此代码仅用于测试.我知道写一个斐波那契函数不是很实用的方法

fib = function(n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
};

console.log(fib(32));

Answer 1

这不是javascript的错,而是你的算法.你一遍又一遍地重新计算相同的子问题,当N更大时,它会变得更糟.这是单个呼叫的呼叫图:

                  F(32)
               /         \
            F(31)            F(30)
          /     \           /      \
      F(30)     F(29)     F(29)    F(28)
    /  \      /     \     /   \     |    \
F(29) F(28) F(28) F(27) F(28) F(27) F(27) F(26)

... deeper and deeper

正如您从这棵树中看到的那样,您可以多次计算一些斐波纳契数,例如F(28)计算4次.来自"算法设计手册"一书:

这个算法花了多少时间来计算F(n)？由于F(n + 1)/ F(n)≈φ=(1 + sqrt(5))/2≈1.61803,这意味着F(n)> 1.6 ^ n.由于我们的递归树只有0和1作为叶子,总结到如此大的数字意味着我们必须至少有1.6 ^ n叶子或过程调用!这个简陋的小程序需要指数时间才能运行!

您必须自下而上使用memoization或构建解决方案(即首先是小的子问题).

此解决方案使用memoization(因此,我们只计算每个Fibonacci数一次):

var cache = {};
function fib(n) {
  if (!cache[n]) {
    cache[n] = (n < 2) ? n : fib(n - 1) + fib(n - 2);
  }
  return cache[n];
}

这个解决了它的自下而上:

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