23. 算法优化：选择合适的时间复杂度、空间换时间策略、近似算法
算法优化这事儿，说白了就是「用更少的资源，干更多的活」。我见过太多团队，上来就撸代码，跑起来发现慢得像蜗牛，回头一看——算法选错了。嗯，今天咱们就聊聊怎么把算法这块硬骨头啃下来。
23.1 时间复杂度：选对算法，事半功倍
时间复杂度不是玄学，它是你代码性能的「天气预报」。你想想看，一个 O(n²) 的算法，数据量从 100 涨到 1000，执行时间直接飙 100 倍。这谁顶得住？
核心原则：在满足业务需求的前提下，优先选择更低时间复杂度的算法。
我在项目中遇到过这么个事：一个日志分析模块，要统计用户访问频次。同事用了两层循环去匹配，数据量才 5000 条，跑了 3 秒多。我换成哈希表，O(n) 搞定，0.02 秒完事。你看，这就是选对算法的威力。
常见的时间复杂度对比：
| 复杂度 | 代表算法 | 数据量 1000 时 | 数据量 10000 时 |
|---|---|---|---|
| O(1) | 哈希查找 | 瞬间 | 瞬间 |
| O(log n) | 二分查找 | 约 10 步 | 约 14 步 |
| O(n) | 线性扫描 | 1000 步 | 10000 步 |
| O(n log n) | 快速排序 | 约 10000 步 | 约 140000 步 |
| O(n²) | 冒泡排序 | 1000000 步 | 100000000 步 |
为什么会这样？因为 O(n²) 的算法，数据量每翻 10 倍，工作量翻 100 倍。而 O(n log n) 只翻 14 倍左右。差距就是这么拉开的。
我的习惯：写代码前先估算数据规模，再选算法。数据量小于 100 时，O(n²) 也能接受；超过 1000，必须上 O(n log n) 或更好的。
23.2 空间换时间：用内存买性能
空间换时间，说白了就是「多占点内存，少跑点时间」。这在 C++ 里特别常见，因为咱们能精细控制内存布局。
我举个例子：一个字符串匹配函数，每次调用都要重新计算模式串的 next 数组。如果调用 10 万次，每次都算一遍，CPU 时间全浪费了。我建议的做法是：把 next 数组缓存起来，或者用静态变量存一份。
// 不好的做法：每次都重新计算
bool match(const std::string& text, const std::string& pattern) {
std::vector<int> next = computeNext(pattern); // 每次都要算
// ... 匹配逻辑
}
// 好的做法：缓存计算结果
class Matcher {
std::string pattern_;
std::vector<int> next_;
public:
Matcher(const std::string& pattern)
: pattern_(pattern), next_(computeNext(pattern)) {}
bool match(const std::string& text) {
// 直接用缓存的 next_
}
};你看，多占了一个成员变量的内存，但每次匹配省掉了 O(m) 的计算时间。这就是典型的空间换时间。
我曾经踩过的坑：过度使用空间换时间，导致内存暴涨。有一次我为了加速查找，把所有中间结果都缓存了，结果 16GB 内存直接爆掉。后来加了 LRU 淘汰策略，才平衡了性能和内存。
常见的空间换时间策略：
- 预计算：把常用结果提前算好存起来
- 缓存：用哈希表或数组缓存重复计算的结果
- 查表法：比如三角函数、CRC 校验，直接查表比计算快得多
- 内存对齐：多占几个字节的填充，换来 CPU 缓存命中率的提升
23.3 近似算法：精度换速度
有些场景，你不需要精确结果。比如图像处理、机器学习、实时渲染——差个 1% 根本看不出来，但速度能快 10 倍。这时候就该近似算法上场了。
我记得有个项目要做实时视频特效，需要计算每帧的直方图。精确计算要遍历所有像素，1080p 的图要算 200 多万个点。后来我改成采样法：只取 10% 的像素做统计，误差不到 2%，但速度提升了 8 倍。客户根本看不出区别。
常见的近似算法：
| 场景 | 精确算法 | 近似算法 | 速度提升 |
|---|---|---|---|
| 排序 | 快速排序 O(n log n) | 近似排序（如桶排序采样） | 2-5 倍 |
| 最短路 | Dijkstra O(n²) | A* 启发式搜索 | 10-100 倍 |
| 统计 | 精确计数 | HyperLogLog 基数估计 | 内存减少 1000 倍 |
| 矩阵运算 | 精确乘法 | 随机化算法（如蒙特卡洛） | 10-50 倍 |
我的建议：使用近似算法前，先问自己三个问题：1) 误差范围能接受吗？2) 用户能感知到误差吗？3) 有没有兜底方案？如果三个答案都是「是」，那就大胆用。
23.4 知识体系总览
下面这张图，把咱们今天聊的内容串起来了。你仔细看看，算法优化的三条路其实是有层次的：先选对复杂度，再考虑空间换时间，最后才上近似算法。
23.5 实战中的选择策略
光知道理论不行，得会用。我总结了一套「算法选择三步法」，你试试看：
- 估算数据规模：数据量小于 1000，O(n²) 也能用；超过 10 万，必须 O(n log n) 或更好
- 评估内存预算：如果内存够用（比如服务器端），大胆用空间换时间；如果是嵌入式设备，省着点
- 确认精度需求：业务要求精确结果？那就别用近似算法。允许 1%-5% 误差？近似算法是你的好朋友
记住：没有银弹。最好的算法优化，是结合业务场景做权衡。我见过有人为了追求 O(1) 搞了个巨复杂的哈希函数，结果常数项太大，还不如 O(n) 的线性扫描快。嗯，这就是典型的「过度优化」。
最后说一句：算法优化不是一锤子买卖。先跑起来，再 profile，最后优化。别一开始就想着搞个大新闻，先把功能做对，再慢慢调优。这才是工程化的思路。
公众号:蓝海资料掘金营，微信deep3321