列表页上线第三天跑三秒。翻代码，没有明显慢查询，也没有死循环，只有一处「遍历订单、再遍历订单里的商品」。数据量从测试库的几百条变成线上的几十万条，这段代码的量级从毫秒跳到秒。
复杂度不是面试题，是写代码之前就能算出来的上限。算不出来，等于把性能交给上线后的运气。
1. 三个数：时间、空间、常数
| 维度 | 关注点 | 谁都容易漏 |
|---|---|---|
| 时间复杂度 | 操作次数随输入如何增长 | 增长阶前面的常数 |
| 空间复杂度 | 额外内存随输入如何增长 | 临时对象与装箱 |
| 实际常数 | 每次操作的真实代价 | 内存层级、序列化、网络往返 |
同样的 O(n)，一次是数组遍历，一次是每元素发一条 SQL，量级相同、耗时差几个数量级。工程上决定成败的经常是第三项，而它恰恰不在纸面复杂度里。
2. 量级换算：把操作次数换成时间
先建立换算直觉，再谈优化。下表是算术换算，单次耗时按实现量级取值，实际按机器与实现核对。
| 操作次数 | 每次 10 ns | 每次 100 ns | 每次 1 µs | 每次 1 ms |
|---|---|---|---|---|
| 10⁴ | 0.1 ms | 1 ms | 10 ms | 10 s |
| 10⁶ | 10 ms | 100 ms | 1 s | 17 min |
| 10⁸ | 1 s | 10 s | 100 s | 28 h |
读法：交互式接口的预算在百毫秒量级，那么「10⁶ 次、每次 1 µs」就已经越线；「10⁸ 次、每次 1 ms」不是优化能救的，得改设计。后台任务按分钟级预算，同一份代码就可以接受。
单次操作的经验量级（按实现核对）：
内存数组访问 纳秒级
HashMap 查找 百纳秒级
一次本地 SQL 几十微秒到毫秒级
一次跨机房调用 毫秒级
3. 嵌套循环：识别与合并的真实收益
| 形态 | 操作次数 | 10³ 输入 | 10⁵ 输入 |
|---|---|---|---|
| 单层遍历 | n | 10³ | 10⁵ |
| 双层嵌套 | n² | 10⁶ | 10¹⁰ |
| 双层 + 内层查找 | n·m | 10⁶ | 10¹⁰ |
| 建索引后单层 | n + m | 2×10³ | 2×10⁵ |
// 差：每个订单都扫一遍商品表
for (Order o : orders) {
for (Item i : items) {
if (i.orderId().equals(o.id())) { o.add(i); }
}
}
// 好：一次分组，之后是 O(1) 查找
Map<Long, List<Item>> byOrder = items.stream()
.collect(Collectors.groupingBy(Item::orderId));
for (Order o : orders) {
o.addAll(byOrder.getOrDefault(o.id(), List.of()));
}
注意区分两种「合并」：把同一集合的两次遍历合成一次，只是常数减半，不改变量级；把内层循环换成哈希索引，才是量级变化。前者值得做但不值得庆祝，后者才是设计层面的决策。
4. N+1 与批量化：差距是量级
| 做法 | 往返次数 | 十万行时的量级 |
|---|---|---|
| 逐条查询 | n | 毫秒级 × 10⁵ |
IN 批量 |
n/批大小 | 毫秒级 × 批次 |
| 一次 join | 1 | 单次往返 + 传输 |
// N+1 的典型写法：循环里调 mapper
for (Long id : ids) { result.add(mapper.selectById(id)); }
// 批量：一次拿回，再在内存里对齐
List<User> users = mapper.selectByIds(ids); // 注意 IN 列表长度上限
差距不是「快三倍」，是从一次往返变成十万次往返。批量的代价是 IN 列表长度、结果集内存占用、以及 SQL 长度上限，这些都要设边界。
5. 排序放在哪：一次排序换多次查找
| 方案 | 总代价（n 条数据，m 次查询） | 适用 |
|---|---|---|
| 每次查询线性扫 | m·n | m 很小、n 也很小 |
| 先排序，再二分 | n log n + m log n | m 较大、数据静态 |
| 建哈希索引 | n + m | 只做等值查找 |
| 交给数据库索引 | 一次 B+ 树查找 | 数据在库里，别捞到内存里排 |
// 排序一次，查询多次
List<Item> sorted = items.stream()
.sorted(Comparator.comparing(Item::price)).toList();
int idx = Collections.binarySearch(sorted, key, comparator);
顺序反了就是灾难：在循环里对同一个列表反复 sort，等于把 n log n 乘上 m。识别方法是看 sort、filter、stream() 是否出现在循环体内。
6. 空间换时间的边界
缓存不是免费的加速器，它把「计算」换成「内存 + 命中率」。
| 命中率 | 净效果 | 结论 |
|---|---|---|
| 九成以上 | 明显收益 | 值得做，注意失效策略 |
| 一半左右 | 收益被维护成本吃掉一半 | 先看能否预计算 |
| 一成以下 | 多数请求仍然穿透 | 缓存只是增加了一层延迟 |
容量估算：10⁶ 条 × 200 字节 ≈ 200 MB 量级
堆预算 2 GB → 单这一份缓存已占一成，且是长期驻留
对象头、包装类型、Map 结构本身还要再加几成
判断标准是收益 = 命中率 × 单次节省 − 维护成本。维护成本包括失效逻辑、内存压力、GC 停顿，以及「缓存和数据库不一致」这类只有半夜才出现的故障。
7. 数据结构速查与三个常见误记
| 操作 | 数组 | 链表 | HashMap | 平衡树 |
|---|---|---|---|---|
| 按下标访问 | O(1) | O(n) | — | — |
| 查找 | O(n) | O(n) | O(1) 期望 | O(log n) |
| 已知位置插入 | O(n) | O(1) | O(1) 期望 | O(log n) |
| 有序遍历 | 需排序 | 需排序 | 无序 | O(n) |
三处误记：链表中间插入仍是 O(n)，因为要先走到那个位置；HashMap 的 O(1) 是期望值，哈希冲突严重或扩容时会退化；数组尾部追加的均摊 O(1) 在扩容那一次是 O(n)，实时性要求高的路径要预分配。
8. 递归的栈深与记忆化的收益
// 栈深 ≈ 递归层数，默认栈在几百 KB 到 1 MB 量级（按 -Xss 与平台核对）
// 每帧几十到几百字节 → 深度到万级就有 StackOverflowError 风险
// 深递归改迭代，或显式用栈
记忆化把指数级递归压成多项式，前提是子问题重叠。没有重叠的递归加缓存，只是多了一次哈希查找和一份内存占用；有重叠但不设上限，缓存会随输入无限增长。
9. 并发不改变单次操作的复杂度
| 手段 | 改变了什么 | 没有改变什么 |
|---|---|---|
| 多线程 | 墙钟时间，接近核数倍 | 总操作次数、单次代价 |
| 批量化 | 往返次数 | 单条数据的处理成本 |
| 缓存 | 命中路径的代价 | 未命中路径的代价 |
| 加机器 | 吞吐上限 | 单请求延迟 |
把 O(n²) 的循环丢进线程池，仍然是 O(n²) 次操作，只是分摊到多个核；一旦共享锁、连接池或下游限流成为瓶颈，加速比会远低于核数。先降量级，再谈并行，顺序反了就是花钱买复杂度。
10. 十倍推演：估算模板
上线前问一句「数据翻十倍会怎样」，比任何 profiling 都便宜。
输入 n = 10^6，单请求处理 k = 20 条
内层查找 2 次/条 → 4×10^7 次操作
单次 100 ns → 4 s
接口预算 200 ms → 超 20 倍
结论：必须先建索引或预聚合，调参无效
估算三步：数操作次数 → 乘单次量级 → 与预算比。留三到五倍余量，因为序列化、GC、锁竞争都不在纸面模型里。估算的精度不重要，数量级对了就足以否决一个设计。
11. 排错：五种「优化了还是慢」
| 现象 | 原因 | 处理 |
|---|---|---|
| 加了缓存更慢 | 命中率低，序列化与网络开销照付 | 先测命中率，再决定去留 |
| 理论 O(n) 实测像平方 | 循环体内有隐藏遍历（contains、sort、字符串拼接） |
逐行找集合操作 |
| 扩容后延迟没降 | 瓶颈在单请求内部，不在并发度 | 看单请求耗时分解 |
| 分页仍慢 | 偏移分页要求数过前面所有行 | 改键集分页或限制页深 |
| CPU 不高但很慢 | 等 IO、等锁、等下游 | 看阻塞而非看火焰图 |
12. 边界：什么时候不该做复杂度优化
| 场景 | 结论 | 理由 |
|---|---|---|
| 数据量稳定在千级 | 不优化 | 常数项与可读性更重要 |
| 框架已内建索引 | 不重复造 | 先确认它做了什么 |
| 瓶颈在 IO 或网络 | 优先改交互次数 | 降复杂度不减少往返 |
| 一次性脚本 | 不优化 | 生命周期短于优化成本 |
| 已被业务规则限流 | 不优化 | 上游根本打不满 |
复杂度优化解决的是「随规模增长而恶化」的问题。规模不增长、瓶颈不在计算，优化只会增加代码的维护面。
13. 自测
- 为什么「纸面同阶、实测差十倍」在工程上是常态？
- 把同一集合遍历两次合并成一次，改变的是量级还是常数？
- N+1 查询的差距为什么用「量级」描述而不是「倍数」？
- 在循环里对同一列表反复排序，代价会变成什么？
- 缓存命中率一成时，为什么说它只是增加了一层延迟？
- 什么时候该先降量级，而不是先加线程？