第9章算法复杂度分析

🎯 本章学习目标

通过本章的学习，你将能够：

理解大O表示法：掌握时间复杂度和空间复杂度的定义
掌握三条法则：熟练运用顺序、循环、分支结构的复杂度分析
熟悉常见等级：记住 O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) 等的增长顺序
分析循环复杂度：能快速判断单层、多层嵌套循环的复杂度
分析递归复杂度：能用递归树法分析递归算法的时间复杂度
区分三种情况：理解最好、最坏、平均时间复杂度的区别
掌握空间复杂度：能分析算法的空间占用，理解递归栈空间
根据数据规模反推：能根据 n 的范围反推应该用什么复杂度的算法
了解时空权衡：理解空间换时间的思想（记忆化、前缀和、哈希等）
应对真题题型：能解决选择、程序阅读等各类复杂度题目

🗺️ 本章知识图谱

算法复杂度分析
├── 大 O 表示法
│   ├── 定义：最坏情况下的上界
│   ├── 忽略常数系数和低阶项
│   └── 三条法则：顺序相加、循环相乘、分支取大
├── 常见复杂度等级
│   ├── 常数阶 O(1)
│   ├── 对数阶 O(log n)
│   ├── 线性阶 O(n)
│   ├── 线性对数阶 O(n log n)
│   ├── 平方阶 O(n²)
│   ├── 立方阶 O(n³)
│   ├── 指数阶 O(2ⁿ)
│   └── 阶乘阶 O(n!)
├── 时间复杂度分析
│   ├── 循环结构
│   │   ├── 单层循环 O(n)
│   │   ├── 嵌套循环 O(nᵏ)
│   │   └── 倍增/折半 O(log n)
│   ├── 递归结构
│   │   ├── 递归树法
│   │   └── 主定理（了解）
│   └── 三种情况
│       ├── 最好情况
│       ├── 最坏情况（大O关注）
│       └── 平均情况
├── 空间复杂度分析
│   ├── 辅助空间
│   ├── 递归栈空间
│   └── in-place（原地算法）
├── 数据规模反推
│   ├── n ≤ 20 → O(2ⁿ)
│   ├── n ≤ 1000 → O(n²)
│   ├── n ≤ 1e5 → O(n log n)
│   └── n ≤ 1e9 → O(log n)
└── 时空权衡
    ├── 记忆化搜索
    ├── 前缀和
    ├── 哈希表
    └── 用空间换时间

一、为什么需要复杂度分析？🤔

同样是"在 n 个数里找一个数"：

从头到尾挨个找 → 平均要看 n/2 个数
二分查找（前提：有序）→ 最多看 log₂n 个数

当 n = 100 万时，前者要看 50 万次，后者只要约 20 次！差距是几万倍。

这就是复杂度的意义：脱离具体机器、编程语言，只看算法本身随数据规模增长的趋势。

💡 核心思想：复杂度关心的是"当 n 趋向无穷大时，运行时间/空间如何增长"，所以常数系数、低阶项都可以忽略。

二、大 O 表示法基础

2.1 定义

大 O 表示法用于描述算法在最坏情况下运行时间（或占用空间）随输入规模 n 增长的上界。

数学定义：若存在正常数 C 和 n₀，使得对所有 n ≥ n₀，都有 T(n) ≤ C · f(n)，则记 T(n) = O(f(n))。

翻译成大白话：

O(f(n)) 表示"增长速度不超过 f(n)"
忽略常数系数：3n → O(n)，5n² → O(n²)
只保留最高阶项：n² + 10n + 100 → O(n²)

2.2 三条基本法则

法则	说明	例子
顺序结构	各段复杂度相加，取最高阶	O(n) + O(n²) = O(n²)
循环结构	循环体复杂度 × 循环次数	一层循环 n 次，循环体 O(1) → O(n)
分支结构	取各分支中最大复杂度	if-else 两个分支 O(n) 和 O(n²) → O(n²)

2.3 常见复杂度等级（⭐ 必背！）

按增长率从慢到快排列：

复杂度	名称	典型算法 / 场景	n=10 时大致操作数	n=100 时
O(1)	常数复杂度	数组随机访问、哈希表查找	1	1
O(log n)	对数复杂度	二分查找、平衡树、GCD	~3	~7
O(n)	线性复杂度	单层循环、线性查找	10	100
O(n log n)	线性对数复杂度	归并排序、快速排序（平均）	~33	~664
O(n²)	平方复杂度	冒泡/选择/插入排序、双层循环	100	10,000
O(n³)	立方复杂度	三层循环、Floyd 最短路	1,000	1,000,000
O(2ⁿ)	指数复杂度	递归枚举子集、朴素斐波那契	1,024	~1.27×10³⁰
O(n!)	阶乘复杂度	暴力全排列	3,628,800	天文数字

🎯 增长率排序（必须记住）： O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

2.4 增长趋势示意（ASCII 图）

操
作
数
    │
    │                                            ■ 2^n (爆炸式增长)
    │                                       ■
    │                                  ■
    │                             ■
    │                        ■
    │                   ■
    │              ■
    │         ■
    │        ╱■ n²
    │       ╱
    │      ╱
    │     ╱
    │    ╱
    │   ╱
    │  ╱
    │ ╱─── n log n
    │╱
    │╲ n (斜线)
    │ ╲
    │  ● log n (几乎平)
    │  ●
    │  ● O(1) (水平线)
    └──────────────────────────────────── 输入规模 n →

💡 直观记忆：log n 几乎是平的，n 是斜线，n² 是抛物线，2ⁿ 直接冲天。

三、多项式复杂度 📐

3.1 定义

若算法的时间是 n 的多项式函数，即 O(nᵏ)（k 为非负整数），则称为多项式复杂度。

O(1)：k=0
O(n)：k=1
O(n²)：k=2
O(n³)：k=3
以此类推……

⚠️ O(√n) = O(n^{0.5}) 虽然不是整数次幂，但通常也归入"多项式量级"讨论（如试除法判素数）。

3.2 嵌套循环分析（核心技巧）

规则：看最内层循环体被执行的总次数。

① O(1)——无循环或循环次数固定

cpp

int getFirst(int a[], int n) {
    return a[0]; // 无论 n 多大，只执行 1 次
}

② O(n)——一层循环跟 n 成正比

cpp

long long sum(int a[], int n) {
    long long s = 0;
    for (int i = 0; i < n; i++) { // 循环 n 次
        s += a[i];                // 每次 O(1)
    }
    return s;
}

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

cpp

// 冒泡排序核心
void bubbleSort(int a[], int n) {
    for (int i = 0; i < n; i++) {              // 外层 n 次
        for (int j = 0; j < n - i - 1; j++) {  // 内层平均约 n/2 次
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }
}
// 总执行次数 ≈ n + (n-1) + ... + 1 = n(n-1)/2 = O(n²)

④ O(n³)——三层嵌套

cpp

// 矩阵乘法 C = A × B，A、B、C 均为 n×n
void matrixMul(int A[][N], int B[][N], int C[][N], int n) {
    for (int i = 0; i < n; i++) {          // n
        for (int j = 0; j < n; j++) {      // n
            C[i][j] = 0;
            for (int k = 0; k < n; k++) {  // n
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}
// 总次数 = n × n × n = n³ → O(n³)

⑤ 非均匀嵌套——注意内层不是 n

cpp

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) { // j 从 0 到 i-1
        // ...
    }
}
// 总次数 = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)

⚠️ 常见陷阱：不是"两层循环就一定是 O(n²)"！要看内层循环的实际次数。
例如 for (int j = 1; j < n; j *= 2) 即使嵌套在 n 次外层循环里，整体也是 O(n log n)。

四、对数复杂度 🌲

4.1 O(log n) 从哪里来？

关键特征：每次循环把问题规模"折半"（或缩小固定比例）。

cpp

// 二分查找（在升序数组 a 中找 x）
int binarySearch(int a[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2; // 防止溢出
        if (a[mid] == x) return mid;
        else if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

分析：每次循环后区间长度变为原来的一半。设循环 k 次后区间长度为 1：

n × (1/2)^k = 1  →  k = log₂n

所以时间复杂度为 O(log n)。

💡 对数的底数不影响大 O：log₂n、log₁₀n、ln n 之间只差常数倍，统一写成 O(log n)。

4.2 其他 O(log n) 场景

场景	为什么是 log n
平衡二叉搜索树（AVL、红黑树）查找	树高 ≈ log₂n
欧几里得 GCD 算法	每两步数值至少减半
快速幂（a^b mod m）	指数 b 每次折半
堆操作（push_heap / pop_heap）	堆高 log₂n

cpp

// 快速幂：计算 base^exp % mod
long long qpow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1; // 指数折半
    }
    return result;
}
// 循环次数 = log₂(exp) → O(log exp)

4.3 O(n log n)——分治的产物

O(n log n) = "外层 n 的工作" × "每次折半到 1 需要 log n 层"。

典型代表：归并排序

cpp

void merge(int a[], int l, int mid, int r) {
    // 合并两个有序区间，O(n)
    int i = l, j = mid + 1, k = 0;
    int* tmp = new int[r - l + 1];
    while (i <= mid && j <= r) {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = 0; t < k; t++) a[l + t] = tmp[t];
    delete[] tmp;
}

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid);       // 排序左半
    mergeSort(a, mid + 1, r);   // 排序右半
    merge(a, l, mid, r);        // 合并 O(n)
}

为什么是 O(n log n)？

递归共 log₂n 层（每次把数组分两半）
每层所有 merge 加起来总共处理 n 个元素
总工作量 = 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)

快速排序平均也是 O(n log n)，最坏 O(n²)（见后文"最好/最坏/平均"一节）。

五、指数复杂度 💥

5.1 O(2ⁿ) 的典型来源：递归枚举子集

cpp

// 枚举一个集合的所有子集
void enumerateSubsets(int a[], int n, int i, vector<int>& current) {
    if (i == n) {
        // 处理当前子集（输出等）
        return;
    }
    // 不选第 i 个元素
    enumerateSubsets(a, n, i + 1, current);
    // 选第 i 个元素
    current.push_back(a[i]);
    enumerateSubsets(a, n, i + 1, current);
    current.pop_back();
}

每个元素有"选/不选"两种可能，n 个元素共 2ⁿ 个子集 → O(2ⁿ)。

5.2 朴素斐波那契：经典的 O(2ⁿ) 反例

cpp

// ❌ 朴素递归：存在大量重复计算
long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

递归树中，fib(n) 会分裂成 fib(n-1) 和 fib(n-2)，总调用次数呈指数增长，约为 O(2ⁿ)。

当 n = 50 时，调用次数已超过 200 亿次，根本跑不完！

5.3 为什么指数复杂度"不可接受"？

n	O(n)	O(n²)	O(2ⁿ)
10	10	100	1,024
20	20	400	~100 万
30	30	900	~10 亿
50	50	2,500	~1×10¹⁵
100	100	10,000	~1×10³⁰

计算机每秒约执行 10⁸ 次基本操作：

O(n) 在 n=10⁸ 时约 1 秒
O(n²) 在 n=10⁴ 时约 1 秒
O(2ⁿ) 在 n=30 时就要约 10 秒，n=40 就需要十几分钟

⚠️ 结论：指数复杂度只在 n 非常小（通常 n ≤ 20）时才能通过。一旦 n 更大，必须寻找多项式算法（如动态规划）。

六、空间复杂度 📦

6.1 定义

空间复杂度衡量算法运行过程中临时占用的存储空间随 n 增长的趋势，同样用大 O 表示。

注意：

输入数据本身占用的空间通常不计入空间复杂度
只计算辅助空间（额外申请的空间）

6.2 常见例子

算法	辅助空间	说明
冒泡 / 选择 / 插入排序	O(1)	只用几个临时变量
归并排序	O(n)	需要一个等大的临时数组合并
快速排序（递归）	O(log n)	递归栈深度平均 log n
n 阶 DP（一维）	O(n)	dp 数组大小 n
n×n 二维 DP	O(n²)	dp 表大小 n×n
DFS / BFS 遍历图	O(V)	visited 数组、栈/队列

6.3 递归栈空间

递归调用会在系统栈上为每层保存参数、局部变量、返回地址，因此递归深度 = 栈空间复杂度。

cpp

// 计算 1+2+...+n 的递归写法
long long sum(int n) {
    if (n == 1) return 1;
    return n + sum(n - 1);
}
// 递归深度 n → 栈空间 O(n)

cpp

// 二分查找式递归（如归并排序）
void f(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    f(l, mid);
    f(mid + 1, r);
}
// 递归深度 log₂n → 栈空间 O(log n)

⚠️ 栈溢出：递归深度过大会导致 Stack Overflow。GESP 五级真题曾考："递归层次过深可能耗尽栈空间"——这是正确说法；而"栈溢出时程序会抛出异常并可继续执行"是错误的（程序会直接崩溃）。

6.4 In-place（原地）算法

若算法的辅助空间为 O(1)（即不随 n 增长），称为 in-place（原地）算法。

✅ 冒泡排序、选择排序、插入排序、快速排序都是 in-place
❌ 归并排序不是 in-place（需要 O(n) 辅助数组）

💡 快速排序虽然递归需要 O(log n) 栈空间，但通常仍被视为 in-place（因为它不需要额外的数组来存放数据）。

七、递归算法复杂度分析 🔁

递归算法的复杂度分析有两件利器：递归树法和主定理。

7.1 方法一：递归树法

步骤：

画出递归调用树
每一层的工作量 = 该层所有节点的工作量之和
总复杂度 = 所有层工作量之和

例 1：归并排序 T(n) = 2T(n/2) + O(n)

                    n              第0层：工作量 n
                  /   \
                n/2   n/2          第1层：工作量 n/2 + n/2 = n
               /  \   /  \
             n/4 n/4 n/4 n/4       第2层：工作量 n
              ...  ...  ...
             共 log₂n 层，每层工作量 n
             
总工作量 = n × log n = O(n log n)

例 2：朴素斐波那契 T(n) = T(n-1) + T(n-2) + O(1)

                    fib(n)
                   /      \
             fib(n-1)    fib(n-2)
             /     \       /    \
        fib(n-2) fib(n-3) ...   ...

树高约 n
第 k 层最多有 2ᵏ 个节点
节点总数 ≤ 2⁰ + 2¹ + ... + 2ⁿ = 2ⁿ⁺¹ - 1
→ O(2ⁿ)

7.2 方法二：主定理（Master Theorem）

📚 拓展 · 超纲：主定理属提高内容，五级考纲只要求"含多项式、对数的复杂度估算"。能识别 T(n)=aT(n/b)+f(n) 的常见形式即可，不要求严格推导。

对于形如

T(n) = a · T(n/b) + f(n)

的递归式（其中 a ≥ 1，b > 1，f(n) 是分解/合并的代价），主定理给出三种情况：

设 crit = log_b a（即 n^{log_b a}），比较 f(n) 与 n^{crit}：

情况	条件	结论	直觉
①	f(n) = O(n^{crit - ε})，ε>0（f 更"轻"）	T(n) = Θ(n^{crit})	叶子节点主导
②	f(n) = Θ(n^{crit} · logᵏ n)，k≥0（同阶）	T(n) = Θ(n^{crit} · log^{k+1} n)	两者相当，多乘 log
③	f(n) = Ω(n^{crit + ε})，ε>0（f 更"重"），且满足正则条件	T(n) = Θ(f(n))	根节点主导

💡 GESP 五级不需要严格证明，能识别最常见的形式即可。

7.3 主定理常见例子

递归式	a	b	crit = log_b a	f(n)	情况	结果
二分查找 T(n)=T(n/2)+O(1)	1	2	0	O(1)=O(n⁰)	②(k=0)	O(log n)
归并排序 T(n)=2T(n/2)+O(n)	2	2	1	O(n)=O(n¹)	②(k=0)	O(n log n)
二分递归+线性扫描 T(n)=2T(n/2)+O(1)	2	2	1	O(1) 更轻	①	O(n)
Strassen 矩阵乘法 T(n)=7T(n/2)+O(n²)	7	2	≈2.81	O(n²) 更轻	①	O(n^2.81)
不当递归 T(n)=2T(n/2)+O(n²)	2	2	1	O(n²) 更重	③	O(n²)

7.4 斐波那契：O(2ⁿ) → O(n) 的飞跃

① 朴素递归（O(2ⁿ)，❌）：前面已讲，大量重复计算。

② 记忆化搜索（O(n)，✅）：用数组记录已算过的值。

cpp

#include <iostream>
#include <algorithm>
using namespace std;

long long memo[105]; // 记忆化数组

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // 已算过，直接返回
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    fill(memo, memo + 105, -1); // 初始化为"未计算"
    cout << fib(50) << endl;    // 瞬间出结果
    return 0;
}

每个 fib(i) 只计算一次，共计算 n 个值 → 时间 O(n)，空间 O(n)。

③ 递推迭代（O(n) 时间 + O(1) 空间，✅✅）：

cpp

long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

🎯 对比总结：
方法时间空间
朴素递归 O(2ⁿ) ❌ O(n)
记忆化搜索 O(n) ✅ O(n)
递推迭代 O(n) ✅ O(1) ✅
这就是典型的时空权衡——用记忆化的 O(n) 空间，把 O(2ⁿ) 时间降到了 O(n)。

方法	时间	空间
朴素递归	O(2ⁿ) ❌	O(n)
记忆化搜索	O(n) ✅	O(n)
递推迭代	O(n) ✅	O(1) ✅

八、最好 / 最坏 / 平均情况

很多算法在不同输入下表现不同。以快速排序为例：

8.1 快速排序回顾

cpp

int partition(int a[], int l, int r) {
    int pivot = a[r];      // 选最右元素为基准
    int i = l - 1;
    for (int j = l; j < r; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}

void quickSort(int a[], int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

8.2 三种情况

情况	输入特征	递归树形态	复杂度
最好	每次 pivot 都把数组均分（在中间）	完美平衡二叉树，log n 层	O(n log n)
平均	随机输入	大致平衡	O(n log n)
最坏	数组已有序（或逆序），pivot 每次在端点	斜树，只有一个子问题，n 层	O(n²)

⚠️ 考点提示：题目若只问"快速排序的时间复杂度"，通常默认填 O(n log n)；若明确问"最坏情况"，则答 O(n²)。归并排序没有最坏情况退化问题，始终是 O(n log n)，这是它相对于快排的优势之一。

其他常见三态算法：

算法	最好	平均	最坏
冒泡排序（已优化）	O(n)	O(n²)	O(n²)
插入排序	O(n)	O(n²)	O(n²)
选择排序	O(n²)	O(n²)	O(n²)
线性查找	O(1)	O(n)	O(n)
二分查找	O(1)	O(log n)	O(log n)

九、根据数据范围反推复杂度（⚡ 实战核心技能）

这是选择题中最实用的技巧：看到题目给的数据范围，立刻判断什么复杂度能过。

9.1 经验表（以"1 秒 ≈ 10⁸ 次操作"估算）

数据规模 n	可接受的复杂度	对应算法
n ≤ 10	O(n!)、O(2ⁿ)	暴力全排列、子集枚举
n ≤ 20	O(2ⁿ)、O(n!)	状压 DP、暴力搜索
n ≤ 100	O(n⁴) 勉强，O(n³) 稳妥	三层循环 DP
n ≤ 1,000	O(n²)、O(n² log n)	双层循环、 floyd
n ≤ 10⁴	O(n²) 极限	冒泡/选择排序上限
n ≤ 10⁵	O(n log n)	归并/快排、二分
n ≤ 10⁶	O(n log n) 或 O(n)	排序、线性扫描、哈希
n ≤ 10⁷	O(n)	只能线性扫描
n ≤ 10⁹	O(log n)、O(1)	二分、数学公式、快速幂

9.2 记忆口诀

n ≤ 20 → 指数算法还能救
n ≤ 100 → O(n⁴) 也能凑
n ≤ 1000 → O(n³) 正合适
n ≤ 1e5 → 必须 n log n
n ≤ 1e6 → n log n 是底线
n ≤ 1e9 → 只能 log n

9.3 实战判断流程

拿到题目
   │
   ├── 看 n 多大？
   │
   ├── n ≤ 20  → 可以写 DFS / 状压 DP（O(2ⁿ) 或 O(n·2ⁿ)）
   ├── n ≤ 100 → 可以写 O(n³)（如 Floyd、区间 DP）
   ├── n ≤ 1000 → 可以写 O(n²)（双重循环 DP）
   ├── n ≤ 1e5 → 必须 O(n log n)（排序、二分、堆）
   ├── n ≤ 1e6 → 必须 O(n log n) 或 O(n)
   └── n > 1e8 → 必须 O(log n) 或 O(1)（二分/数学）

🎯 GESP 真题套路：题目给 n ≤ 10⁵，选项出现 O(n²)——直接排除；给 n ≤ 20，出现 O(2ⁿ)——可能正确。

十、时空权衡 🔄

时空权衡（Time-Space Tradeoff）：用更多的存储空间来换取更快的运行时间，是算法优化的核心思想之一。

10.1 记忆化（Memoization）

前面斐波那契的例子：用 O(n) 数组记住已算结果，把 O(2ⁿ) 降到 O(n)。

10.2 预处理 / 前缀和

cpp

// 问题：多次查询数组区间 [l, r] 的和
// 朴素：每次遍历 O(n)，查询 m 次 → O(nm)
// 前缀和：预处理 O(n)，每次查询 O(1)，共 O(n + m)

int a[MAXN], pre[MAXN];

void buildPrefix(int n) {
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i]; // 预处理
    }
}

int rangeSum(int l, int r) {
    return pre[r] - pre[l - 1]; // O(1) 查询
}

用 O(n) 的 pre 数组，把查询从 O(n) 降到 O(1)。

10.3 哈希表：O(1) 查找的代价

cpp

#include <unordered_map>
using namespace std;

// 在数组中找两个数之和为 target
// 朴素：双重循环 O(n²)，O(1) 空间
// 哈希：一遍扫描 O(n)，O(n) 空间
bool twoSum(int a[], int n, int target) {
    unordered_map<int, bool> seen;
    for (int i = 0; i < n; i++) {
        if (seen.count(target - a[i])) return true;
        seen[a[i]] = true;
    }
    return false;
}

10.4 常见时空权衡策略

策略	空间代价	时间收益
记忆化搜索	O(状态数)	指数 → 多项式
前缀和 / 差分	O(n)	区间查询 O(1)
哈希表	O(n)	查找 O(1)
打表（预处理所有答案）	O(答案范围)	查询 O(1)
动态规划（vs 递归）	O(状态数)	避免重复子问题
计数排序	O(值域)	O(n + 值域)

💡 编程中的平衡：空间有限时不能一味"以空间换时间"；时间紧迫时，适当的预处理可以救命。要根据题目限制灵活选择。

十一、看代码判复杂度——实战技巧 🧐

GESP 选择题常给一段代码问复杂度。按以下步骤分析：

找循环：一层循环看跟谁成正比（n？log n？固定？）
看嵌套：嵌套循环把各层次数相乘
注意折半：循环变量 i *= 2 或 i /= 2 → log n
注意递归：写出递归式，用递归树/主定理
取最坏：大 O 描述的是最坏情况（除非特别说明）
忽略常量：3n、100n、n+5 都是 O(n)

示例分析

cpp

for (int i = 1; i < n; i *= 2) {     // 执行 log₂n 次
    for (int j = 0; j < n; j++) {    // 每次 n 次
        // O(1) 操作
    }
}
// 总次数 = log₂n × n = O(n log n)

cpp

for (int i = 1; i < n; i++) {
    for (int j = i; j < n; j *= 2) {
        // 注意 j 从 i 开始倍增
    }
}
// 外层 n 次，内层最多 log n 次 → O(n log n)

cpp

for (int i = 1; i < n; i++) {
    for (int j = 0; j < n; j += i) {
        
    }
}
// i=1: n 次；i=2: n/2 次；... i=n: 1 次
// 总和 = n(1 + 1/2 + 1/3 + ... + 1/n) ≈ n ln n = O(n log n)

⚠️ 调和级数：1 + 1/2 + 1/3 + ... + 1/n ≈ ln n，是 O(log n) 量级，考试中偶尔出现。

十二、📝 实战练习

练习题 1（程序阅读题）

题目： 阅读以下两个判断素数的函数，回答问题。

cpp

#include <iostream>
using namespace std;

bool isPrimeA(int N) {
    if (N < 2) return false;
    for (int i = 2; i < N; i++) {
        if (N % i == 0) return false;
    }
    return true;
}

bool isPrimeB(int N) {
    if (N < 2) return false;
    for (int i = 2; i * i <= N; i++) {
        if (N % i == 0) return false;
    }
    return true;
}

关于两个函数的时间复杂度，下列说法正确的是（）

A. isPrimeA 更优，时间复杂度为 O(N)
B. isPrimeB 更优，时间复杂度为 O(√N)
C. 两个函数时间复杂度相同，都是 O(N)
D. isPrimeA 更优，时间复杂度为 O(√N)

🔑 点击查看答案与解析

答案： B

isPrimeA：for 循环 i 从 2 到 N-1，最坏（N 是素数）执行 N-2 次 → O(N)
isPrimeB：for 循环 i 从 2 到 √N，最坏执行 √N-1 次 → O(√N)
O(√N) < O(N)，所以 isPrimeB 更优。

🎯 此题是 GESP 五级经典真题，核心是识别 试除法判素数优化到 √n。

--- ### 练习题 2（单选题）

题目： 下列代码的时间复杂度为（）

cpp

for (int i = 1; i < n; i *= 2) {
    cout << i << " ";
}

A. O(n)　　B. O(log n)　　C. O(n log n)　　D. O(n²)

🔑 点击查看答案与解析

答案： B

循环变量 i 每次翻倍：1, 2, 4, 8, ..., 直到 ≥ n。共执行 log₂n 次，每次 O(1) → O(log n)。

--- ### 练习题 3（单选题）

题目： 下列关于归并排序和快速排序的叙述，正确的是（）

A. 归并排序最坏情况下时间复杂度为 O(n²) B. 快速排序在任何情况下都是 O(n log n) C. 归并排序需要 O(n) 的辅助空间，快速排序平均时间复杂度 O(n log n) D. 快速排序是稳定排序，归并排序是不稳定排序

🔑 点击查看答案与解析

答案： C

A 错：归并排序始终是 O(n log n)，不会退化。
B 错：快排最坏（有序数组 + 端点 pivot）为 O(n²)。
C 正确：归并需要临时数组合并 O(n) 空间；快排平均 O(n log n)。
D 错：说反了——归并稳定，快排不稳定。

---

练习题 4（单选题）

题目： 某题数据规模为 n ≤ 20，要求统计一个集合中满足某条件的子集个数。下列复杂度中最合适的是（）

A. O(n!)　　B. O(2ⁿ)　　C. O(n³)　　D. O(n log n)

🔑 点击查看答案与解析

答案： B

子集总数为 2ⁿ，枚举子集的复杂度自然是 O(2ⁿ)。
n=20 时 2²⁰ ≈ 10⁶（约 100 万），在 1 秒内可完成。
O(n!) 一般用于全排列问题；n ≤ 20 时 O(2ⁿ) 最贴合子集枚举场景。
如果题目允许，也可以用状压 DP 在 O(n·2ⁿ) 内解决，但基础枚举就是 O(2ⁿ)。

💡 这就是"根据数据范围反推复杂度"的典型应用：n=20 是 O(2ⁿ) 的标志性信号。

--- ### 练习题 5（单选题）

题目： 已知递归关系 T(n) = 2T(n/2) + O(n)，且 T(1) = O(1)。则 T(n) = （）

A. O(log n)　　B. O(n)　　C. O(n log n)　　D. O(n²)

🔑 点击查看答案与解析

答案： C

这是最经典的主定理形式：

a = 2，b = 2，crit = log₂2 = 1
f(n) = O(n) = O(n¹)，与 $n^{crit}$ 同阶 → 主定理第 ② 种情况（k=0）
结果 = Θ(n¹ · log¹ n) = O(n log n)

这正是归并排序的递归式。用递归树也能直观看出：共 log n 层，每层工作量 n，总和 n log n。

---

练习题 6（单选题）

题目： 递归求阶乘的空间复杂度是？（）

A. O(1)
B. O(n)
C. O(log n)
D. O(n²)

🔑 点击查看答案与解析

答案： B

解析：

递归的空间复杂度主要取决于递归深度（调用栈的深度）。

阶乘递归 fact(n) 的调用链：

fact(n) → fact(n-1) → fact(n-2) → ... → fact(1)

递归深度为 n，每层需要一个栈帧，所以空间复杂度是 O(n)。

选 B。

⚠️ 易错点：不要只看声明了几个变量就以为空间是 O(1)，递归的栈空间也是空间！

---

练习题 7（单选题）

题目： 如果某题的数据范围是 n ≤ 10⁵（10万），下面哪种复杂度的算法最可能通过？（）

A. O(n²)
B. O(n log n)
C. O(2ⁿ)
D. O(n!)

🔑 点击查看答案与解析

答案： B

解析：

估算各复杂度在 n=10⁵ 时的操作数：

A. O(n²) = 10¹⁰ = 100 亿次 → 太慢了，肯定超时
B. O(n log n) ≈ 10⁵ × 17 ≈ 170 万次 → ✅ 没问题
C. O(2ⁿ) → 天文数字，想都不要想
D. O(n!) → 更不用说了

经验规则（1秒大约能跑 10⁷ ~ 10⁸ 次操作）：

n ≤ 20 → O(2ⁿ) 可以
n ≤ 1000 → O(n²) 可以
n ≤ 10⁵ → O(n log n) 可以
n ≤ 10⁷ → O(n) 可以
n ≤ 10⁹ → O(log n) 可以

选 B。

💡 实战技巧：考试时看到 n 的范围，先反推应该用什么复杂度的算法，再想对应的算法是什么。

---

练习题 8（判断题）

题目： 以下复杂度从小到大排列是否正确：O(1) < O(log n) < O(n) < O(n²) < O(n log n) < O(2ⁿ)（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析：

正确的从小到大顺序是：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

题目中把 O(n²) 放在了 O(n log n) 前面，是错误的。

n log n 比 n² 小得多！比如 n=1000 时：

n log n ≈ 1000 × 10 = 10,000
n² = 1,000,000

差了 100 倍！

🔥 必背口诀：常对幂指阶（常数、对数、多项式、指数、阶乘）。多项式里面还有：n < n log n < n² < n³。

---

练习题 9（程序阅读题）

题目： 阅读以下代码，分析其时间复杂度。

cpp

int fun(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j *= 2) {
            count++;
        }
    }
    return count;
}

（1）这段代码的时间复杂度是？
A. O(n)　　B. O(n²)　　C. O(n log n)　　D. O(log n)

（2）当 n = 1024 时，count 的值大约是多少？
A. 1024　　B. 10240　　C. 524288　　D. 1048576

🔑 点击查看答案与解析

答案： （1）C　（2）B

解析：

（1）时间复杂度分析：

外层循环 i 从 0 到 n-1，共执行 n 次
内层循环 j 从 1 开始，每次乘 2，直到 j >= n 停止。即 j 取值为 1, 2, 4, 8, ..., 共 log₂n 次
总执行次数 = n × log₂n → O(n log n)

选 C。

（2）n = 1024 时 count 的值：

外层 1024 次
内层：log₂1024 = 10 次（2¹⁰ = 1024）
count ≈ 1024 × 10 = 10240

选 B。

💡 经典组合：外层线性 + 内层折半/倍增 = O(n log n)。归并排序、快速排序（平均）都是这个复杂度量级。

练习题 10（编程题）

题目： 题目描述：验证"1 秒约执行 10⁸ 次操作"的经验法则。给定一个整数 n，编写程序执行 n 次空循环（只做计数），输出执行的次数。

（本题用于理解数据规模与运行时间的关系，实际考试中会以选择题形式考查"给定 n 的范围，哪种复杂度能通过"。）

思考题：

如果 n = 10⁷，程序大约运行多久？
如果 n = 10⁹，会发生什么？

🔑 点击查看答案与解析

参考答案：

cpp

#include <iostream>
#include <ctime>
using namespace std;

int main() {
    long long n;
    cin >> n;
    
    clock_t start = clock();  // 记录开始时间
    
    long long count = 0;
    for (long long i = 0; i < n; i++) {
        count++;  // 简单操作：计数
    }
    
    clock_t end = clock();    // 记录结束时间
    double duration = (double)(end - start) / CLOCKS_PER_SEC;
    
    cout << "执行次数：" << count << endl;
    cout << "耗时：" << duration << " 秒" << endl;
    cout << "每秒操作数约：" << (long long)(n / duration) << endl;
    
    return 0;
}

解析与思考题答案：

这是一道"体验型"编程题，目的是让你直观感受不同复杂度在实际运行中的差异：

n = 10⁷（1000万）：约 0.1 秒左右，很快完成
n = 10⁸（1亿）：约 1 秒，这就是经验法则的来源
n = 10⁹（10亿）：约 10 秒，严重超时

复杂度与数据规模对照表（C++，1秒）：

复杂度	安全上限	典型算法
O(n)	~ 10⁷ ~ 10⁸	线性扫描、计数排序
O(n log n)	~ 10⁶ ~ 2×10⁶	归并排序、快速排序
O(n²)	~ 5000 ~ 10⁴	冒泡排序、二维DP
O(n³)	~ 200 ~ 300	Floyd最短路、三维DP
O(2ⁿ)	n ≤ 20 ~ 25	子集枚举、状压DP

🔥 实战技巧：拿到题先看 n 的范围，反推算法复杂度，再想对应的算法是什么。这是竞赛选手的"条件反射"。

十三、📊 考点总结表

考点	重要程度	出题形式	易错点
大O表示法定义与规则	⭐⭐⭐	选择、判断	忽略常数和低阶项的规则理解不清
循环复杂度分析	⭐⭐⭐	选择、程序阅读	内层循环次数不仔细数，想当然按层数判断
对数复杂度来源	⭐⭐⭐	选择	折半/倍增导致O(log n)的场景识别
递归复杂度（递归树+主定理）	⭐⭐	选择、判断	主定理三种情况混淆；递归树层数算错
快速排序三种情况	⭐⭐⭐	选择、判断	最坏情况O(n²)的触发条件记不清
空间复杂度（含递归栈）	⭐⭐⭐	选择、判断	忽略递归栈空间；原地算法概念不清
数据范围反推复杂度	⭐⭐⭐	选择	1秒操作数量级记忆不准；不留安全余量
时空权衡思想	⭐⭐	选择、判断	记忆化/前缀和/哈希表的空间代价理解
常见算法复杂度对比	⭐⭐⭐	选择、判断	排序算法的时间/空间/稳定性张冠李戴
复杂度增长排序	⭐⭐⭐	选择、判断	O(√n)、O(n log n)等中间量级位置记错

⭐ 必背速记卡

┌──────────────────────────────────────────────────────────────────┐
│                   ⭐ GESP 五级复杂度必背要点                      │
├──────────────────────────────────────────────────────────────────┤
│                                                                  │
│  1. 增长率排序：                                                  │
│     O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³)         │
│             < O(2ⁿ) < O(n!)                                      │
│                                                                  │
│  2. 循环变量倍增/折半 → O(log n)                                 │
│  3. k 层嵌套循环，每层跟 n 相关 → O(nᵏ)                          │
│  4. 归并排序：始终 O(n log n)，空间 O(n)，稳定                    │
│  5. 快速排序：平均 O(n log n)，最坏 O(n²)，不稳定，原地           │
│  6. 冒泡/选择/插入：O(n²)，其中冒泡/插入最好情况 O(n)            │
│  7. 试除法判素数：O(√n)                                          │
│  8. 朴素斐波那契：O(2ⁿ)；记忆化/递推：O(n)                       │
│  9. 主定理 T(n)=aT(n/b)+f(n)：                                   │
│     - f 更轻 → O(n^{log_b a})                                    │
│     - 同阶   → O(n^{crit} log n)                                 │
│     - f 更重 → O(f(n))                                           │
│ 10. n ≤ 20 可 O(2ⁿ)；n ≤ 1e5 须 O(n log n)；n ≤ 1e9 须 O(log n)│
│ 11. 辅助空间 O(1) = in-place；递归深度 = 栈空间                  │
│ 12. 时空权衡：记忆化、前缀和、哈希表——用空间换时间              │
│                                                                  │
└──────────────────────────────────────────────────────────────────┘

第9章 算法复杂度分析 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、为什么需要复杂度分析？🤔 ​

二、大 O 表示法基础 ​

2.1 定义 ​

2.2 三条基本法则 ​

2.3 常见复杂度等级（⭐ 必背！） ​

2.4 增长趋势示意（ASCII 图） ​

三、多项式复杂度 📐 ​

3.1 定义 ​

3.2 嵌套循环分析（核心技巧） ​

四、对数复杂度 🌲 ​

4.1 O(log n) 从哪里来？ ​

4.2 其他 O(log n) 场景 ​

4.3 O(n log n)——分治的产物 ​

五、指数复杂度 💥 ​

5.1 O(2ⁿ) 的典型来源：递归枚举子集 ​

5.2 朴素斐波那契：经典的 O(2ⁿ) 反例 ​

5.3 为什么指数复杂度"不可接受"？ ​

六、空间复杂度 📦 ​

6.1 定义 ​

6.2 常见例子 ​

6.3 递归栈空间 ​

6.4 In-place（原地）算法 ​

七、递归算法复杂度分析 🔁 ​

7.1 方法一：递归树法 ​

7.2 方法二：主定理（Master Theorem） ​

7.3 主定理常见例子 ​

7.4 斐波那契：O(2ⁿ) → O(n) 的飞跃 ​

八、最好 / 最坏 / 平均情况 ​

8.1 快速排序回顾 ​

8.2 三种情况 ​

九、根据数据范围反推复杂度（⚡ 实战核心技能） ​

9.1 经验表（以"1 秒 ≈ 10⁸ 次操作"估算） ​

9.2 记忆口诀 ​

9.3 实战判断流程 ​

十、时空权衡 🔄 ​

10.1 记忆化（Memoization） ​

10.2 预处理 / 前缀和 ​

10.3 哈希表：O(1) 查找的代价 ​

10.4 常见时空权衡策略 ​

十一、看代码判复杂度——实战技巧 🧐 ​

示例分析 ​

十二、📝 实战练习 ​

练习题 1（程序阅读题） ​

练习题 4（单选题） ​

练习题 6（单选题） ​

练习题 7（单选题） ​

练习题 8（判断题） ​

练习题 9（程序阅读题） ​

练习题 10（编程题） ​

十三、📊 考点总结表 ​

⭐ 必背速记卡 ​

第9章算法复杂度分析

🎯 本章学习目标

🗺️ 本章知识图谱

一、为什么需要复杂度分析？🤔

二、大 O 表示法基础

2.1 定义

2.2 三条基本法则

2.3 常见复杂度等级（⭐ 必背！）

2.4 增长趋势示意（ASCII 图）

三、多项式复杂度 📐

3.1 定义

3.2 嵌套循环分析（核心技巧）

四、对数复杂度 🌲

4.1 O(log n) 从哪里来？

4.2 其他 O(log n) 场景

4.3 O(n log n)——分治的产物

五、指数复杂度 💥

5.1 O(2ⁿ) 的典型来源：递归枚举子集

5.2 朴素斐波那契：经典的 O(2ⁿ) 反例

5.3 为什么指数复杂度"不可接受"？

六、空间复杂度 📦

6.1 定义

6.2 常见例子

6.3 递归栈空间

6.4 In-place（原地）算法

七、递归算法复杂度分析 🔁

7.1 方法一：递归树法

7.2 方法二：主定理（Master Theorem）

7.3 主定理常见例子

7.4 斐波那契：O(2ⁿ) → O(n) 的飞跃

八、最好 / 最坏 / 平均情况

8.1 快速排序回顾

8.2 三种情况

九、根据数据范围反推复杂度（⚡ 实战核心技能）

9.1 经验表（以"1 秒 ≈ 10⁸ 次操作"估算）

9.2 记忆口诀

9.3 实战判断流程

十、时空权衡 🔄

10.1 记忆化（Memoization）

10.2 预处理 / 前缀和

10.3 哈希表：O(1) 查找的代价

10.4 常见时空权衡策略

十一、看代码判复杂度——实战技巧 🧐

示例分析

十二、📝 实战练习

练习题 1（程序阅读题）

练习题 4（单选题）

练习题 6（单选题）

练习题 7（单选题）

练习题 8（判断题）

练习题 9（程序阅读题）

练习题 10（编程题）

十三、📊 考点总结表

⭐ 必背速记卡