J-L20 算法概念与复杂度直觉¶

覆盖词条：KJ-29 ｜ 先修：J-L07/L09

什么是算法¶

算法是解决问题的有限、确定的操作步骤序列：有零个或多个输入、产生输出、每一步含义明确、必须在有限步内结束。

描述一个算法有三种常用方式：自然语言（像上面这句话）、流程图（用框和箭头画出行进路线）、伪代码（介于自然语言和程序之间的书写方式，例如）：

1
2
3
4
5
6
7

算法：找出三个数中的最大值 maxnum
输入：a, b, c
输出：最大值
1. m ← a
2. 若 b > m，则 m ← b
3. 若 c > m，则 m ← c
4. 返回 m

同一个问题往往有很多种算法，好坏差别巨大——衡量好坏的尺子就是复杂度。

分析方法：逐层计数法¶

时间复杂度数的是基本操作的执行次数随输入规模 \(n\) 增长的量级。方法只有一招——逐层计数：

1. 把每一层循环的执行次数写成含 \(n\) 的式子；
2. 嵌套的循环把各层次数相乘，并列的代码段把次数相加；
3. 化简时舍去常数和低阶项，只留增长最快的最大项，记作 \(O(\text{最大项})\)。

例如 for i=1..n 里再套 for j=1..n：内层次数是 \(n\)，外层执行 \(n\) 次，总次数 \(n \times n = n^2\)，记 \(O(n^2)\)。后面所有法则用的都是这一招。

基础法则¶

常见复杂度排序¶

\(n = 10^5\) 时，\(O(n)\) 约 10 万次运算（眨眼间），\(O(n^2)\) 约 100 亿次（数分钟以上），\(O(n!)\) 宇宙热寂也算不完——量级差一点，天壤之别。

法则 1：顺序执行，取最大项¶

1
2
3

for (int i = 1; i <= n; i++) cnt1++;        // O(n)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) cnt2++;    // O(n^2)

复杂度：\(O(n) + O(n^2) = O(n^2)\)。并列的代码段次数相加，化简时低阶项丢掉，只留最大项。

法则 2：常数倍不改变量级¶

1
2

for (int i = 1; i <= 2 * n; i++) cnt++;     // 2n 次
for (int i = 1; i <= n / 2; i++) cnt++;     // n/2 次

复杂度：都是 \(O(n)\)。\(2n\) 与 \(n/2\) 随 \(n\) 增长的速度一样，大 O 只看量级、不看常数——但实际做题时，常数过大仍可能超时，这叫「卡常数」。

法则 3：\(10^8\) 估算法则¶

评测机 1 秒大约能执行 \(10^8\) 次简单运算。拿到题先看数据范围，再反推需要什么复杂度：

循环结构定级¶

法则 4：单层循环 → \(O(n)\)¶

1

for (int i = 1; i <= n; i++) cnt++;

复杂度：\(O(n)\)。循环 \(n\) 次，次数就是 \(n\)。

法则 5：\(k\) 层独立嵌套 → \(O(n^k)\)¶

1
2
3

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        for (int k = 1; k <= n; k++) cnt++;

复杂度：\(O(n^3)\)。每层都独立跑 \(n\) 次，逐层相乘：\(n \times n \times n\)。

法则 6：三角形循环 → \(O(n^2)\)¶

1
2

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) cnt++;     // j 从 i 开始，不是从 1

复杂度：内层次数为 \(n-i+1\)，总次数 \(n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}\)，约 \(0.5n^2\) → \(O(n^2)\)。等差数列求和是嵌套循环最常见的化简。

法则 7：倍增循环 → \(O(\log n)\)¶

1

for (int i = 1; i <= n; i *= 2) cnt++;      // i: 1, 2, 4, 8, ...

复杂度：\(O(\log n)\)。\(i\) 每次翻倍，翻 \(k\) 次得 \(2^k \ge n\)，所以 \(k = \log_2 n\)——循环次数是对数。凡是「每次把规模砍半或翻倍」的结构都是 \(\log n\)。

法则 8：外层 \(n\) 层循环 × 内层 \(\log n\) → \(O(n\log n)\)¶

1
2

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j *= 2) cnt++;

复杂度：\(O(n\log n)\)。最常见于排序——很多「分治 + 合并」类算法都是这个量级。

法则 9：双指针相加 → \(O(n)\)¶

1
2
3
4
5

int i = 1, j = n;               // i 只向右、j 只向左
while (i < j) {
    if (check(i, j)) j--;
    else i++;
}

复杂度：\(O(n)\)。容易误判成 \(O(n^2)\)，但 \(i\) 和 \(j\) 是此消彼长：两个指针移动的总次数不超过 \(n\)，是相加关系。反面教材：若内层每次都从头扫一遍（独立执行 \(n\) 次），就是相乘，\(O(n^2)\)——判断双指针，只看「每个指针总共移动多少步」。

级数与对数¶

法则 10：调和级数 → \(O(n\log n)\)¶

1
2

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i) cnt++;  // j = i, 2i, 3i, ...

复杂度：内层次数 \(\frac{n}{i}\)，总次数

括号里叫调和级数 \(H_n\)，增长速度约等于 \(\ln n\)。所以总量级是 \(O(n\log n)\)——「看起来像两层 \(n\)」但实际是 \(n \log n\)，这是第一个「奇怪复杂度」。

法则 11：埃氏筛 → \(O(n\log\log n)\)¶

1
2
3

for (int i = 2; i <= n; i++)
    if (isPrime[i])                         // 只有素数才向后筛
        for (int j = 2 * i; j <= n; j += i) isComposite[j] = true;

复杂度：和法则 10 结构一样，但内层只对素数 \(p\) 执行，总次数 \(\sum_{p \le n} \frac{n}{p} \approx n\ln\ln n\)，即 \(O(n\log\log n)\)。直觉：\(1 \sim n\) 中素数约 \(\frac{n}{\ln n}\) 个（密度约 \(\frac{1}{\ln n}\)），素数的倒数之和增长极慢，只有 \(\ln\ln n\)——比 \(n\log n\) 还快得多。筛法详见 J-L32。

法则 12：线性筛 → \(O(n)\)¶

1

// 每个合数只被它的最小质因数筛掉一次，因此总次数恰为 O(n)

复杂度：\(O(n)\)，比埃氏筛更快。思路与代码在 J-L32 数论课展开，这里记住结论：筛法可以做到严格线性。

法则 13：几何级数 → \(O(n)\)¶

1
2

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++) cnt++;      // 内层次数 = i

复杂度：内层次数是 \(1, 2, 4, 8, \ldots\)，总次数 \(1 + 2 + 4 + \cdots + 2^k \approx 2^{k+1} \le 2n\)，是等比数列求和 → \(O(n)\)。对数循环外面套一层「和它一样大」的循环，总量级只翻常数倍。

递归的复杂度直觉¶

法则 14：\(T(n) = T(n-1) + O(n) \to O(n^2)\)¶

1
2
3
4
5
6

int sum(int n) {
    if (n == 0) return 0;
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;    // 本层 O(n)
    return s + sum(n - 1);                  // 递归 O(n) 次
}

复杂度：\(n + (n-1) + \cdots + 1 = O(n^2)\)。递归展开成 \(n\) 层，每层工作量构成等差数列。

法则 15：\(T(n) = 2T(n-1) + O(1) \to O(2^n)\)¶

1
2
3
4
5

void f(int n) {
    if (n == 0) return;
    f(n - 1);                               // 每层分裂成两份
    f(n - 1);
}

复杂度：调用次数 \(1 + 2 + 4 + \cdots + 2^n = O(2^n)\)。指数级增长——\(n = 40\) 就已经是万亿级，这类搜索必须靠剪枝（J-L26 / S-L13）。

法则 16：\(T(n) = 2T(n/2) + O(n) \to O(n\log n)\)¶

1
2
3
4
5
6

void solve(int n) {
    if (n == 1) return;
    solve(n / 2);                           // 问题减半
    solve(n / 2);
    for (int i = 0; i < n; i++) cnt++;      // 合并代价 O(n)
}

复杂度：递归深度 \(\log n\) 层，每层的总合并代价都是 \(O(n)\)，相加得 \(O(n\log n)\)。归并排序就是这个模型（S-L09）。

10⁸ 估算与空间复杂度¶

空间复杂度¶

内存按字节计算，128MB ≈ \(1.3 \times 10^8\) 字节 ≈ \(3 \times 10^7\) 个 int。开数组前先估算：f[10000][10000] 是 \(10^8\) 个 int ≈ 400MB，直接 MLE。空间复杂度的数法与时间相同，只是数的是格子数而不是运算次数。

常见陷阱¶

• 时间和空间都要估算：一个 \(O(n\log n)\) 但开了 f[n][n] 的做法照样死在内存上；
• 递归也有空间代价：法则 15 的递归深度是 \(O(n)\)，栈空间同样要算在内。