Lesson 0012 · 复杂度分析入门

C++ 进阶 — 第 5 课

1. 什么是时间复杂度

不是精确时间（秒），是「增长趋势」—— 数据量翻倍，操作次数翻几倍？

这张表怎么读：只看最右边两列。n 从 1000 涨到 10000（翻 10 倍），O(n) 的工作量也翻 10 倍，O(n²) 翻 100 倍，而 O(log n) 只多了 10 次 —— 这就是「阶」的差别。

2. 你会碰到的复杂度

O(1) — 一步到位

int a = v[5];          // 数组按下标取值
st.push(x);            // 栈顶操作
cout << pq.top();     // 堆顶查看

O(n) — 扫一遍

for (int i = 0; i < n; i++)      // 一层循环
    sum += v[i];
v.push_back(x);                   // vector 末尾追加

O(n²) — 嵌套两层的循环

for (int i = 0; i < n; i++)      // 冒泡排序
    for (int j = 0; j < n; j++)
        ...

O(n log n) — sort 级别

sort(v.begin(), v.end());        // 标准排序
pq.push(x);  // 堆操作单次 O(log n)，n 次就是 O(n log n)

O(2ⁿ) — 选或不选的暴力枚举

// P1036 选数（选/不选每个元素）
void dfs(...) {
    dfs(idx+1, ...);   // 选
    dfs(idx+1, ...);   // 不选  → 每层分2叉，共 2ⁿ 条路
}

3. 怎么数循环

数循环只问两个问题：外层跑几次、内层每次跑几次。乘起来，再把常数和低次项丢掉，就是阶。下面六段，一段一段数。

① 一层循环 → O(n)

for (int i = 0; i < n; i++)      // 外层：跑 n 次
    sum += a[i];                  // 里面：做 1 件事

外层跑 n 次，内层每次只做一件固定的事（O(1)）。合起来 n × 1 = O(n)。

② 两段并列 → 还是 O(n)

for (int i = 0; i < n; i++) cnt++;   // 第一段：n 次
for (int j = 0; j < n; j++) cnt++;   // 第二段：n 次

这是加法不是乘法：n + n = 2n。系数 2 丢掉，还是 O(n)。规则是「并列取最大」—— 如果一段是 n、一段是 n²，答案就是 O(n²)，小的那一段被吃掉。

③ 两层都跑满 n → O(n²)

for (int i = 0; i < n; i++)          // 外层：n 次
    for (int j = 0; j < n; j++)      // 内层：每次都跑满 n 次
        cnt++;

外层每走一步，内层就跑一整圈 n 次。n × n = O(n²)。这就是冒泡、选择、插入这些双重循环的阶。

④ 内层跟着 i 走 → 仍然是 O(n²)

for (int i = 0; i < n; i++)          // 外层：n 次
    for (int j = 0; j < i; j++)      // 内层：跑 i 次，i 从 0 到 n-1
        cnt++;

内层的次数是 0 + 1 + 2 + … + (n−1) = n(n−1)/2。虽然只有一半，但 n(n−1)/2 里最高的项还是 n²，系数 1/2 丢掉 → O(n²)。「内层少跑一半」不等于降一阶。

⑤ 每次砍一半 → O(log n)

for (int i = n; i > 0; i /= 2)      // 循环变量每次变成一半
    cnt++;

n → n/2 → n/4 → … → 1。数「除几次才到 1」就是 log₂n，所以是 O(log n)。对照第 1 节那张表：n = 1000 时 log₂1000 差不多就是 10，和我们写的「~10」对得上。

⑥ 外层 n、内层砍半 → O(n log n)

for (int i = 0; i < n; i++)              // 外层：n 次
    for (int j = n; j > 0; j /= 2)       // 内层：log n 次
        cnt++;

外层 n 次 × 内层 log n 次 = O(n log n)。sort 之所以是这个阶，就是因为它做了大约 log n 轮、每轮扫 n 个元素。

六段收成一张表

4. 常见复杂度对照表

把前面的结论收在一起。这张表只有量级，不写毫秒 —— 同一阶换台机器能差好几倍，能比的只有「数据量翻 10 倍，工作量变几倍」。

最后一行没有「翻 10 倍」可言：数据每多一个，工作量就翻一倍，很快就谁也跑不动了。所以看到指数，先回头问一句「n 到底多大」。

5. 你学过的数据结构复杂度速查

6. 空间复杂度

同理 —— 额外用了多少内存。日常记两个：

vector<int> v(n);     // O(n) — 存 n 个
int memo[1001];        // O(1) — 固定大小，不随输入增长

注意「额外」两个字：输入数据本身占的那份不算，只算你为了算答案另外开的空间。memo[1001] 写死了一千个格子，输入再大也不涨，所以是 O(1)。

7. 实战判断

n = 100000, 二重循环 for(i) for(j) → O(n²) = 10¹⁰ 次 → 超时 💀
n = 100000, sort → O(n log n) ≈ 1.7×10⁶ 次 → 轻松 ✅
n = 20,     dfs 选/不选 → O(2²⁰) ≈ 10⁶ 次 → 能过 ✅
n = 1000,   二重循环 → O(n²) = 10⁶ 次 → 能过 ✅

这四行就是「先看 n 的范围，再看自己的阶」的完整流程。同样是二重循环，n = 1000 能过，n = 100000 就必超时 —— 阶没变，变的是 n。

8. 坑点清单

• 复杂度不是秒数：同一阶换台机器能差好几倍，能比的只有「数据量翻倍后工作量变几倍」。
• 别只数循环层数：单层不一定 O(n)（i /= 2 是 O(log n)），两层也不一定 O(n²)（内层只跑固定几次，合起来还是 O(n)）。
• 并列的循环是加法，不是乘法：两段各 n 次，合起来是 2n = O(n)；只留最大的那一项。
• 常数必须丢掉：2n 是 O(n)，n(n−1)/2 是 O(n²)，一半的平方还是平方。
• 空间复杂度只算「额外」：int memo[1001] 是 O(1)，vector<int> v(n) 才是 O(n)。
• 指数级别别硬上：O(2ⁿ) 的暴力枚举在 n 到 20 左右就封顶，先对第 1 节的洛谷经验法则。

9. 小测

10. 动手练习

1. 先猜后数：把第 3 节的六段代码抄进编辑器，每段先写一个猜测的阶，再按「外层几次 × 内层几次」手算一遍，对不上的地方标记出来。
2. 回头看旧代码：翻出 0011 的括号匹配（只有一层 for (char c : s)），数一数它是几阶；再想想为什么它没有跟着变慢。
3. 四行判断：用第 7 节那四行，分别写一句结论 —— 「n = 10⁵ 的二重循环」「n = 10⁵ 的 sort」「n = 20 的选/不选 DFS」「n = 10³ 的二重循环」，各自是过还是超时，理由是哪一条经验法则。
4. 选做：把 n(n−1)/2 代几个 n（10、100、1000）算出来，和 n²/2 比一比，看看差多少比例 —— 你会明白为什么系数可以扔。

卡住时的自查顺序

1. 先圈出循环变量：它每次怎么变？i++、i /= 2、还是别的？
2. 外层跑几次？把 n 代成 8 或 10 数一遍，别硬背。
3. 内层每次跑几次？固定、跟着 i 走、还是砍半？
4. 乘起来（并列的用加法），再把常数和低次项划掉。
5. 拿第 4 节的对照表核一下，阶写对了吗。
6. 还是不确定：把代码和你的数法一起贴过来，我们逐行对。

本课小结

• 时间复杂度 = 操作次数随数据量的增长趋势，不是秒数。
• 数循环三步：外层几次 × 内层几次 → 丢掉常数和低次项 → 定阶；并列的循环用加法、只留最大项。
• 三个易错点：i /= 2 是 O(log n)；内层 j < i 仍是 O(n²)；int memo[1001] 的空间是 O(1)。
• 洛谷经验：n ≤ 10⁵ 用 O(n log n)；n ≤ 10³ 用 O(n²)；n ≤ 20 用 O(2ⁿ)。
• 数据结构选择：查 vector 时想想能不能用 set；嵌套循环前想想能不能优化。