3. 时间复杂度分析：大O表示法、常见时间复杂度、最坏情况与平均情况
聊到算法，绕不开的就是效率问题。我刚开始写C代码那会儿，觉得能跑就行。后来在嵌入式项目里，一个排序多花了200毫秒，整个系统就卡住了。嗯，从那以后，我养成了一个习惯——写代码前先算算复杂度。
说白了，时间复杂度就是衡量代码跑得快不快的一把尺子。它不关心你的CPU主频多高，也不管编译器优化多强，它只关注：当数据量变大时，你的程序执行时间会怎么变。
3.1 大O表示法：我们到底在衡量什么？
大O表示法，我个人理解就是「忽略细节，抓大放小」。它描述的是算法执行时间随输入规模增长的增长趋势。
举个例子，你写了个循环：
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}这个循环执行了n次。不管你的printf有多快，当n翻倍时，执行时间也大约翻倍。这就是O(n)——线性阶。
大O表示法有几个核心规则：
- 只保留最高阶项：比如 3n² + 2n + 1，只取 n²
- 忽略常数系数：100n 和 n，都写成 O(n)
- 关注最坏情况：我们通常分析的是「最差」时的表现
核心理解：大O不是精确的时间，而是「当n足够大时，时间增长的级别」。O(1000n) 和 O(n) 在n=10时差很多，但n=10亿时，它们属于同一个量级。
3.2 常见时间复杂度：从快到慢排个队
我在项目中整理过一张表，每次面试新人时也喜欢拿这个考考他们。你想想看，下面这些复杂度，你见过几个？
| 大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(n²) 和 O(n log n) 在n=100时差距不大，但n=10000时，就是天壤之别。我在做图像处理时，一个O(n²)的滤镜算法处理一张图要3秒，换成O(n log n)的优化版本后，降到0.1秒。这就是复杂度的威力。
3.3 常数阶 O(1)：最快的梦想
常数阶意味着：不管数据多大，执行时间固定。比如：
int getFirst(int arr[]) {
return arr[0];
}无论数组有10个元素还是1000万个，这条语句都只执行一次。这就是O(1)。
小技巧：写代码时，尽量把「热点数据」用O(1)的方式访问。比如用哈希表代替链表查找，用数组代替链表遍历。我习惯在数据结构设计阶段就问自己：「这个操作能不能做到O(1)？」
3.4 对数阶 O(log n)：二分法的魅力
对数阶是算法工程师最喜欢的一种复杂度。它增长极慢——n从100涨到100万，log₂n只从7涨到20。
二分查找就是典型：
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 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;
}为什么是O(log n)？因为每次循环，搜索范围缩小一半。2^k = n，所以k = log₂n。
注意：二分查找的前提是数组必须有序。我曾经在项目中直接对无序数组做二分查找，结果查了半天找不到数据，还以为是算法写错了……后来才发现数据没排序。排序本身是O(n log n)，如果只查一次，不如直接线性查找。
3.5 线性阶 O(n) 与 线性对数阶 O(n log n)
线性阶很好理解——一个循环走一遍。比如求数组最大值：
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}n=1000时执行1000次，n=100万时执行100万次。线性增长。
O(n log n)稍微复杂一点。它通常出现在「分治」类算法中，比如归并排序：把数组分成两半（log n层），每层合并时遍历所有元素（n个）。所以是n × log n。
我个人觉得，O(n log n)是「性价比最高」的复杂度。它比O(n²)快得多，但实现起来比O(log n)的算法简单。日常开发中，大部分排序场景用O(n log n)就够了。
3.6 平方阶 O(n²)：小心你的双重循环
平方阶是新手最容易写出来的复杂度。两个嵌套循环，每个都跑n次：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("(%d, %d)\n", i, j);
}
}n=100时，1万次操作。n=10000时，1亿次。n=10万时，100亿次——你的程序基本就卡死了。
避坑指南：我曾经在数据处理模块里写了一个三重循环O(n³)，处理1000条记录时跑了整整40秒。后来改成O(n²)的算法，降到0.5秒。记住：看到嵌套循环，就要警惕。能用哈希表、排序、双指针优化的，尽量别用暴力法。
3.7 最坏情况与平均情况
大O表示法通常指的是最坏情况。为什么？因为我们要保证「下限」——即使数据再差，算法也不能崩。
拿快速排序举例：
- 最坏情况：O(n²)——当数组已经有序，且每次选第一个元素作为pivot时
- 平均情况：O(n log n)——随机数据下，表现稳定
- 最好情况：O(n log n)——每次pivot都能平分数组
你可能会问：「那为什么我们平时都说快排是O(n log n)？」
因为在实际工程中，通过随机化pivot或三数取中法，最坏情况几乎不会出现。所以平均情况更有参考价值。
但有些场景，你必须考虑最坏情况。比如：
- 实时系统：响应时间不能超过100ms，最坏情况必须达标
- 安全场景：密码验证算法，不能因为输入特殊就变慢（防止时序攻击）
我的习惯：写算法时，先分析最坏情况复杂度。如果最坏情况可以接受，那平均情况肯定没问题。如果最坏情况太差，再考虑优化或换算法。
3.8 本章知识体系总览
下面这张图，把本章的核心逻辑串起来了。你可以把它当作一个「复杂度速查地图」：
3.9 总结一下
时间复杂度分析，说白了就是回答一个问题：当数据变大时，你的代码会不会变慢？变慢多少？
记住几个关键点：
- 大O表示法忽略常数，只看增长趋势
- O(1) 和 O(log n) 是最理想的，尽量往这个方向靠
- O(n) 是底线，大部分场景可以接受
- O(n²) 及以上，数据量一大就扛不住了
- 最坏情况分析保证下限，平均情况反映真实表现
我在写每一段代码前，都会在脑子里过一遍复杂度。这个习惯帮我避免了很多性能灾难。希望你也能养成这个习惯——毕竟，写出能跑的代码只是第一步，写出高效的代码才是工程师的追求。