算法复杂度：大 O 记号到底在衡量什么

大 O 衡量的不是速度

这是最大的误解。大 O 描述的是当输入规模 n 增长时，运行时间的增长趋势，而不是具体快慢。

一个 O(n²) 的算法在 n=10 时可能比 O(n log n) 的算法更快，因为它常数项更小。大 O 关心的是 n 变大以后会发生什么。

常见量级的差别

这张表最有价值的读法是看差距：n=1000 时，O(n log n) 和 O(n²) 差了 100 倍。数据量再翻十倍，差距会变成 1000 倍。

为什么常数被忽略

大 O 只保留最高次项，并去掉系数：

3n² + 5n + 100  →  O(n²)

理由是在 n 足够大时，n² 项会完全主导。但「足够大」这三个字很关键——实际工程中的数据量往往不够大。

所以出现了两种算法时，不要只看量级，也要看常数。一个 O(n²) 但内层只有一次加法的算法，可能比 O(n log n) 但内层有大量对象分配的算法更快。

空间复杂度

时间之外还要看空间。通常两者可以互换：

// 时间 O(n²)，空间 O(1)：每次现算
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) { /* 计算 */ }
}

// 时间 O(n)，空间 O(n)：用哈希表换时间
const seen = new Map();
for (const item of list) { /* 查 seen */ }

在内存便宜的今天，绝大多数场景应该优先换时间。 但要注意递归的栈空间，深度过大会直接爆栈。

均摊复杂度

动态数组的「末尾追加」是 O(1) 还是 O(n)？答案是：单次可能 O(n)，均摊是 O(1)。

原因是扩容策略：容量不够时申请一块两倍大小的新空间并复制。复制那次是 O(n)，但它发生得越来越稀疏。把总成本摊到每次追加上，平均值是常数。

这个思路很有用：偶尔的昂贵操作可以接受，只要它不频繁。缓存失效、索引重建都属于这一类。

实际工程中的偏差

理论复杂度在真实环境里会遇到三个修正因素：

第一，CPU 缓存。 顺序访问连续内存比随机访问快得多。一个 O(n) 的数组遍历，实际可能比 O(log n) 的树查找还快——因为数组访问全部命中缓存，树查找要跳好几次内存。

第二，数据量小的时候，简单算法赢。 对小数组做插入排序（O(n²)）比归并排序（O(n log n)）快，这也是标准库的排序实现会先用插入排序处理小分区的原 因。所以「用更高级的算法」在数据量小的时候未必更快。

第三，输入分布影响巨大。 快排的平均复杂度是 O(n log n)，但对已排序数组（用最朴素的取首元素做基准）会退化成 O(n²)。理论上的「平均」和你的实际数据分布可能完全不同。

怎么用才实际

我的建议是分三层：

1. 先写出正确、清晰的实现，别急着优化
2. 测量，确认瓶颈真的在这里（大多数时候不是）
3. 只优化热点，并且优化后重新测量

不测量就优化，等于闭着眼睛改代码。而大多数性能问题的根源是「在循环里做了 I/O」或「重复查询数据库」，不是算法选错了。

小结

大 O 是有用的思维工具，它让你能预判「数据量涨十倍会怎样」。但它不是性能的最终裁判。

记住两句话：复杂度看趋势，性能看测量。两者都要，但不能互相替代。