讲解

评价一个算法，不靠秒表——同样的代码在不同机器上耗时天差地别。我们用的是复杂度分析：不关心具体跑几秒，关心的是当输入规模 n 增长时，基本操作的次数如何增长。大 O 记号（Big O）描述的是增长的上界量级，忽略常数和低阶项：3n + 2 是 O(n)，2n² + 5n 是 O(n²)。忽略常数不是敷衍，而是因为 n 足够大时，增长阶数才是主导项。

常见的复杂度从好到坏排开：O(1) 常数（哈希表查找）、O(log n) 对数（二分查找）、O(n) 线性（一次遍历）、O(n log n)（高效排序）、O(n²) 平方（双重循环）、O(2ⁿ) 指数（全子集枚举）、O(n!) 阶乘（全排列）。记住一个直觉锚点：n = 10⁵ 时 O(n log n) 约 170 万次操作，轻松通过；O(n²) 是 100 亿次，必然超时。面试中拿到题目先根据数据范围反推可接受的复杂度，再倒选算法，这是性价比最高的应试技巧。

空间复杂度同理，衡量算法需要的额外内存。原地交换的排序是 O(1) 空间，递归调用的栈深度计入空间——深度为 n 的递归就是 O(n) 空间，这也是为什么递归层数过深会栈溢出。

还有两个进阶概念知道即可。均摊复杂度（amortized）：动态数组扩容一次要 O(n)，但摊到每次 push 上是 O(1)，因为扩容频率随大小指数下降；JS 数组的 push、哈希表的 rehash 都是均摊 O(1)。主定理（Master Theorem）：对 T(n) = aT(n/b) + f(n) 型的分治递归式给出复杂度公式——归并排序 T(n) = 2T(n/2) + O(n) 由它直接读出 O(n log n)。日常不推导，但看到分治结构要能估出量级。

示例

复杂度不是纸面概念，可以直接数出来。下面的代码对同一个问题（数组中是否有重复元素）实现了 O(n²) 的暴力解和 O(n) 的哈希解，并精确统计了基本操作次数：

import assert from 'node:assert/strict';

function containsDuplicateOn2(arr) {
  let ops = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      ops++;
      if (arr[i] === arr[j]) return { found: true, ops };
    }
  }
  return { found: false, ops };
}

function containsDuplicateOn(arr) {
  let ops = 0;
  const seen = new Set();
  for (const x of arr) {
    ops++;
    if (seen.has(x)) return { found: true, ops };
    seen.add(x);
  }
  return { found: false, ops };
}

const data = Array.from({ length: 1000 }, (_, i) => i);
const slow = containsDuplicateOn2(data);
const fast = containsDuplicateOn(data);

assert.strictEqual(slow.found, false);
assert.strictEqual(fast.found, false);
assert.strictEqual(slow.ops, (1000 * 999) / 2); // 499500 次比较
assert.strictEqual(fast.ops, 1000);

console.log('O(n^2) 暴力解比较次数:', slow.ops);
console.log('O(n) 哈希解查找次数:', fast.ops);
console.log('操作次数相差', slow.ops / fast.ops, '倍');

1000 个元素，暴力解比较了近 50 万次，哈希解只查了 1000 次——差距约 500 倍，而且 n 每扩大 10 倍，这个差距再扩大 10 倍。这就是增长阶数的威力：不是快一点，是快得不在一个世界。

常见坑

  • 把 O(2n) 写成 O(n) 时心理别扭：常数系数就是要扔掉，O(2n) 就是 O(n)，两段独立的线性遍历不是 O(n²)。
  • 嵌套循环不一定是 O(n²)：内层循环总迭代次数可能受外层约束（如滑动窗口中每个元素最多进出一次），总复杂度仍是 O(n)。
  • 忘记递归的空间开销：递归深度 n 意味着 O(n) 栈空间，写「空间 O(1)」的递归解法时要检查这一层。
  • 平均和最坏不分：哈希表查找平均 O(1) 最坏 O(n)，快速排序平均 O(n log n) 最坏 O(n²)。面试被追问时要答得上来。
  • 对着小数据谈优化：n = 20 时 O(n²) 和 O(n log n) 没有体感差别，先确认数据规模再决定优化优先级。

小结

复杂度用增长阶数而非秒表衡量；记住 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) 这条链和「数据范围反推复杂度」的技巧；均摊和主定理知道含义即可。下一章进入第一个实战模式：数组与双指针。