5

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

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

console.log(fib(32));
4

5 回答 5

6

这不是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 个叶子或过程调用！这个不起眼的小程序需要指数级的时间来运行！

您必须使用记忆或自下而上构建解决方案（即首先是小子问题）。

此解决方案使用记忆化（因此，我们只计算每个斐波那契数一次）：

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;
}
于 2012-07-02T03:39:58.823 回答
3

众所周知，如果天真地实施，您在问题中给出的斐波那契函数的实施需要很多步骤。特别是，它需要 7,049,155 次调用。

但是，这些算法可以通过一种称为memoization的技术大大加快。如果您看到函数调用fib(32)需要几秒钟，那么该函数的实现是天真的。如果它立即返回，则该实现很可能正在使用 memoization。

于 2012-07-02T03:24:31.037 回答
2

根据已经提供的证据，我得出的结论是：

当代码不是从控制台运行时（比如在 jsFiddle 中，我的机器 Sandy Bridge Macbook Air 在 55 毫秒内计算它），JS 引擎能够 JIT 并可能自动记忆算法。

从 js 控制台运行时，不会发生这种情况。在我的机器上，它只慢了 10 倍以下：460 毫秒。

然后我编辑了代码以查找 F(38)，它将时间提高到 967 毫秒和 9414 毫秒，因此它保持了类似的加速因子。这表明没有执行记忆，加速可能是由于 JITting。

于 2012-07-02T06:27:42.683 回答
1

只是一个评论...

函数调用相对昂贵，递归非常昂贵并且总是比使用有效循环的等效函数慢。例如，以下是 IE 中的递归替代方法的数千倍：

function fib2(n) {
  var arr = [0, 1];
  var len = 2;

  while (len <= n) {
    arr[len] = arr[len-1] + arr[len-2];
    ++len;
  }
  return arr[n];
}

正如其他答案中所指出的，OP 算法似乎本身也很慢，但我想这不是真正的问题。

于 2012-07-02T04:17:12.513 回答
0

除了@galymzhan 推荐的记忆方法之外，您还可以一起使用另一种算法。传统上，第 n 个斐波那契数的公式是 F(n) = F(n-1) + F(n-2)。这具有与 n 成正比的时间复杂度。

Dijkstra 提出了一种算法，可以用不到传统公式规定的一半步骤导出斐波那契数。这在他的著作EDW #654中有概述。它去：

  1. 对于偶数，F(2n) = (F(n))2 + (F(n+1))2
  2. 对于奇数，F(2n+1) = (2F(n) + F(n+1)) * F(n+1) 或 F(2n-1) = (2F(n+1) - F(n )) * F(n)
于 2012-07-11T12:40:52.650 回答