算法复杂度实战与收尾

十篇走到最后。前面我们学了数组、链表、栈队列、树与平衡树、哈希、堆、图、并查集、排序——每一个都挂着一串 O(...)。可"复杂度"不是背结论，而是拿到一段代码或一道题，能亲手算出来、能选对数据结构。本篇把散落的工具收拢：怎么解递归式（主定理）、均摊分析回顾、以及一个"看到需求就选结构"的决策表。这是 CS61B 的收官，也是把前面九篇拧成肌肉记忆的一课。

---

一、实战：看到代码，算出复杂度

1.1 循环套循环

for (int i = 0; i < n; i++)        // n 次
    for (int j = 0; j < n; j++)    // 每次 n 次
        sum += a[i] * b[j];

外层 n、内层 n → O(n²)。

1.2 循环减半（二分、堆下沉）

for (int i = n; i > 0; i /= 2) process(i);   // 每次规模 /2

i 走 n → n/2 → n/4 → … → 1，共 log₂ n 步 → O(log n)。

坑①：log 的底数在 O 记号里不重要——log₂ n、log₁₀ n 只差常数倍，统一写作 O(log n)。别纠结底数是 2 还是 e。

---

二、主定理（Master Theorem）：一眼看穿分治

对形如 T(n) = a·T(n/b) + f(n) 的递归（a 个子问题、规模 n/b、合并代价 f(n)），比较 f(n) 与 n^(log_b a)：

情形	条件	结论
①	f(n) = O(n^(log_b a − ε))	T(n) = Θ(n^(log_b a))
②	f(n) = Θ(n^(log_b a) · log^k n)	T(n) = Θ(n^(log_b a) · log^(k+1) n)
③	f(n) = Ω(n^(log_b a + ε)) 且正则	T(n) = Θ(f(n))

实战速查：

• 归并排序：a=2, b=2, f(n)=Θ(n) → n^(log₂2)=n，情形② → Θ(n log n)。
• 二分查找：a=1, b=2, f(n)=Θ(1) → n^(log₂1)=1，情形② → Θ(log n)。
• 普通矩阵乘法分治（strassen 之前）：a=8,b=2,f=Θ(n²) → n³ vs n²，情形① → Θ(n³)。

坑②：主定理只覆盖"子问题规模相等"的规整分治。像快排（规模不固定）就不直接适用，要用期望分析或递归树。

---

三、均摊分析：单次贵，长期便宜

动态数组插入、斐波那契堆，都靠"偶尔花大钱、平时几乎免费"来摊薄。回顾记账法看动态数组翻倍：

• 每次 add 收 3 元：1 元付"写入自己"，1 元留给"未来被拷贝时搬自己"，1 元帮"最老那个曾填满的数组"付搬迁费。
• 这样每次操作"预付"的余额永远够付下一次扩容，均摊 O(1)——尽管某次扩容本身是 O(n)。

本质一句话：均摊分析算的是"一连串操作的平均单价"，不是单次最坏。哈希扩容、splay 树都靠它站得住。

---

四、决策表：看到需求，选对结构

这是 CS61B 全篇的"总纲"——把十篇拧成一张查表：

---

五、CS61B 全篇回顾：一条主线

把十篇串起来，CS61B 其实只回答一个问题："怎么组织数据，让操作足够快？"

篇	结构	解决的核心矛盾
01 数据结构导论	ADT	接口与实现的分离
02 数组与动态数组	动态数组	定长 vs 可增长，均摊
03 链表	单/双链表、哨兵	连续内存 vs 灵活插入
04 栈与队列	线性结构	LIFO vs FIFO
05 树与平衡	BST/AVL/红黑/B树	有序 + O(log n) 插入
06 哈希表	散列 + 冲突处理	任意键 O(1) 查找
07 堆	完全二叉树	只取极值 O(1) peek
08 图	邻接表/矩阵 + 遍历	网络关系与最短路
09 并查集与排序	集合 + O(n log n)	连通性 + 全序
10 复杂度与收官	主定理/均摊/决策	会算、会选

本质一句话（CS61B 收官）：数据结构不是死记的清单，而是一组"用某种代价换另一种代价"的权衡工具箱——先看清你要的是"查找 / 极值 / 有序 / 连通 / 全序"哪一种，再按决策表取对应的那一件。

---

六、小结

• 是什么：复杂度是"能算出来"的技能（循环计数、主定理、均摊），不是背答案。
• 坑：O(log n) 不关心底数；主定理只管规整分治；均摊看长期单价而非单次最坏。
• 本质一句话：CS61B 的全部努力，都是为了让你在写代码前先问一句"我的操作主要是什么、希望能多快"——然后选对那一个结构。十篇到此收官，但"权衡"这条主线会贯穿你之后的每一门课。