算法练习01 记忆化斐波那契函数

题目(2018-11-15)

斐波那契数列指的是类似于下面的数列：

1， 1， 2， 3， 5， 8， 13， ……

也就是，第n个数是由前面两个数相加而来

完成fibonacci函数，接受n作为参数，可以获取数列中第n个数，例如：

fibonacci(1) // => 1
fibonacci(2) // => 1
fibonacci(3) // => 2
...

实现

想到的最简单的实现就是利用递归：

const fibonacci = (n) => {
  if (n === 2 || n === 1) {
    return 1
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

这样的问题时，当n比较大的时候（比如500），计算时间过长，程序会失去响应

所以需要进行改进，需要利用缓存，空间换区时间，在计算时多传入一个cache对象，用于缓存计算过的数据：

const fibonacci = (n, cache = {}) => {
  if (n <= 2) {
    return cache[n] = 1;
  }
  if (cache[n]) {
    return cache[n];
  }
  return cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache)
};

console.time('1st');
console.log(fibonacci(1000));
console.timeEnd('1st');
// 4.346655768693743e+208
// 1st: 1.26904296875ms

console.time('2ed');
console.log(fibonacci(1000));
console.timeEnd('2ed')
// 41 4.346655768693743e+208
// 2ed: 0.637939453125ms

通过实验，这样是行得通的。

我们还可以进一步优化，由于缓存cache在每次计算都是需要反问的，也就是说cache是需要保留在内存中的，那么我们就可以构造一个闭包，让cache保留在闭包中，供递归时使用：

const fibonacci = ((cache = {}) => n => {
  if (cache[n]) {
    return cache[n];
  }
  if (n <= 2) {
    return cache[n] = 1;
  }
  return cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
})();

console.time('1st');
console.log(fibonacci(1000));
console.timeEnd('1st');
// 4.346655768693743e+208
// 1st: 0.6630859375ms

console.time('2ed');
console.log(fibonacci(1000));
console.timeEnd('2ed')
// 41 4.346655768693743e+208
// 2ed: 0.186279296875ms

多次试验后发现，采用闭包的计算速度还是要快于直接传参的计算速度的，尤其是非首次计算，相对于首次计算时，由于cache会保留在内存中，对计算速度的提高非常大

参考

• ScriptOJ - 102 记忆化斐波那契函数（Memoization）
• CSDN - 记忆化斐波那契函数