算法复杂度基础：时间复杂度与空间复杂度、大O表示法、常见算法复杂度分析
聊到算法优化，复杂度分析是绕不开的第一道坎。我刚开始做工程时，总觉得「能跑就行」，直到有一次线上服务因为一个O(n²)的循环把CPU打满，用户请求排队到超时……嗯，那次教训让我彻底明白了：不懂复杂度，你连代码为什么慢都说不清楚。
一、什么是算法复杂度？
说白了，算法复杂度就是衡量代码「跑多快」和「占多少内存」的两把尺子。它不关心你用的是i7还是树莓派，只关心当数据量变大时，你的程序会怎么表现。
我习惯把复杂度拆成两个维度来看：
- 时间复杂度：算法执行需要的时间，随数据规模增长的趋势
- 空间复杂度：算法执行需要的额外内存，随数据规模增长的趋势
你想想看，如果数据量从100变成100万，你的代码耗时是翻倍还是翻了1万倍？这就是复杂度要回答的问题。
二、大O表示法——复杂度界的「速记符号」
大O表示法，其实就是在描述「最坏情况下的增长趋势」。它忽略常数和低阶项，只保留最高阶的部分。
核心规则：
- 忽略常数：O(2n) → O(n)
- 忽略低阶：O(n² + n) → O(n²)
- 只保留最高阶：O(3n³ + 2n² + 5) → O(n³)
举个例子，我写过一段代码：
// 查找数组中是否存在目标值
bool findTarget(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return true;
}
}
return false;
}这段代码的时间复杂度是O(n)。为什么？因为最坏情况下（目标值在末尾或不存在），你得把整个数组遍历一遍。n就是数组长度。
我的小技巧：分析复杂度时，先找循环。一层循环通常是O(n)，两层嵌套循环往往是O(n²)。递归的话，画个调用树会清晰很多。
三、常见算法复杂度速查表
我在项目中整理过一张表，每次写代码前都会瞄一眼：
| 复杂度 | 名称 | 典型场景 | 数据量100时的操作数 |
|---|---|---|---|
| O(1) | 常数阶 | 数组随机访问、哈希表查找 | 1 |
| O(log n) | 对数阶 | 二分查找、平衡二叉树 | 约7 |
| O(n) | 线性阶 | 遍历数组、链表查找 | 100 |
| O(n log n) | 线性对数阶 | 归并排序、快速排序（平均） | 约664 |
| O(n²) | 平方阶 | 冒泡排序、双重循环 | 10,000 |
| O(2ⁿ) | 指数阶 | 递归斐波那契、子集枚举 | 天文数字 |
看到O(2ⁿ)那行了吗？数据量到100时，操作数比宇宙中的原子还多。我曾经在面试中遇到过候选人用递归算斐波那契第50项，结果等了半天没出结果……这就是没做复杂度分析的后果。
四、空间复杂度——别光顾着快，内存也要命
很多人只盯着时间复杂度，忽略了空间复杂度。我踩过这个坑：
我曾经……在嵌入式设备上实现一个缓存算法，为了追求O(1)的查找速度，把整个数据集都加载到内存里。结果设备内存只有64MB，数据量一上来直接OOM（内存溢出）。后来才明白，有时候O(log n)的查找配上O(1)的空间，才是工程上的最优解。
空间复杂度分析其实更简单：
- 额外开辟了一个长度为n的数组 → O(n)
- 递归深度为n → O(n)（调用栈占空间）
- 只用了几个临时变量 → O(1)
五、复杂度分析的核心逻辑图
下面这张图是我自己总结的，每次做复杂度分析时都会在脑子里过一遍：
六、实战：分析一个排序算法
拿冒泡排序举个例子，看看怎么实际分析：
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { // 外层循环 n-1 次
for (int j = 0; j < n - i - 1; j++) { // 内层循环 n-i-1 次
if (arr[j] > arr[j + 1]) {
int temp = arr[j]; // 交换操作 O(1)
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}时间复杂度分析：
- 外层循环执行 n-1 次
- 内层循环平均执行 n/2 次
- 总操作数 ≈ (n-1) × (n/2) = n²/2 - n/2
- 忽略常数和低阶项 → O(n²)
空间复杂度分析：
- 只用了几个临时变量（i, j, temp）
- 没有额外开辟数组或递归调用
- → O(1)
避坑指南：我见过有人把冒泡排序优化成「提前退出」版本——如果某轮没有交换就提前结束。这时候最好情况是O(n)，但最坏情况仍然是O(n²)。分析复杂度时，永远先看最坏情况，这才是你的性能底线。
七、常见误区与我的经验
这些年带团队，发现新手最容易犯这几个错：
- 把常数时间当成O(0)：O(1)不是不花时间，而是时间恒定。比如哈希表查找，虽然快，但还是要算哈希值的。
- 忽略递归的栈空间：递归深度为n时，空间复杂度是O(n)，不是O(1)。我见过有人用递归写深度优先搜索，数据量一大就栈溢出。
- 混淆平均情况和最坏情况：快速排序平均是O(n log n)，但最坏是O(n²)。如果你处理的数据恰好是逆序的，那就等着卡死吧。
我个人习惯是：写代码前先估算复杂度，写完后用实际数据压测验证。理论分析和工程实践要结合起来，缺一不可。
好了，复杂度基础就聊到这儿。记住一句话：不懂复杂度的工程师，写出的代码就像蒙着眼睛开车——能跑，但不知道什么时候会翻车。