信息学竞赛 C++ 教材

Appearance

第 38 章 算法的速度——复杂度分析 ​

🏗️ 前情回顾：前面五个模块，你学会了变量、分支、循环、数组、字符串、函数和结构体。你已经能写程序解决问题了。但有一个关键问题你还没认真想过：同样的任务，不同的写法，谁更快？ 比如求 1 到 n 的和，用 for 循环累加和用公式 n*(n+1)/2，速度一样吗？这一章，我们一起来学习如何衡量算法的"快慢"——这是竞赛中最基础的素养之一。

🎯 本章目标 ​

学完这一章，你能：

  • 理解为什么要分析算法的速度，而不只看程序"能不能跑"
  • 掌握时间复杂度的概念，用循环次数估算程序的运行时间
  • 读懂大 O 记号：O(n)、O(n²)、O(n³)、O(log n)、O(n log n)
  • 了解空间复杂度的概念
  • 区分最好情况、最坏情况和平均情况
  • 学会一眼看出嵌套循环的复杂度，理解常数项为什么可以忽略

📖 故事引入 ​

小明和小红各写了一个程序，功能一模一样：判断 n 个数里有没有重复的数。

小明的写法是双重循环——每个数和它后面的所有数都比较一遍。小红的写法是先排序，再检查相邻的数。输入 10 个数时，两个程序都是"秒出结果"。但输入 100000 个数时，小明的程序跑了 10 秒还没出结果，小红的程序 0.1 秒就搞定了。

同样的功能，为什么速度差了一百倍？

这就是算法效率的差异。在 CSP-J 竞赛中，一道题的正确解法往往不止一种，但只有复杂度合理的算法才能拿满分。所以你必须学会：不看代码写得多漂亮，而看它跑得多快。

🧱 知识讲解 ​

38.1 什么是时间复杂度 ​

时间复杂度 = 衡量程序运行时间随数据规模增长而变化的规律。不是精确的秒数（不同机器跑出来的时间不一样），而是一个趋势。

最常见的衡量方式：数一数最内层语句被执行了多少次——如果数据规模是 n，执行次数大约是 n 的某个函数 f(n)，就说时间复杂度是 O(f(n))。

cpp
// 例 1：单层循环 — 执行 n 次
int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += i;           // 执行 n 次
}
// 时间复杂度：O(n)
cpp
// 例 2：双重循环 — 执行 n² 次
int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        count++;         // 执行 n × n = n² 次
    }
}
// 时间复杂度：O(n²)
cpp
// 例 3：每次翻倍 — 执行 log₂n 次
int x = 1;
while (x < n) {
    x = x * 2;          // x: 1 → 2 → 4 → 8 → ... 直到 ≥ n
}
// 循环次数 ≈ log₂n → 时间复杂度：O(log n)

38.2 大 O 记号 ​

大 O 记号（Big-O Notation）是描述复杂度的标准"语言"。它只关注增长最快的项，忽略常数和低阶项。

大 O通俗名称举例
O(1)常数直接算公式，与 n 无关
O(log n)对数二分查找、每次操作范围减半
O(n)线性一轮 for 循环
O(n log n)线性对数高效排序（快排、归并）
O(n²)平方双重 for 循环、冒泡/选择/插入排序
O(n³)立方三重 for 循环、Floyd 最短路
O(2ⁿ)指数递归求斐波那契（暴力版）、穷举子集

类比：大 O 就像"车速级别"。具体是 58km/h 还是 62km/h 不太重要（常数项），重要的是"你是走路、骑车还是开车"（O(n) vs O(n²) vs O(log n)）。

38.3 一眼看出循环的复杂度 ​

给你一段代码，怎么快速看出它是 O(几)？

法则 1：单层循环，从 1 到 n → O(n)

法则 2：嵌套循环 → 各层循环次数的乘积

cpp
for (int i = 1; i <= n; i++)        // n 次
    for (int j = 1; j <= n; j++)    // n 次
        doSomething();              // 总共 n² 次 → O(n²)

法则 3：循环变量每次翻倍 → O(log n)

cpp
for (int i = 1; i <= n; i *= 2)    // i: 1, 2, 4, 8, ..., n
    doSomething();                  // 总共 log₂n 次 → O(log n)

法则 4：只看最大项，忽略常数

cpp
for (int i = 1; i <= n; i++)        // n 次 → O(n)
    doSomething();
for (int i = 1; i <= n; i++)        // n 次 → 还是 O(n)，不是 O(2n)
    doSomethingElse();
// 总复杂度：O(n)，常数 2 被忽略
cpp
for (int i = 1; i <= n; i++)        // n
    for (int j = 1; j <= n; j++)    // n²
        doSomething();
for (int i = 1; i <= n; i++)        // n
    doSomethingElse();
// 总复杂度：O(n²)，O(n) 被更高阶的 O(n²) 吞掉

38.4 空间复杂度 ​

除了时间，还要考虑空间——程序需要多占多少内存。

cpp
// 空间 O(1) — 只有几个变量，不随 n 增长
int sum = 0;
for (int i = 1; i <= n; i++) sum += i;

// 空间 O(n) — 开了一个长度为 n 的数组
int a[n];
for (int i = 0; i < n; i++) a[i] = i;

竞赛中的经验值：

  • int a[1000005] ≈ 4MB（通常安全）
  • int a[100000005] ≈ 400MB（多半超限）
  • C++ 一般内存限制 256MB，算一算就知道数组能开多大

38.5 最好、最坏和平均情况 ​

同一个算法，面对不同的输入，表现可能大不相同。

举个例子：在数组中查找目标值（线性查找）：

cpp
for (int i = 0; i < n; i++) {
    if (a[i] == target) break;  // 找到了就停
}
  • 最好情况：第一个就是 → O(1)
  • 最坏情况：最后一个才是，或者根本不在 → O(n)
  • 平均情况：大约检查 n/2 个 → 还是 O(n)（常数被忽略）

通常我们说一个算法的复杂度，如果没有特别说明，指的是最坏情况。但有些算法（比如快速排序）最好和最坏差别很大，需要重点区分。

✋ 动手试试 ​

试试 1：分析下面代码的时间复杂度。

cpp
int s = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        s++;

（提示：内层循环执行 1 + 2 + 3 + ... + n = n(n+1)/2 次 → O(n²)）

试试 2：写一个程序，输入 n，用 clock() 函数测量双重循环运行的时间。把 n 从 1000 翻倍到 2000，观察时间大约变成几倍？

试试 3：为什么 O(n²) 的排序只能处理 n ≤ 10⁴ 左右的数据，而 O(n log n) 能处理 n ≤ 10⁵～10⁶？用 n² 和 n log₂n 的值算一算。

⚠️ 容易犯的错 ​

错 1：把 O(2n) 当成比 O(n) 高一级 ​

❌ "两个 for 循环就是 O(2n)，比 O(n) 大一级"

✅ O(2n) 就是 O(n)，常数在大 O 里被忽略

错 2：忽略内层循环的变化 ​

❌ 认为 for(i=1;i<=n;i++) for(j=i;j<=n;j++) 是 O(n²)，但没注意到 j 从 i 开始，所以其实是 n + (n-1) + ... + 1 = n(n+1)/2 → 仍然是 O(n²)，这个判断碰巧对了，但如果内层范围变化更复杂就要仔细算

错 3：log n 的底数纠结 ​

❌ "二分查找到底是 O(log₂n) 还是 O(log₁₀n)？"

✅ 大 O 记号不区分底数，因为 logₐn = log₂n / log₂a，差一个常数因子，被大 O 吞掉。所以统一写成 O(log n)

错 4：用计时器判断算法复杂度 ​

❌ 在 Dev-C++ 里跑了 0.3 秒就以为算法是 O(1)

✅ 要在不同数据规模下测试，看增长趋势，而不是绝对值

📝 练习 ​

基础题 ​

1. 选择题

（1）以下哪个复杂度增长最快？
A. O(n)   B. O(n log n)   C. O(n²)   D. O(2ⁿ)

（2）for(int i=1;i<=n;i*=3) 的复杂度是：
A. O(n)   B. O(log n)   C. O(n²)   D. O(3ⁿ)

（3）空间复杂度的主要作用是：
A. 衡量程序运行时间   B. 衡量程序占用内存   C. 衡量代码行数   D. 衡量变量个数

2. 填空题

（1）双重循环（每层都从 1 到 n）的时间复杂度是 _____。

（2）在 n 个有序数中二分查找的时间复杂度是 _____。

（3）大 O 记号中，O(n² + n) 简化为 _____。

提高题 ​

3. 分析题 — 程序段复杂度判断

分析以下各段代码的复杂度（用大 O 记号）：

cpp
// (a)
for (int i = 1; i <= n; i += 2)
    for (int j = 1; j <= m; j++)
        doSomething();
cpp
// (b)
int i = n;
while (i > 1) {
    i = i / 2;
    doSomething();
}
cpp
// (c)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j *= 2)
        doSomething();

4. 思考题

某 O(n²) 算法在 n=1000 时跑了 1 秒。当 n=10000 时，大约需要多少秒？

挑战题 ​

5. 编程题 — 感受复杂度差异

写三个版本的"求最大子段和"（在 n 个整数中找一段连续子数组，使和最大）：

  • 版本 A：三重循环 O(n³)
  • 版本 B：两重循环 O(n²)
  • 版本 C：一遍扫描 O(n)（想想怎么做？提示：如果当前累加和变成负数，就舍弃前面的）

分别测试 n = 100, 1000, 10000，感受复杂度的实际影响。

🧠 本章小结 ​

时间复杂度 → 算法运行速度随数据规模的增长趋势

大 O 记号规则：
  - 只保留增长最快的项
  - 忽略常数和系数
  - O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)

空间复杂度 → 算法额外占用内存的量

三种情况：
  - 最好情况（最小代价）
  - 最坏情况（最大代价，最常用）
  - 平均情况（期望代价）

竞赛中 n 的规模与可用复杂度的经验：
  n ≤ 30     → O(2ⁿ) 也能过
  n ≤ 10³    → O(n²) 可行
  n ≤ 10⁵    → O(n log n) 可行
  n ≤ 10⁷    → O(n) 可行

📝 配套练习 ​

共3题（纸笔分析）。复杂度不是写出来的，是分析出来的。。★核心（课堂必做） ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心——拿M5旧题标注复杂度：百鸡O(n²)→O(n)、双指针O(n)、前缀和O(1)
◆ 拓展——给5段代码分析复杂度（单循环/嵌套/while/=2/递归）
◆ 拓展——判断：n=10^5时哪些算法能过1秒？（O(n)/O(nlogn)/O(n²)/O(2^n)）

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 2 道◆拓展题，覆盖不同变式和细节。

配套练习 ​

共3题（纸笔分析）。复杂度不是写出来的，是分析出来的。★核心（课堂必做） · ◆拓展（课后练习）

级别题号链接覆盖知识点
★ 核心——拿M5旧题标注复杂度：百鸡O(n²)→O(n)、双指针O(n)、前缀和O(1)
◆ 拓展——给5段代码分析复杂度（单循环/嵌套/while/=2/递归）
◆ 拓展——判断：n=10^5时哪些算法能过1秒？（O(n)/O(nlogn)/O(n²)/O(2^n)）

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 2 道◆拓展题，覆盖不同变式和细节。

自查清单：

  • [ ] 我能说出 5 种以上常见大 O 记号的含义
  • [ ] 我会通过数循环层数判断基本复杂度
  • [ ] 我理解为什么常数和低阶项在大 O 中被忽略
  • [ ] 我知道空间复杂度和时间复杂度的区别
  • [ ] 我能区分最好、最坏和平均情况
  • [ ] 我明白竞赛中复杂度分析为什么重要——它直接决定你能拿多少分

🚀 下章预告：学完了怎么衡量算法的快慢，接下来我们开始学具体的排序算法。最经典的三种 O(n²) 排序——冒泡、选择和插入——虽然速度不算最快，但它们是理解排序思想的起点。第 39 章，我们来看看它们各自是怎么"把一堆数排整齐"的。