主题
界面
时间复杂度和空间复杂度
1. 本节定位
《数据结构：数组、链表、栈与队列》 与 《树、堆与哈希表》 讲了数据结构；本节讲衡量它们的尺子：
text
数据结构：能装什么、怎么取
复杂度： 取一次要花多少代价 ← 本节复杂度是"忽略常数、只看增长趋势"的抽象 ✓ ——本节的实测就是让这个抽象落到真实的时间上 ✓
2. 学习目标
- 能写出常见操作的复杂度，并说出"为什么忽略常数项" ★★★；
- 能看着一段代码说出它的复杂度 ★★★；
- 知道 O(n²) 在什么规模会"突然不可用" ★★★（实测数据）；
- 理解"均摊复杂度"与最坏复杂度的区别 ★★★；
- 知道空间换时间的典型做法与代价 ★★；
- 知道微基准测试的三个陷阱 ★★。
3. 前置知识检查
- 知道数组与链表的随机访问差异吗？（《数据结构：数组、链表、栈与队列》）✓
- 会写循环与递归吗？✓
4. 为什么需要这个知识
先看一段"能跑但会被线上流量打死"的代码 ✗：
java
// 看起来人畜无害：判断列表里有没有重复
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
if (list.get(i).equals(list.get(j))) { return true; }
}
}★ 本节的实测数据会告诉你它有多危险：
text
n=1000 → 4 ms （测试环境：毫无感觉）
n=10000 → 43 ms （还行）
n=30000 → 340 ms （开始慢）
n=100000 → 536 ms （一次调用半秒）✗✗★ 换成 HashSet 之后（O(n)）：
text
n=1000 → 5 ms
n=100000 → 5 ms ← 规模涨 100 倍，耗时不变 ✓✓这就是复杂度的现实意义：它决定了你的代码"能撑到多大规模" ✓✓
5. 核心概念
5.1 大 O 看的是增长趋势 ★★★
为什么忽略常数：
| 写法 | 真实耗时 | 大 O |
|---|---|---|
for (i = 0; i < n; i++) sum += i; | n 次加法 | O(n) |
for (i = 0; i < n; i++) { a(); b(); c(); } | 3n 次操作 | 还是 O(n) ✓ |
★ 因为常数在 n → ∞ 时被增长项淹没 ✓ ——而"哪个增长项"才是决定性的 ✓
★ 但要记住一件事 ✗：
大 O 只说"增长趋势"，不说"绝对快慢" ✓✓
O(n) 的算法常数很大时，在小 n 上可能慢于 O(n log n) ✓（本节的实测里就有这种情况）✓
5.2 四条增长曲线的实测 ★★★
实测输出（ComplexityLesson，单位 ms，取较大规模档）：
text
n O(1) O(log n) O(n) O(n log n)
100 万 1 1 2 8
1000 万 1 1 3 167★ 注意最后一列：n 涨到 10 倍，O(n log n) 涨了约 20 倍 ✓ ——因为 log 也在涨 ✓ 而 O(1) 与 O(log n) 从 100 万到 1000 万几乎没动 ✓✓
★ 关键观察：
| 曲线 | 观察 |
|---|---|
| O(1) ★ | 与 n 完全无关——不管 n 是 1 万还是 1000 万，耗时都是常数 ✓ |
| O(log n) ★★★ | 从 1 万到 1000 万，只从 14 次循环变成 24 次 ✓✓ |
| O(n) | 线性增长 ✓ |
| O(n log n) | 在 1000 万时才显出明显成本 ✓ |
★ O(log n) 的意义（这条最值得记住）：
text
1 千 → 约 10 次比较
1 百万 → 约 20 次比较
10 亿 → 约 30 次比较 ← 只多了 10 次 ✓✓对数级别的算法，几乎"不受数据规模影响" ✓✓
这就是索引、二分、跳表、B+ 树的价值 ✓
5.3 O(n²) 的"突然不可用" ★★★
实测输出：
text
n O(n²) ms O(n log n) ms 倍数
1000 4 5 0.8 ← 小规模时反而更快！
3000 4 2 2.0
10000 43 4 10.8
30000 340 6 56.7
100000 536 5 107.2 ← 差两个数量级 ✗✗★ 三点观察：
| 观察 | 说明 |
|---|---|
| n=1000 时 O(n²) 反而"更快" ★★ | 常数项占主导 ——教科书里的"O(n²) 更慢"在小规模上不成立 ✓ |
| n 翻 3 倍，O(n²) 涨约 9 倍 ★★★ | 这就是"平方"的含义 ✓ |
| n=10 万时差 107 倍 ✗✗ | "能跑"与"不能用"的分界 ✓ |
★ 工程判据（可以直接用）：
| 复杂度 | 可接受的 n |
|---|---|
| O(n²) ★ | n < 1 万（再大就要几百毫秒）✗ |
| O(n log n) ✓ | n 到千万级都没问题 ✓ |
| O(n) ✓✓ | n 到亿级 ✓ |
| O(log n) ✓✓✓ | n 几乎无上限 ✓ |
★ 一个重要推论：
"这个数据量很小，O(n²) 没关系"这句话，必须配上"并且它不会增长" ✓✓
今天 1000 条、明年 10 万条的业务，一开始就该写成 O(n) ✓
5.4 均摊复杂度：ArrayList.add 为什么敢叫 O(1) ★★★
实测输出：
text
连续 add 10000000 个元素：总耗时 492 ms（平均每个约 49.2 ns）
其中**最慢的单个 add** 耗时约 38.19 ms ← 扩容那一次★ 单次最慢 38 ms，平均却只要 49 ns ✓✓ ——差了 78 万倍 ✗
这是怎么成立的：
text
第 1 次扩容：复制 10 个元素
第 2 次扩容：复制 15 个
第 3 次：22 个
... 按 1.5 倍增长
总复制次数 ≈ 10 + 15 + 22 + ... ≈ 3n ← 常数倍！
所以摊到每次 add，还是 O(1) ✓★ 关键在"增长比例" ✓：
| 扩容策略 | 均摊复杂度 |
|---|---|
| 每次 +1（容量固定增量）✗✗ | O(n) ——每次都要复制全部 ✗ |
| 每次 ×1.5 / ×2 ★★★ | O(1) ✓✓ |
★ 工程启示：
如果能预估容量，用
new ArrayList<>(expectedSize)✓不是为了"减少复制"（那本来就是均摊常数），而是为了消除那 38 ms 的"抖动" ✓✓
对延迟敏感的服务，一次 38 ms 的停顿就足以触发一次超时 ✗
5.5 空间换时间 ★★
实测输出：
text
朴素递归 fib(40)：485 ms（结果 102334155）
记忆化递归 fib(40)：0 ms（结果 102334155）
多用了 41 个 long（约 328 字节）缓存★ 328 字节换掉了 485 毫秒 ✓✓ ——收益高得离谱 ✓
★ 它的原理：朴素递归把同一个子问题算了无数遍 ✗
text
fib(40) 会算 fib(38) 两次、fib(37) 三次、fib(36) 五次……
调用次数就是 2^n 量级（S2-006 的实测：fib(34) 要 1845 万次调用）空间换时间的三种常见形态：
| 形态 | 例子 | 代价 |
|---|---|---|
| 缓存（Memoization） ★★ | 记忆化递归、Map 缓存 | 内存 + 失效逻辑 ✓ |
| 预计算 / 打表 ★ | 素数表、查找表 | 启动时间 + 内存 ✓ |
| 索引 ★★★ | 数据库索引、倒排索引 | 写入变慢 + 存储（《MySQL 性能优化基础》）✓ |
★ 但空间不是免费的 ✗：
缓存会带来"一致性"问题（《缓存一致性与更新策略》）✓
索引会让"写"变慢（《MySQL 性能优化基础》 实测过：写入 988 → 1364 ms）✓
所以"空间换时间"必须算总账，不是无条件加缓存 ✓✓
5.6 微基准测试的三个陷阱 ★★
本节的实验自己就踩到了其中一个 ✓ ——所以这一节很实在 ✓
| # | 陷阱 | 表现 |
|---|---|---|
| ① 不预热 ★★★ | 前几次是解释执行 ——测到的是"JIT 编译过程" ✗ | 数据波动大、偏慢 |
| ② 常数项淹没差异 ★★ | n 太小时，O(n) 与 O(n log n) 都是 1 ms ✗ | 看不出差异（本节的"四条曲线"就出现了）✓ |
| ③ 死代码消除 ★★ | JIT 发现结果没被使用，直接把循环删掉 ✗✗ | 测出 0 ms ✓ |
★ 本项目的处理方式（可以直接抄）：
java
/** 基准黑盒：只写不读，用于阻止 JIT 优化掉被计时的循环 */
@SuppressWarnings("unused")
private static long sink; // ★ 把结果写进一个"看起来有用"的静态变量
private static void linearOp(int n) {
long sum = 0;
for (int i = 0; i < n; i++) { sum += i; }
sink += sum; // ★ 防止 JIT 把整个循环优化掉
}★ 加上"预热"与"放大规模"：
java
// 预热：先跑几轮，让 JIT 编译热点代码
for (int round = 0; round < 3; round++) { consume(list); }
// 再正式计时
long elapsed = timeOf(() -> consume(list));★ 一条务实的建议：
除非真的需要精确基准，否则不要自己写微基准 ✗
用 JMH（Java Microbenchmark Harness） ✓（《LeetCode 刷题方法与 Java 解题模板》 会提到）✓
但"看懂复杂度"这件事，不需要微基准也能做 ✓✓
6. 递进示例
6.1 最小示例：判断复杂度
java
// O(n)：一层循环
for (int i = 0; i < n; i++) { ... }
// O(n²)：两层嵌套（都与 n 相关）
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ... } }
// O(log n)：每次把范围减半
for (int i = 1; i < n; i *= 2) { ... }
// O(n log n)：外层 n 次，内层每次是 log 量级
for (int i = 0; i < n; i++) { for (int j = 1; j < n; j *= 2) { ... } }6.2 业务示例：用 Set 把 O(n²) 降到 O(n)
java
// ✗ O(n²)
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] == a[j]) { return true; }
}
}
// ✓ O(n)
Set<Integer> seen = new HashSet<>();
for (int value : a) {
if (!seen.add(value)) { return true; } // add 返回 false 说明已存在
}6.3 反例：n=100 就断言"O(n²) 没问题"
问题在于"n 会不会增长" ✗ ——业务数据总是会增长的 ✓
7. 完整可运行代码与实测
代码：labs/cs-basics/src/main/java/cn/kb/learn/cs/ComplexityLesson.java
运行：
powershell
cd labs
.\mvnw.cmd -pl cs-basics compile
java "-Dstdout.encoding=UTF-8" -cp cs-basics/target/classes cn.kb.learn.cs.ComplexityLesson实测输出（节选，真实运行）：
text
===== 2. O(n²) vs O(n log n)：什么时候「突然不能用了」=====
n O(n²) ms O(n log n) ms 倍数
1000 4 5 0.8
3000 4 2 2.0
10000 43 4 10.8
30000 340 6 56.7
100000 536 5 107.2
===== 3. 空间换时间：缓存的收益与代价 =====
朴素递归 fib(40)：485 ms（结果 102334155）
记忆化递归 fib(40)：0 ms（结果 102334155）
===== 4. 均摊复杂度：为什么 ArrayList.add 敢叫 O(1) =====
连续 add 10000000 个元素：总耗时 492 ms（平均每个约 49.2 ns）
其中**最慢的单个 add** 耗时约 38.19 ms ← 扩容那一次★ 三条可以直接写进评审清单的结论 ✓：
| # | 结论 | 依据 |
|---|---|---|
| ① | n 过万的两层循环必须改写成哈希/排序方案 | 10 万时差 107 倍 ✗ |
| ② | "缓存换时间"的收益常是数量级，但要算一致性的账 | 328 字节 vs 485 ms ✓ |
| ③ | 对延迟敏感的服务，要预估 ArrayList/HashMap 容量 | 单次扩容 38 ms ⚠️ |
★ 一个诚实的说明："四条曲线"那一组在较小规模上全是 1 ms ✗ —— 因为达到毫秒精度的下限了 ✓ ——这不是测量失败，而是"常数项淹没差异"的真实体现 ✓✓（5.6 陷阱②）
8. Debug 观察点
- 把"四条曲线"的 n 再放大 10 倍：观察 O(n log n) 终于拉开 ✓；
- 去掉
sink +=那一行：观察某些实验直接变成 0 ms（死代码消除）★★； - 去掉预热循环：观察第一次运行明显更慢 ★；
- 把
HashSet版本与双层循环版本跑同一个 n：亲手量出 O(n) 与 O(n²) 的差距 ✓； - 用
-Xint跑：所有数字都变慢，但相对关系不变 ✓（复杂度是"关系"，不是"绝对值" ✓）。
9. 常见错误
| # | 错误 | 说明 |
|---|---|---|
| 1 | 以为 O(n) 一定比 O(n log n) 快 ✗ | 小规模时常数项主导（5.3）✗ |
| 2 | 用"数据量小"为 O(n²) 辩护 ✗✗ | 数据会增长 ✓ |
| 3 | 微基准不预热 ✗✗ | 测到 JIT 编译过程（5.6①）✗ |
| 4 | 微基准没有"防死代码消除" ✗✗ | 测出 0 ms 还以为是"优化成功" ✓ |
| 5 | 以为"均摊 O(1)"意味着"每次都快" ✗✗ | 偶发的 38 ms 抖动是真实的 ⚠️ |
| 6 | 无条件加缓存 ✗ | 一致性与内存成本也要算（5.5）✗ |
| 7 | 把复杂度当成"精确的耗时预言" ✗ | 它只说增长趋势 ✓ |
10. 动手实验
目标：亲手量出"复杂度决定可用规模"这条结论。
步骤：
- 跑
ComplexityLesson，记录 O(n²) 与 O(n log n) 在各档的倍数 ✓； - 自己写一个"列表查重"：分别用双层循环与
HashSet，在 n=1000 / 10000 / 100000 上对比 ★★； - 画出（或列出）两者的增长曲线 ✓；
- 算出"如果数据再涨 10 倍会怎样"（提示：O(n²) 会涨 100 倍）★；
- 给
ComplexityLesson加一个"n=100 万的双层循环"（估计跑几分钟）——体会"不能用"是什么感觉 ⚠️。
验收方式：能说出"你的业务数据涨 10 倍时，这段代码会变成多少毫秒"。
扩展任务：用 JMH 重做一次本节的微基准：
- 加依赖
org.openjdk.jmh:jmh-core与jmh-generator-annprocess✓； - 用
@Benchmark与@Warmup注解 ✓； - 对比"自己写的计时"与 JMH 的结果差异 ★；
- 说明：JMH 帮你处理了哪些陷阱（提示：预热、死代码消除、JIT 分层、统计置信区间）✓
11. 练习题
- 判断：O(n) 的算法一定比 O(n log n) 快。（对 / 错）
- 填空：n 翻 3 倍时，O(n²) 的耗时约涨 ______ 倍，O(n) 约涨 ______ 倍。
- 简答：
ArrayList.add单次最慢要 38 ms，为什么还说它是 O(1)？ - （代码阅读）
java
Map<String, List<Order>> byUser = new HashMap<>();
for (Order a : orders) {
for (Order b : orders) {
if (a.getUserId().equals(b.getUserId())) { ... }
}
}这段代码的复杂度是多少？如果 orders 有 10 万条会怎样？怎么改？ 5. （编程）写一个方法，判断数组里是否存在两个数之和等于目标值：
- 先用双层循环实现（O(n²)）✓；
- 再用
HashSet实现（O(n)）✓； - 在 n=10 万上对比耗时 ★。
参考答案（要点）
- 错。常数项在小规模时会主导 ✓（本节的实测：n=1000 时 O(n²) 反而是 5 ms vs 4 ms）✓★
- 约 9 倍（平方）；约 3 倍（线性）✓
- 因为扩容按 1.5 倍增长，总复制次数是 O(n) 级别 ✓ ——摊到 n 次 add 上仍是常数 ✓ 但要记住：偶发的长停顿是真实的 ⚠️（5.4）
- O(n²) ✗ ——10 万条会跑几百毫秒到几秒 ✗ 改法：用一次遍历 +
Map分组 ✓（O(n)）✓ - 要点：
- 双层循环：
for i, for j > i, if (a[i]+a[j]==target) return true;✓ - 哈希：遍历时判断
set.contains(target - value)✓ - 对比结果：O(n²) 在 10 万上要几百毫秒，O(n) 只要几毫秒 ✓
- 双层循环：
12. 掌握标准
- [ ] 能看着代码说出复杂度 ★★★；
- [ ] 知道"忽略常数"的含义与它的边界（小规模时常数主导）★★★；
- [ ] 知道 O(n²) 的可用规模上限（n < 1 万） ★★★；
- [ ] 理解均摊复杂度，并知道偶发抖动是真实的 ★★★；
- [ ] 知道空间换时间的三种形态与各自的代价 ★★；
- [ ] 知道微基准的三个陷阱，并且会用
sink防死代码消除 ★★； - [ ] 知道 JMH 的存在与它能解决什么 ✓。
13. 扩展资源
14. 下一步学习
《LeetCode 刷题方法与 Java 解题模板》：把复杂度分析用在解题上。
进度只保存在本机浏览器，可随时清除