3. 算法复杂度进阶：从大O表示法到实际测量
聊到算法复杂度，很多人第一反应就是大O表示法。嗯，这没错。但我在实际项目中见过太多人栽在「理论上快，实际慢」的坑里。今天我们就来把这个话题聊透。
3.1 大O表示法：你真的懂了吗？
大O表示法描述的是算法运行时间的增长趋势。它忽略常数因子和低阶项。比如 O(2n) 和 O(100n) 都写成 O(n)。
但这里有个关键点：大O只告诉你当 n 趋近无穷大时的行为。它不告诉你实际运行时间。
核心理解：大O是「渐近分析」，不是「精确计时」。
举个例子。我有个朋友优化排序算法，把 O(n²) 的冒泡排序换成了 O(n log n) 的快速排序。结果数据量只有 100 个，优化后反而慢了。为什么？因为快速排序的常数因子大，小数据量时劣势明显。
3.2 常见算法的时间复杂度
我整理了一张表，这些是我工作中反复用到的。
| 算法 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) |
| 二分查找 | O(1) | O(log n) | O(log n) |
| 哈希表查找 | O(1) | O(1) | O(n) |
注意看快速排序的最坏情况。我在项目中遇到过，当输入数据已经有序时，快速排序退化成 O(n²)。那次线上服务超时，查了半天才发现是数据分布问题。
3.3 空间复杂度：别只盯着时间
很多人优化算法只关心时间，忽略了空间。你想想看，内存不够用，程序直接崩了，时间再快也没用。
空间复杂度分析的是算法运行时占用的额外内存。比如：
- 原地排序（如冒泡排序）：O(1) 额外空间
- 归并排序：O(n) 额外空间
- 递归算法：调用栈深度决定空间复杂度
注意：递归深度过大可能导致栈溢出。我曾经在嵌入式设备上写递归快排，数据量一大就崩。后来改成迭代版本才解决。
3.4 常数因子陷阱：理论快不等于实际快
这是最容易被忽视的地方。大O相同，常数因子不同，实际性能可能差几倍甚至几十倍。
来看个具体例子。两种方式计算数组元素之和：
// 方式一：for循环
int sum1(int arr[], int n) {
int s = 0;
for (int i = 0; i < n; i++) {
s += arr[i];
}
return s;
}
// 方式二：递归
int sum2(int arr[], int n) {
if (n == 0) return 0;
return arr[n-1] + sum2(arr, n-1);
}两个算法都是 O(n)。但方式二慢得多。为什么？函数调用有开销。每次递归都要压栈、传参、返回。n=10000 时，方式二可能慢 10 倍以上。
我的建议：写代码时多想想「这行代码实际执行了多少条指令」。循环内的函数调用、内存分配、类型转换，都是隐藏的常数因子。
3.5 实际测量：用数据说话
理论分析完了，最终还是要跑一下。我习惯用以下步骤：
- 写基准测试：用不同规模的数据跑算法
- 记录时间：取多次运行的平均值
- 分析曲线：看时间随 n 增长的趋势
- 定位瓶颈：用 profiler 找出最耗时的部分
举个例子。我优化一个字符串匹配算法。理论上 KMP 算法 O(n+m) 比暴力匹配 O(n*m) 快。但实际测试发现，当模式串很短时，暴力匹配反而更快。因为 KMP 的预处理和状态机跳转有额外开销。
所以我的原则是：先理论分析，再实际测量，最后做决策。
3.6 避坑指南
这些年踩过的坑，分享给你：
- 别迷信大O：O(n²) 的算法在 n 很小时可能比 O(n log n) 快
- 注意缓存：内存访问模式影响巨大。数组遍历比链表遍历快得多，因为缓存友好
- 考虑输入特征：你的数据是随机的？有序的？还是重复的？不同输入影响算法表现
- 别忘了编译优化：编译器会做很多优化，比如循环展开、内联函数。写代码时要考虑这些
一句话总结：算法复杂度是工具，不是真理。用它指导方向，用测量验证结果。
好了，这一章就到这里。下一章我们聊聊实际项目中如何做性能调优，到时候我会分享一个我优化图像处理算法的完整案例。