4、算法与数据结构优化：时间复杂度与空间复杂度、常见算法优化技巧、数据结构选择策略
聊到性能优化，算法和数据结构这块是绕不开的硬骨头。我见过太多项目，硬件堆得挺猛，结果跑起来慢得像蜗牛，一查全是算法选型出了问题。说白了，代码写得再漂亮，底层逻辑不对，一切都是白搭。
这一章，咱们就扎进去看看，怎么从算法和数据结构的角度，把性能给榨出来。
4.1 时间复杂度与空间复杂度：性能的度量衡
你想想看，两个程序都能算出结果，但一个眨眼功夫，另一个要喝杯咖啡。区别在哪？就在复杂度上。
时间复杂度，衡量的是代码执行时间随数据量增长的趋势。不是精确的秒数，而是“量级”。比如 O(1) 是常数级，不管数据多大，时间都差不多；O(n) 是线性级，数据翻倍，时间也翻倍；O(n²) 是平方级，数据一多，时间就爆炸。
空间复杂度，衡量的是代码运行时占用的内存空间。有些算法快是快，但内存吃得厉害，这在嵌入式或移动端就是灾难。
核心原则： 时间复杂度和空间复杂度往往需要权衡。用空间换时间，或者用时间换空间，没有绝对的好坏，只有合不合适的场景。
我记得有一次优化一个日志分析系统，原始代码用了三层嵌套循环，数据量一上百万，直接卡死。我把它改成哈希表加一次遍历，时间复杂度从 O(n³) 降到了 O(n)，内存虽然多了几百 KB，但执行时间从 5 分钟降到了 2 秒。这笔买卖，值。
4.2 常见算法优化技巧
实战中，我总结了几招特别管用的优化技巧。嗯，这里要注意，不是所有技巧都万能，得看场景。
4.2.1 空间换时间：缓存与预计算
这是最常用的招数。把重复计算的结果存起来，下次直接用。
- 缓存： 比如用 Redis 缓存数据库查询结果，或者用本地 HashMap 缓存函数计算结果。
- 预计算： 比如游戏里的碰撞检测，提前把地图网格化，运行时直接查表，省得每帧都算一遍。
// 一个简单的斐波那契数列缓存示例
// 没有缓存时，n=50 能算到天荒地老
// 加了缓存，瞬间出结果
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
private static Map<Integer, Long> cache = new HashMap<>();
public static long fib(int n) {
if (n <= 1) return n;
if (cache.containsKey(n)) {
return cache.get(n);
}
long result = fib(n - 1) + fib(n - 2);
cache.put(n, result);
return result;
}
}
我的习惯： 写递归函数时，第一件事就是考虑要不要加缓存。尤其是那种参数组合有限、但调用次数极多的场景，缓存能救命。
4.2.2 减少不必要的计算：懒加载与短路求值
能不现在算的，就晚点算。能不全部算的，就只算一部分。
- 懒加载： 对象创建时，不初始化所有字段。等真正用到某个字段时，再加载。比如 ORM 框架里的延迟加载。
- 短路求值： 逻辑与 (&&) 和逻辑或 (||) 运算中，如果第一个条件已经能决定结果，第二个条件就不执行了。比如
if (user != null && user.getName().equals("admin"))，如果 user 是 null，就不会执行 getName()，避免了空指针。
4.2.3 循环优化：减少循环次数与循环内操作
循环是性能杀手。优化循环，往往立竿见影。
- 减少循环次数： 能用二分查找的，别用线性查找。能用哈希的，别用遍历。
- 减少循环内操作： 把循环内不变的表达式提到外面。比如
for (int i = 0; i < list.size(); i++)，每次循环都调用 size() 方法，不如先int len = list.size()再循环。 - 循环展开： 对于固定次数的循环，手动展开可以减少分支判断。不过现代编译器很多会自动做，不用太刻意。
// 优化前：每次循环都计算 size()
for (int i = 0; i < list.size(); i++) {
// do something
}
// 优化后：只计算一次 size()
int len = list.size();
for (int i = 0; i < len; i++) {
// do something
}
4.2.4 分治与并行：把大问题拆成小问题
数据量太大，单线程搞不定？那就分而治之。
- 分治： 把大任务拆成多个小任务，分别解决，再合并结果。比如归并排序、MapReduce。
- 并行： 利用多核 CPU，同时处理多个任务。Java 里的 ForkJoinPool、Python 里的 multiprocessing，都是干这个的。
我曾经踩过的坑： 并行不是万能的。任务拆分和合并本身有开销，如果任务太小，并行反而比串行慢。另外，线程安全问题也得小心，一不小心就死锁或者数据不一致。
4.3 数据结构选择策略
数据结构选对了，算法优化事半功倍。选错了，神仙也救不了。
下面这张图，是我自己总结的数据结构选择决策流程，你可以参考一下。
当然，实际场景比这张图复杂得多。比如你需要一个既能快速查找又能保持插入顺序的结构，那 LinkedHashMap 就是你的菜。你需要一个线程安全的队列，那 ConcurrentLinkedQueue 或者 BlockingQueue 就得上场。
4.3.1 数组 vs 链表
| 特性 | 数组 (ArrayList) | 链表 (LinkedList) |
|---|---|---|
| 随机访问 | O(1) — 极快 | O(n) — 慢 |
| 插入/删除（头部） | O(n) — 需要移动元素 | O(1) — 只需改指针 |
| 插入/删除（尾部） | O(1) 均摊 — 很快 | O(1) — 很快 |
| 内存占用 | 连续内存，较少 | 分散内存，每个节点有额外指针开销 |
| 适用场景 | 频繁读取，很少插入删除 | 频繁插入删除，很少随机访问 |
我个人习惯是，90% 的场景直接用 ArrayList。只有在明确需要频繁在头部插入删除，或者数据量极大且不确定大小时，才考虑 LinkedList。
4.3.2 哈希表 vs 树结构
| 特性 | 哈希表 (HashMap) | 树结构 (TreeMap) |
|---|---|---|
| 查找 | O(1) 平均，O(n) 最坏 | O(log n) |
| 有序性 | 无序 | 有序（按自然顺序或比较器） |
| 内存 | 较高（有负载因子和扩容） | 较高（有节点指针） |
| 适用场景 | 快速查找，不需要顺序 | 需要范围查询、排序、按顺序遍历 |
避坑指南： 我曾经在需要频繁范围查询的场景用了 HashMap，结果每次都要遍历所有数据，性能惨不忍睹。后来换成 TreeMap，利用它的 subMap() 方法，性能直接提升了 10 倍。选对结构，比优化代码本身更重要。
4.4 总结
算法与数据结构优化，说白了就是两件事：选对结构，用对技巧。时间复杂度、空间复杂度是衡量标准，缓存、懒加载、循环优化、分治并行是常用手段。而数据结构的选择，得根据你的业务场景来——要快查用哈希，要有序用树，要频繁插删用链表，要随机访问用数组。
没有银弹，只有权衡。多积累实战经验，慢慢你就会有感觉了。