实现斐波那契数列 fibonacci

很早之前实现过这个，当时的目标是：

实现多个方法
实现单元测试
实现基准测试
1. 使用 benchmark 验证最优方法

现在重新研究这个问题，实现使用 JavaScript 尽可能快地来计算斐波那契数列

迭代方式(for, while)
递归方法
尾递归优化
带缓存的递归
动态规划 DP

实现代码

/**
 * 迭代方式来实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function iter(n) {
  let current = 0
  let next = 1
  for (let i = 0; i < n; i++) {
    const swap = current
    current = next
    next = swap + next
  }
  return current
}

// while 同 for
function whileFn(n) {
  let current = 0 // 表示 f(n)
  let next = 1 // 表示 f(n+1)
  while (n--) {
    next += current
    current = next - current
  }
  return current
}

/**
 * 递归方式实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function recurse(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return recurse(n - 1) + recurse(n - 2)
}

// 暴力递归，存在大量的重叠子问题
// 这就是动态规划问题的第⼀个性质：重叠⼦问题
// 子问题的个数 O(2^n), 算法的时间复杂度 O(2^n)

/**
 * 尾递归优化实现斐波那契数列
 *
 * @param {number} n
 * @returns
 */
function tail(n) {
  return fib(n, 0, 1)
}

/**
 * 尾递归优化
 *
 * @param {number} n
 * @param {number} current
 * @param {number} next
 * @returns
 */
function fib(n, current, next) {
  if (n === 0) return current
  return fib(n - 1, next, current + next)
}

// 带备忘录的递归解法（使用 memo 数组或哈希表充当备忘录）
// 备忘录相当于提供了一套“剪枝”操作，使递归数改造为不存在冗余的递归树，极大地减少了子问题

const memo = [0, 1]

function memoFib(n) {
  return helper(memo, n)
}

function helper(memo, n) {
  if (n === 1 || n === 2) {
    memo[n] = 1
    return memo[n]
  }
  if (typeof memo[n] !== 'undefined') {
    return memo[n]
  }
  memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
  return memo[n]
}

// 无冗余计算
// 子问题时间复杂度 O(1), 子问题个数 O(n), 算法的时间复杂度 O(n)
// 比起暴力算法，强太多了
// 带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。
// 只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」

// 从一个规模较大的原问题，比如 f(20)，向下逐渐分解规模，直到触底，然后逐层返回答案，这就叫做「自顶向下」
// 反过来，直接从最底下，最简单、问题规模最小的开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路
// 这也是为什么动态规划一般都脱离了递归，而是有循环迭代完成计算。

// 动态规划

function dpFib(n) {
  if (n === 0) return 0
  if (n === 1 || n === 2) return 1

  const dp = [0, 1, 1]
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

// 「状态转移方程」
// 动态规划问题最困难的就是写出状态转移方程，就是暴力解
// 优化方法无非就是用备忘录或 DPtable，再无奥妙可言

// 继续思考
// 根据斐波那契数列的状态转移方程，可以看出当前状态只和之前的两个状态相关，
// 所以并不需要很长的 DPTable 来存储所有状态，字需要存储两个状态就行了
// 这样进一步优化，可以把空间复杂度从 O(n) 降为 O(1)

注意

使用动态规划这种思想解决问题的前提是，

一个问题当中必须有重复的子问题才能使用动态规划进行解决。

实现斐波那契数列 fibonacci ​

实现斐波那契数列 fibonacci