[!info] related notes

• 所属 MOC: 算法面试题型 MOC, 算法面试模式 MOC
• 前置概念: [[algo/recursion|递归]], [[algo/dp|动态规划]]
• 并列概念: 回溯算法

斐波那契

这篇笔记回答一个问题：斐波那契数列有哪些实现方式，以及面试中哪种最稳。

题目

斐波那契数列定义为 F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)（n >= 2）。求 F(n)。

实现方式

1. 纯递归（不推荐）

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

时间复杂度 O(2^n)，大量重复计算，面试直接说”会超时”。

2. 记忆化递归

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

时间复杂度 O(n)，空间复杂度 O(n)。

3. 迭代（面试推荐）

function fib(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

时间复杂度 O(n)，空间复杂度 O(1)。面试最稳的写法。

4. 动态规划

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

时间复杂度 O(n)，空间复杂度 O(n)。可以优化为 O(1) 空间。

常见边界

• n = 0 返回 0
• n = 1 返回 1
• n 很大时注意整数溢出（JS 中 Number.MAX_SAFE_INTEGER 是 2^53 - 1，fib(78) 就超了）

最小例子

fib(0);  // 0
fib(1);  // 1
fib(2);  // 1
fib(3);  // 2
fib(10); // 55

Related notes

• 前端工程化MOC
• 前端基础MOC
• CSS MOC
• ECMAScript MOC