算法复杂度优化：大O表示法、空间换时间、预计算、缓存结果
聊到性能优化，有个话题绕不开——算法复杂度。说白了，就是你的代码到底有多快，吃多少内存。我见过太多人上来就撸代码，跑起来发现慢得像蜗牛，回头一查，原来是选了个O(n²)的算法去处理百万级数据。嗯，这种坑我自己也踩过。
大O表示法：给代码算笔账
大O表示法不是数学考试，它就是个估算工具。告诉你当数据量变大时，你的程序会变慢多少。我个人习惯在写核心逻辑前，先拿大O估算一下，心里有个底。
| 大O符号 | 含义 | 典型场景 |
|---|---|---|
| O(1) | 常数时间 | 数组随机访问 |
| O(log n) | 对数时间 | 二分查找 |
| O(n) | 线性时间 | 遍历数组 |
| O(n log n) | 线性对数 | 快速排序、归并排序 |
| O(n²) | 平方时间 | 冒泡排序、双重循环 |
| O(2ⁿ) | 指数时间 | 递归斐波那契（未优化） |
你想想看，O(n²)和O(n log n)在数据量1000时差距还不明显，但到了100万，O(n²)要跑一万亿次操作，而O(n log n)只要两千万次。这差距，不是优化几行代码能追回来的。
空间换时间：用内存买速度
这个思路其实很朴素——你不想重复计算，那就把结果存起来。我在项目中遇到过好几次，内存便宜，CPU时间贵，那就拿内存换时间呗。
举个经典例子：斐波那契数列。递归写法简单，但重复计算太多。
// 糟糕的递归：O(2ⁿ)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
// 空间换时间：O(n)
int fib(int n) {
if (n <= 1) return n;
int *dp = malloc((n+1) * sizeof(int));
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
int result = dp[n];
free(dp);
return result;
}递归版本算fib(40)可能要几秒，而动态规划版本瞬间出结果。多花了一点点内存，换来了指数级的性能提升。这笔账，划算。
预计算：把功夫花在刀刃上
预计算，说白了就是「提前算好，用时直接拿」。我在做嵌入式系统时经常用这招——MCU性能有限，但有些值是可以提前算好的。
比如查表法算sin值：
#define TABLE_SIZE 360
double sin_table[TABLE_SIZE];
void init_sin_table() {
for (int i = 0; i < TABLE_SIZE; i++) {
sin_table[i] = sin(i * M_PI / 180.0);
}
}
double fast_sin(int degree) {
return sin_table[degree % TABLE_SIZE];
}这个表只占不到3KB内存，但每次查表只需要O(1)时间。如果实时计算sin，每次都要调用数学库，慢得多。我曾经在一个实时音频处理项目里用这招，把CPU占用率从85%降到了30%。
缓存结果：别重复造轮子
缓存和预计算有点像，但更灵活。预计算是提前算好所有可能，缓存是「用到了才算，算完存起来，下次直接用」。
我举个实际例子：假设你有个函数，根据用户ID查权限。每次查都要走数据库，很慢。那就加个缓存：
#include <string.h>
typedef struct {
int user_id;
int permission;
int valid;
} CacheEntry;
CacheEntry cache[1024];
int cache_count = 0;
int get_permission(int user_id) {
// 先查缓存
for (int i = 0; i < cache_count; i++) {
if (cache[i].user_id == user_id && cache[i].valid) {
return cache[i].permission;
}
}
// 缓存没有，去数据库查（模拟）
int perm = query_database(user_id);
// 存入缓存
if (cache_count < 1024) {
cache[cache_count].user_id = user_id;
cache[cache_count].permission = perm;
cache[cache_count].valid = 1;
cache_count++;
}
return perm;
}这个模式叫「惰性缓存」——第一次查慢，后面就快了。我曾经在一个Web服务器项目里用LRU缓存，把热点数据的查询延迟从50ms降到了0.1ms。效果立竿见影。
知识体系总览
下面这张图把本章的核心逻辑串起来了。你可以看到，从大O分析出发，到三种优化策略，再到实际落地，是一条清晰的路径。
实际应用中的取舍
说了这么多，你可能会问：到底什么时候用预计算，什么时候用缓存？
我的经验是这样的：
- 数据量小且固定 → 预计算。比如三角函数表、CRC校验表。
- 数据量大但热点集中 → 缓存。比如用户权限、商品详情。
- 计算代价极高 → 空间换时间。比如动态规划、矩阵乘法优化。
- 数据动态变化 → 只能用缓存，而且要加过期策略。
最后说一句：算法复杂度优化不是炫技，是实打实的工程决策。你想想看，一个O(n²)的排序，数据量从1000涨到10000，时间就涨了100倍。而换成O(n log n)，只涨了13倍。这差距，不是靠「多写几个if优化」能追上的。
嗯，今天就聊到这儿。记住一句话：先算复杂度，再动手写代码。这个习惯，能帮你省下无数调试时间。