斐波那契数

迭代+缓存

  1. 图解：

  2. 复杂度：

    • 时间复杂度：O(n)；
    • 空间复杂度：O(1)；

  3. 代码实现：

    function fib(n: number): number {
  if (n < 2) return n;

  let memo = [0, 1];
  let res = 0;

  for (let i = 2; i <= n; i++) {
    res = memo[0] + memo[1];

    memo[0] = memo[1];
    memo[1] = res;
  }

  return res;
}

递归+缓存

  1. 复杂度：

    • 时间复杂度：O(n)；
    • 空间复杂度：O(n)；

  2. 代码实现：

    function fib(n: number): number {
  let list = [0, 1];
  return reverse(list, n);
}

function reverse(memo: Array<number>, n: number): number {
  if (n < 2) return n;
  if (memo[n]) return memo[n];

  memo[n] = reverse(memo, n - 1) + reverse(memo, n - 2);
  return memo[n];
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 斐波那契数
  2. 2. 迭代+缓存
  3. 3. 递归+缓存