算法复杂度分析：时间与空间的博弈
说实话，我刚开始写C++那会儿，根本不在乎什么复杂度分析。能跑就行，管它快不快？直到有一次，我写了个双重循环处理几十万条数据，程序跑了整整三分钟还没出结果……嗯，从那以后，我就老老实实把复杂度分析当成了必修课。
今天咱们聊聊算法复杂度。说白了，就是衡量你的代码到底有多「贵」——贵在时间，贵在内存。
大O表示法：别被名字吓到
大O表示法，英文叫Big O Notation。我第一次看到这个O的时候，还以为是「哦」的意思。后来才知道，它描述的是算法运行时间的增长趋势。
举个例子：你写了个循环，遍历一个数组。数组有n个元素，循环就要执行n次。那这个算法的时间复杂度就是O(n)。如果数组翻倍，时间也翻倍——线性增长。
大O表示法关注的是最坏情况下的上界。它忽略常数和低阶项。为什么？因为当n足够大时，那些细枝末节根本不重要。
核心要点：大O表示的是「当输入规模趋近无穷大时，算法运行时间的增长速率」。
时间复杂度：你的代码跑多快？
时间复杂度，就是算法执行时间随输入规模增长的函数关系。我习惯把它分成几档：
| 复杂度 | 名称 | 典型场景 | n=1000时的大致操作数 |
|---|---|---|---|
| O(1) | 常数时间 | 数组随机访问 | 1 |
| O(log n) | 对数时间 | 二分查找 | 约10 |
| O(n) | 线性时间 | 遍历数组 | 1000 |
| O(n log n) | 线性对数时间 | 快速排序、归并排序 | 约10000 |
| O(n²) | 平方时间 | 冒泡排序、双重循环 | 1,000,000 |
| O(2ⁿ) | 指数时间 | 递归斐波那契（未优化） | 天文数字 |
你看这个表，O(n²)在n=1000时就已经是百万级别了。我在项目中遇到过有人用冒泡排序处理十万条数据——嗯，那顿饭吃完回来程序还在跑。
空间复杂度：内存不是免费的
空间复杂度，就是算法占用的额外内存空间。很多人只盯着时间，忽略了空间。但你要知道，嵌入式系统、移动设备上，内存比时间更金贵。
空间复杂度的分析方法和时间复杂度类似，也是用大O表示。常见的空间复杂度有：
- O(1)：只用了几个临时变量，不随输入规模变化
- O(n)：需要额外分配一个和输入等大的数组
- O(n²)：比如二维矩阵的存储
我的习惯：写代码前先问自己三个问题——这个算法需要多少额外内存？能不能原地操作？有没有空间换时间的可能？
常见算法复杂度对比
咱们拿排序算法来做个对比，这是最经典的例子：
| 算法 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 归并排序 | O(n log 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(n²)。归并排序稳定，但需要额外O(n)的空间。这就是典型的时间-空间权衡。
实战：如何分析一段代码的复杂度？
咱们直接上代码。我写个例子，你来感受一下：
// 例1：O(n) —— 线性时间
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += arr[i];
}
// 例2：O(n²) —— 平方时间
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// 做一些操作
}
}
// 例3：O(log n) —— 对数时间
int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}分析的时候，我一般这么看：
- 有没有循环？嵌套了几层？
- 每次循环的规模是n还是缩小了？
- 有没有递归调用？递归深度是多少？
我曾经踩过的坑：写了一个看似O(n)的算法，结果里面调用了std::vector的insert操作——insert是O(n)的！外层循环再跑n次，直接变成O(n²)。所以，STL容器操作的时间复杂度一定要心里有数。
复杂度分析的核心逻辑
下面这张图，是我自己总结的复杂度分析决策流程。每次拿到一个算法，我就按这个思路走一遍：
这张图的核心逻辑很简单：先看有没有循环或递归，再看循环次数和嵌套层数。每次规模减半就是O(log n)，单层循环是O(n)，双层嵌套就是O(n²)。
避坑指南：我踩过的那些坑
最后分享几个实战中容易忽略的点：
- STL容器操作不是免费的：std::vector的push_back是均摊O(1)，但insert是O(n)。std::map的查找是O(log n)，但std::unordered_map是O(1)——前提是哈希函数写得好。
- 递归的空间复杂度别忘了：递归调用会占用栈空间。深度为n的递归，空间复杂度就是O(n)。我曾经写了个深度递归，结果栈溢出了……
- 常数优化有时也很重要：虽然大O忽略常数，但实际工程中，一个O(n)算法如果常数很大，可能还不如一个优化好的O(n log n)算法快。
我的建议：写代码前先估算复杂度。如果预估到O(n²)以上，就要警惕了。能用STL就用STL，它里面的实现都是经过千锤百炼的，复杂度有保证。
复杂度分析，说白了就是让你对代码的性能有个「心理预期」。别等到线上出问题了才去优化——那时候代价就大了。
公众号:蓝海资料掘金营，微信deep3321