C / C++ / 系统课时
分析循环代码的时间复杂度
分析循环代码的时间复杂度
面对一段 C 循环代码,真正要判断的不是它“跑了几行”,而是输入规模 n 增长时,关键操作次数如何增长。掌握单层、嵌套和折半循环后,就能快速估算常见循环的时间复杂度。
学习目标
- 根据循环执行次数判断 O(n)、O(n²) 和 O(log n)
- 理解顺序循环、嵌套循环和折半循环的计算方法
- 避免只看循环层数或代码行数判断复杂度
先找输入规模和关键操作
时间复杂度描述的是输入规模增长时,算法执行成本的增长趋势。分析循环时,通常先把输入规模记为 n,再选择循环体中的一个常数时间操作作为“关键操作”,估算它会执行多少次。
赋值、整数加减、数组按下标访问等操作通常视为 O(1)。因此,不需要精确统计 CPU 指令,只要抓住执行次数随 n 的变化即可。
下面用计数器直接观察三种典型循环。程序中的计数本身只是为了演示执行次数,不是实际算法必须保留的代码。
#include <stdio.h>
long long count_linear(int n) {
long long count = 0;
for (int i = 0; i < n; ++i) {
++count;
}
return count;
}
long long count_quadratic(int n) {
long long count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
++count;
}
}
return count;
}
long long count_logarithmic(int n) {
long long count = 0;
// 每轮把问题规模减半,因此轮数增长得很慢。
for (int x = n; x > 0; x /= 2) {
++count;
}
return count;
}
int main(void) {
int n = 8;
printf("linear: %lld\n", count_linear(n));
printf("quadratic: %lld\n", count_quadratic(n));
printf("logarithmic: %lld\n", count_logarithmic(n));
return 0;
}预期输出
linear: 8
quadratic: 64
logarithmic: 4当 n 为 8 时,三段循环分别执行 8、64、4 次。更重要的是 n 继续增大后的趋势:第一段与 n 成正比,第二段与 n² 成正比,第三段每轮把规模除以 2,因此只需要约 log₂n 轮。
| 循环形式 | 关键操作次数 | 时间复杂度 |
|---|---|---|
| 单层循环执行 n 次 | n | O(n) |
| 两层各执行 n 次 | n² | O(n²) |
| 每轮把规模减半 | 约 log₂n | O(log n) |
嵌套循环要算真实执行次数
看到两层循环时,可以先想到平方级,但不能机械地认为“几层循环就是几次方”。真正决定复杂度的是内层循环累计执行多少次。
片段示例:假设 work() 每次调用都是 O(1),并且 n 为非负整数。内层循环次数由外层变量 i 决定。
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
work();
}
}work() 的执行次数是 0 + 1 + 2 + ... + (n - 1),总数为 n(n-1)/2。虽然内层不是每次都执行 n 次,但最高次项仍然是 n²,所以时间复杂度仍为 O(n²)。
另一种组合是外层不断折半,内层每次完整扫描 n 个元素。此时外层约执行 log n 次,每次需要 O(n),总复杂度就是 O(n log n),而不是简单根据“两层循环”判断为 O(n²)。
顺序执行通常相加,嵌套执行看乘积
如果两个独立循环先后执行,第一个做 n 次操作,第二个做 2n 次操作,总成本是 3n,忽略常数因子后仍是 O(n)。如果一个 O(n) 的循环完整嵌套在另一个 O(n) 循环中,则关键操作会达到 n×n 次,形成 O(n²)。
分析时最终只保留增长最快的项。例如 O(n²+n+20) 写成 O(n²),O(5n+100) 写成 O(n)。这样做不是说低阶项没有执行,而是当 n 足够大时,它们不会改变增长级别。
用固定顺序检查循环
面对新的循环代码,可以按下面的顺序判断:
- 明确 n 代表什么输入规模,例如数组长度或元素数量。
- 找出关键操作,并判断单次执行是否可以视为 O(1)。
- 计算关键操作总共执行多少次,特别注意循环边界是否依赖外层变量。
- 写出关于 n 的表达式,去掉常数因子和低阶项,只保留增长最快的部分。
只要把注意力从“代码有几行、循环有几层”转向“关键操作随 n 增长多少次”,单层、嵌套和折半循环的复杂度就能用同一套方法稳定判断。