C / C++ / 系统课时

分析循环代码的时间复杂度

分析循环代码的时间复杂度

面对一段 C 循环代码,真正要判断的不是它“跑了几行”,而是输入规模 n 增长时,关键操作次数如何增长。掌握单层、嵌套和折半循环后,就能快速估算常见循环的时间复杂度。

学习目标

  • 根据循环执行次数判断 O(n)、O(n²) 和 O(log n)
  • 理解顺序循环、嵌套循环和折半循环的计算方法
  • 避免只看循环层数或代码行数判断复杂度

先找输入规模和关键操作

时间复杂度描述的是输入规模增长时,算法执行成本的增长趋势。分析循环时,通常先把输入规模记为 n,再选择循环体中的一个常数时间操作作为“关键操作”,估算它会执行多少次。

赋值、整数加减、数组按下标访问等操作通常视为 O(1)。因此,不需要精确统计 CPU 指令,只要抓住执行次数随 n 的变化即可。

下面用计数器直接观察三种典型循环。程序中的计数本身只是为了演示执行次数,不是实际算法必须保留的代码。

c
#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;
}

预期输出

text
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 决定。

c
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 足够大时,它们不会改变增长级别。

用固定顺序检查循环

面对新的循环代码,可以按下面的顺序判断:

  1. 明确 n 代表什么输入规模,例如数组长度或元素数量。
  2. 找出关键操作,并判断单次执行是否可以视为 O(1)。
  3. 计算关键操作总共执行多少次,特别注意循环边界是否依赖外层变量。
  4. 写出关于 n 的表达式,去掉常数因子和低阶项,只保留增长最快的部分。

只要把注意力从“代码有几行、循环有几层”转向“关键操作随 n 增长多少次”,单层、嵌套和折半循环的复杂度就能用同一套方法稳定判断。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

分析循环代码的时间复杂度

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通