18、算法优化：时间复杂度分析，空间换时间策略，分治与动态规划
聊到算法优化，很多同学第一反应就是「快」。但到底怎么个快法？快多少？值不值得快？
我做了十几年C语言开发，见过太多人一上来就撸代码，结果跑起来才发现——嗯，慢得离谱。其实，算法优化的核心就三件事：算清楚复杂度、拿空间换时间、选对策略。今天咱们就掰开揉碎聊聊。
18.1 时间复杂度分析：别凭感觉，要算账
先问个问题：你写的代码，到底跑多快？
很多人说「我测过，挺快的」。但测出来的数据有局限性——数据量一变，性能可能天差地别。我个人习惯，先做理论分析，再动手优化。
18.1.1 大O表示法：最坏情况下的「天花板」
大O表示法，说白了就是看输入规模n变大时，你的代码要干多少活。常见的有：
| 复杂度 | 含义 | 典型场景 |
|---|---|---|
| O(1) | 常数时间，跟n无关 | 数组随机访问 |
| O(log n) | 对数时间，增长极慢 | 二分查找 |
| O(n) | 线性时间，跟n成正比 | 遍历数组 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序 |
| O(n²) | 平方时间，n一大就崩 | 冒泡排序、双重循环 |
| O(2ⁿ) | 指数时间，基本不可用 | 暴力递归斐波那契 |
举个例子，你写了个双重循环：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 做一些操作
}
}这就是O(n²)。当n=1000时，循环100万次。当n=10000时，循环1亿次。你看，n只翻了10倍，工作量翻了100倍。这就是为什么我常说：别小看复杂度，它决定了你的代码能撑多大场面。
18.1.2 空间复杂度：内存不是无限的
时间复杂度看CPU，空间复杂度看内存。很多新手只盯着时间，忽略了内存。但你要知道，内存不够用，程序一样崩。
空间复杂度同样用大O表示：
- O(1)：只用了几个变量，跟n无关
- O(n)：用了一个跟n等长的数组
- O(n²)：用了一个n×n的矩阵
我曾经在项目中遇到一个坑：用递归实现深度优先搜索，没控制好递归深度，结果栈溢出了。嗯，这就是空间复杂度没算清楚——递归调用栈也是空间开销。
18.2 空间换时间策略：用内存买性能
这是我最常用的优化手段。说白了就是：多存点数据，少算几遍。
18.2.1 查表法：预计算，直接取
比如你要计算0~255每个数的平方。每次用的时候算一遍？太慢了。直接建个表：
static int square_table[256];
void init_table() {
for (int i = 0; i < 256; i++) {
square_table[i] = i * i;
}
}
int get_square(int x) {
return square_table[x];
}查表是O(1)，计算是O(n)。你想想看，如果这个函数被调用几百万次，查表能省多少时间？
18.2.2 缓存结果：避免重复劳动
我在做图像处理时遇到过一个问题：同一个像素点的颜色值被反复计算。后来我加了个缓存，算过的结果直接存起来，下次直接取。效果立竿见影。
举个简单的例子，斐波那契数列：
// 普通递归（O(2ⁿ)）
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// 带缓存的递归（O(n)）
int fib_memo(int n, int* memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
return memo[n];
}你看，加了个数组缓存，复杂度从指数级降到线性。这就是空间换时间的经典案例。
1. 缓存命中率够不够高？
2. 内存开销是否在可接受范围内？
3. 有没有更好的算法可以根本解决问题？
18.3 分治策略：化整为零，各个击破
分治，说白了就是「大事化小」。把一个大问题拆成几个小问题，分别解决，再合并结果。
18.3.1 分治的经典套路
分治有三个步骤：
- 分解：把原问题拆成若干子问题
- 解决：递归地解决每个子问题
- 合并：把子问题的解合并成原问题的解
最典型的例子就是归并排序：
void merge_sort(int arr[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
merge_sort(arr, left, mid); // 分解
merge_sort(arr, mid + 1, right); // 分解
merge(arr, left, mid, right); // 合并
}归并排序的时间复杂度是O(n log n)，空间复杂度是O(n)。它比冒泡排序（O(n²)）快得多，但需要额外空间来合并。
18.3.2 分治的适用场景
不是所有问题都能分治。你得满足两个条件：
- 子问题相互独立：子问题之间没有依赖关系
- 子问题可以合并：子问题的解能组合成原问题的解
我遇到过有人硬拿分治去解有重叠子问题的问题，结果效率还不如暴力。嗯，这时候就该动态规划上场了。
18.4 动态规划：记住历史，避免重算
动态规划（DP）和分治很像，但有一个关键区别：DP的子问题会重复出现。所以DP的核心就是「记住已经算过的结果」。
18.4.1 动态规划的三要素
我个人总结，DP就三件事：
- 状态定义：dp[i]表示什么？
- 状态转移方程：dp[i]怎么从dp[i-1]或dp[i-2]推出来？
- 初始条件：边界值是什么？
拿经典的「爬楼梯」问题举例：
// 爬n阶楼梯，每次可以爬1阶或2阶，有多少种方法？
int climb_stairs(int n) {
if (n <= 2) return n;
int dp[n+1];
dp[1] = 1; // 初始条件
dp[2] = 2; // 初始条件
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 状态转移
}
return dp[n];
}你看，状态转移方程就是dp[i] = dp[i-1] + dp[i-2]。为什么？因为到第i阶，要么从i-1跨1步，要么从i-2跨2步。这就是DP的精髓——用历史推导未来。
18.4.2 空间优化：滚动数组
很多DP问题，其实不需要整个dp数组。比如上面的爬楼梯，只需要记住前两个状态：
int climb_stairs_opt(int n) {
if (n <= 2) return n;
int prev1 = 1, prev2 = 2, curr;
for (int i = 3; i <= n; i++) {
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}空间复杂度从O(n)降到了O(1)。这就是「滚动数组」技巧——只保留需要的历史状态，扔掉没用的。
18.5 知识体系总览
下面这张图，是我自己梳理的算法优化知识体系。你可以把它当作一个「决策树」：遇到性能问题，先看复杂度，再选策略。
18.6 实战建议：怎么选？
最后，我分享几个实战中的判断标准：
- 数据量小（n < 100）：O(n²)也能接受，别过度优化
- 数据量大（n > 10000）：至少O(n log n)，优先考虑分治或DP
- 重复计算多：空间换时间，加缓存
- 子问题有重叠：动态规划，别用分治
- 子问题独立：分治，简单高效
记住一句话：没有最好的算法，只有最合适的算法。我见过太多人为了炫技，用DP解决一个O(n)就能搞定的事——结果代码又长又难维护。嗯，没必要。
公众号:蓝海资料掘金营，微信deep3321