写了两章代码，现在回答关键问题：怎么证明你的算法快？ 靠秒表？不靠谱——机器不同、心情不同。本章教你用数学给算法「体检」📊。
📈 七种函数：算法界的常住人口
几乎所有算法的运行时间都由这 7 个函数描述，从快到慢：
| 函数 | 昵称 | 直观感受（n=100万） |
|---|---|---|
| 1 | 常数 | 眨眼间 ✨ |
| log n | 对数 | 约 20 步 |
| n | 线性 | 100 万步 |
| n log n | 线性对数 | 约 2000 万步 |
| n² | 平方 | 1 万亿步 😱 |
| n³ | 立方 | 宇宙热寂级别 |
| 2ⁿ | 指数 | 直接放弃治疗 |
对数 log n 是算法界的超级明星：n 翻倍，它只加 1。二分查找、平衡树、堆——凡是对数级的，都是好文明 🌟。
🎯 大 O：只看增长趋势
大 O 记号回答一个问题：当 n 变大时，运行时间的增长有多快？
// 例：数组最大值
int findMax(int a[], int n) {
int best = a[0];
for (int i = 1; i < n; i++) // 循环 n-1 次
if (a[i] > best) best = a[i];
return best;
}
循环体执行 n-1 次，每次 O(1) → 总时间 O(n)。
三条实用规则：
- 顺序相加取最大：O(n) + O(n²) = O(n²)（龟兔赛跑，乌龟说了算）；
- 嵌套相乘：两层各 n 次的循环 = O(n²)；
- 常数和低阶项统统扔掉：3n² + 5n + 2 → O(n²)。为什么敢扔？因为我们比较的是「增长曲线的形状」，不是具体数值——n 足够大时，n² 甩开其他项 N 条街。
三个记号的分工（考试常考 ⚠️）：
- O(f(n))：上界——「最多也就这么慢」（最坏情况分析最常用）；
- Ω(f(n))：下界——「至少这么快不了」；
- Θ(f(n))：上下界夹死——「就是这个量级」。
举例：快速排序最坏 O(n²)，最好 Ω(n log n)，平均情况 Θ(n log n)。三个记号说的是不同的问题，别混着用 🙃。
🔍 证明技巧三件套
- 反例法（counterexample）：想证明「所有 A 都 B」？找出一个不满足的，一枪毙命；
- 反证法（contradiction）：假设命题不成立 → 一路推理 → 撞上矛盾 → 原命题成立；
- 归纳法（induction）：证明 n=1 成立（基础），假设 n-1 成立推出 n 成立（归纳步）→ 全体成立。递归算法的正确性分析几乎都靠它。
🎯 本章通关清单
- [ ] 把 7 个函数按增长速度排序，并说出 n=100 时的实际量级
- [ ] 给嵌套循环代码算出大 O
- [ ] 区分 O / Ω / Θ 各自在描述什么
- [ ] 会用归纳法证明一个简单结论
有了尺子，下一章的栈和队列就能科学比较了 🥞