javascript - 如何使这个 fib 序列更快？

Question

var fibonacci = function(n) {
    let cache = {};
    let value;
    if (n in cache) {
        value = cache[n];
    } else {
        if (n == 0 || n == 1) {
            value = n;
        } else {
            value = fibonacci(n - 1) + fibonacci(n - 2);
            cache[n] = value;
        }enter code here
    }
    return value;
};

fibonacci(60)

---

codewar 不会接受这个 fib 序列它太慢了如何让它更快

标签： javascript

Answer 1

使用两个递归会导致非常糟糕的性能（有利于理解递归）。您需要在记忆化旁边使用循环和数组以获得良好的性能。毕竟繁重的计算阻塞了 JavaScript 中的主线程，因此对于繁重的计算应用程序来说不是一个好的选择。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

const cache = [1, 1]

function fibonacci(n) {
  if (n <= cache.length) {
    return cache[n - 1]
  }
  for (let i = cache.length; i < n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2]
  }
  return cache[n - 1]
}

为避免使用全局，您可以使用闭包：

function fibonacci(m) {
  const cache = [1, 1]
  return (function (n) {
    if (n <= cache.length) {
      return cache[n - 1]
    }
    for (let i = cache.length; i < n; i++) {
      cache[i] = cache[i - 1] + cache[i - 2]
    }
    return cache[n - 1]
  })(m)
}

这是一个使用递归和记忆的动态编程的例子。