时间复杂度和空间复杂度怎么分析？常见操作的复杂度是多少？

详细解析#

大 O 的含义和数据规模的直觉#

大 O 描述上界：3n² + 100n + 7 记作 O(n²)，n 足够大时，常数系数和低阶项对增长趋势的影响可以忽略。对数不写底数，log₂n 和 log₁₀n 只差常数倍。

最后一列是按"每秒执行约 10⁸ 次简单操作"这个粗略假设倒推的，只用来建立直觉，不同语言和机器差别很大。按这个假设，n = 10⁵ 时 O(n²) 是 10¹⁰ 次操作，要 100 秒左右，肯定超时；O(n log n) 只有约 1.7 × 10⁶ 次。所以题目给的 n 是 10⁵ 量级时，就该往 O(n log n) 或 O(n) 去想。

循环、递归和递归栈怎么算#

• 循环：顺序执行的部分相加取最大项，嵌套的部分相乘。内层次数不一定是 n：for (let i = 1; i < n; i *= 2) 只执行约 log n 次；j 从 i + 1 开始的两层循环执行 n(n-1)/2 次，仍是 O(n²)
• 递归：写出递推式，或者画递归树，总耗时 = 各层工作量之和

空间复杂度一般只算额外空间，输入本身不算。递归的每层调用占一个栈帧，空间至少是 O(最大递归深度)：朴素递归求斐波那契数总共调用指数级次，但同一时刻栈上最多 n 层，空间是 O(n)。ES2015 规范要求严格模式下做尾调用优化，但 V8（Chrome、Node.js）只在早期放在实验开关后面试过，没有正式上线，递归深度到 10⁴ 量级就可能报 RangeError: Maximum call stack size exceeded，深度可能很大时要改成循环或手动维护栈。

均摊分析：push 为什么是 O(1)#

动态数组底层预留了容量，满了就申请一块更大的内存，把旧元素搬过去。单次扩容是 O(n)，但容量按比例放大，越往后扩容越少。以每次翻倍为例，n 次 push 搬运的元素总数是 1 + 2 + 4 + … < 2n，平摊到每次 push 是 O(1)，这叫均摊 O(1)。实际扩容倍数由引擎决定，只要按比例扩容结论就成立；如果每次只多加固定的 10 个位置，总搬运量是 O(n²)，均摊就变成了 O(n)。

// 模拟 n 次 push，统计扩容时一共搬运了多少个元素
function countCopies(n, grow) {
  let capacity = 1
  let copies = 0
  for (let size = 0; size < n; size++) {
    if (size === capacity) {
      copies += size // 已有的 size 个元素全部搬到新内存
      capacity = grow(capacity)
    }
  }
  return copies
}
console.log(countCopies(1000, (c) => c * 2)) // 1023：小于 2n
console.log(countCopies(1000, (c) => c + 10)) // 49600：约 n² / 20

JS 常见操作的复杂度#

规范对大多数操作没有规定复杂度，下表是主流引擎的典型情况：

面试时怎么说复杂度#

1. 先给结论并说明变量含义："时间 O(n)，空间 O(n)，n 是数组长度"
2. 再给依据："只遍历一遍，每次 Set 操作平均 O(1)；最坏情况 Set 里存 n 个元素"
3. 多个输入规模分开写，如 O(m + n)、O(n · k log k)，不要随手合并成 O(n)
4. 有最好、最坏、均摊之分的主动说明，比如"快排平均 O(n log n)，最坏 O(n²)，随机选基准可以避免"
5. 从暴力解讲起，指出瓶颈再优化。比如判断数组有没有重复元素，两层循环是 O(n²)，瓶颈是"查之前有没有出现过"要 O(n)；用 Set 记录见过的值，查找降到 O(1)，整体 O(n)，代价是 O(n) 的额外空间。更多以空间换时间的例子见哈希表的典型应用

代码示例：斐波那契数的三种写法#

同一道题，写法不同，复杂度差别很大。朴素递归大量重复计算同一个子问题；记忆化让每个 n 只算一次；只依赖前两项，所以可以只保留两个变量。

// 朴素递归：时间 O(2ⁿ)，空间 O(n)（递归深度）
function fibNaive(n) {
  return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2)
}

// 记忆化递归：时间 O(n)，空间 O(n)（缓存 + 递归栈）
function fibMemo(n, memo = new Map()) {
  if (n < 2) return n
  if (!memo.has(n)) memo.set(n, fibMemo(n - 1, memo) + fibMemo(n - 2, memo))
  return memo.get(n)
}

// 迭代：时间 O(n)，空间 O(1)
function fib(n) {
  let prev = 0
  let curr = 1
  for (let i = 0; i < n; i++) [prev, curr] = [curr, prev + curr]
  return prev
}
console.log([fibNaive(10), fibMemo(10), fib(10)]) // [55, 55, 55]

面试官可能追问#

易错点#

• 循环里调用 includes、indexOf、shift、splice，看起来只有一层循环，实际是 O(n²)
• 递归只算了变量占的空间，漏了调用栈；记忆化递归是 O(n) 的缓存加 O(n) 的栈
• 多个输入规模混成一个 n，或者忽略字符串长度 k，比如对 n 个字符串分别排序是 O(n · k log k)
• 把 Map 的 O(1) 当成最坏情况的保证，它是平均复杂度