算法复杂度速查手册

本文是 OI Wiki - 复杂度简介的整合精简版，所有示例均使用 C++。

1. 核心概念

概念	说明
基本操作	加减乘除、变量访问、赋值等，每次算一步
时间复杂度	算法执行步骤数随输入规模 $n$ 增长的趋势
空间复杂度	算法占用内存随输入规模 $n$ 增长的趋势
最坏复杂度	所有可能输入中，用时最长的情况（竞赛中默认用这个）
平均复杂度	所有可能输入下用时的平均值

为什么关注"趋势"而非"精确值"？
现代 CPU 每秒处理数亿次操作。
$O(n^2)$ 的算法在 $n=10^5$ 时需要 $10^{10}$ 次操作，直接超时；
$O(n \log n)$ 只需 $\approx 1.7 \times 10^6$ 次，轻松通过。趋势比常数系数更重要。

2. 渐近符号（大 O 家族）

符号	类比	含义	何时用
$\Theta(g)$	$=$	上界且下界（紧确界）	精确描述增长趋势
$O(g)$	$\le$	渐近上界	描述最坏情况（最常用）
$\Omega(g)$	$\ge$	渐近下界	证明算法不可能更快
$o(g)$	$<$	严格渐近上界	数学分析（竞赛少用）
$\omega(g)$	$>$	严格渐近下界	数学分析（竞赛少用）

记忆口诀：含"等于"用大写，不含等于用小写；相等是 $\Theta$ ，小于是 $O$ ，大于是 $\Omega$ 。

常用性质

f₁(n) + f₂(n)  = O(max(f₁, f₂))     // 取大的那个
f₁(n) × f₂(n)  = O(f₁ × f₂)         // 嵌套相乘
log_a(n)        = O(log n)            // 对数底数无所谓，可省略
f(n) = Θ(g(n)) ⟺ f = O(g) 且 f = Ω(g)

3. 复杂度计算实例

3.1 嵌套循环 → 相乘

int n, m;
std::cin >> n >> m;

for (int i = 0; i < n; ++i) {       // n 次
    for (int j = 0; j < n; ++j) {   // n 次
        for (int k = 0; k < m; ++k) // m 次
            std::cout << "hello\n";
    }
}
// 复杂度：Θ(n²m)

规则：嵌套循环各层次数相乘。

3.2 图的 DFS / BFS → 点 + 边

// 对 n 个点、m 条边的图做 DFS
void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u])   // 每条边只走一次
        if (!visited[v]) dfs(v);
}
// 复杂度：Θ(n + m)

规则：每个节点和每条边各访问常数次 → $O(n+m)$ 。

3.3 常量循环 → O(1)

constexpr int N = 100000;  // N 是固定常量，与输入无关

for (int i = 0; i < N; ++i)
    std::cout << "hello\n";
// 复杂度：O(1)  —— N 不随输入变化，视为常数

关键：判断一个变量是否是"输入规模"。与输入无关的量都是常量，当 1 处理。

4. 主定理（Master Theorem）

用于快速求递归算法的复杂度。

适用形式： $T(n) = a \cdot T(n/b) + f(n)$ ，其中 $a \ge 1,\ b > 1$ 。

情况	条件	结论
情况 1	$f(n) = O(n^{\log_b a - \varepsilon})$ ， $\varepsilon > 0$	$T(n) = \Theta(n^{\log_b a})$
情况 2	$f(n) = \Omega(n^{\log_b a + \varepsilon})$ ，且满足正则条件	$T(n) = \Theta(f(n))$
情况 3	$f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ ， $k \ge 0$	$T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$

正则条件（情况 2 需满足）： $a \cdot f(n/b) \le c \cdot f(n)$ ，对某常数 $c < 1$ 且足够大的 $n$ 成立。

速查示例

递推式	$a$	$b$	$\log_b a$	适用情况	结论
$T(n) = 2T(n/2) + 1$	2	2	1	情况 1	$\Theta(n)$
$T(n) = T(n/2) + n$	1	2	0	情况 2	$\Theta(n)$
$T(n) = T(n/2) + \log n$	1	2	0	情况 3， $k=1$	$\Theta(\log^2 n)$
$T(n) = T(n/2) + 1$	1	2	0	情况 3， $k=0$	$\Theta(\log n)$

对应算法举例

// 归并排序：T(n) = 2T(n/2) + n  → Θ(n log n)  [情况 3, k=0]
void mergeSort(int* arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);     // T(n/2)
    mergeSort(arr, mid+1, r);   // T(n/2)
    merge(arr, l, mid, r);      // O(n)
}

// 二分查找：T(n) = T(n/2) + 1  → Θ(log n)  [情况 3, k=0]
int binarySearch(int* arr, int l, int r, int target) {
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearch(arr, mid+1, r, target);
    return binarySearch(arr, l, mid-1, target);
}

5. 常见复杂度对比

从快到慢排列（ $n = 10^6$ 时的量级参考）：

复杂度	名称	$n=10^6$ 时操作数	典型算法
$O(1)$	常数	1	哈希表查找
$O(\log n)$	对数	$\approx 20$	二分查找
$O(\sqrt{n})$	平方根	$\approx 1000$	分块、质因数分解
$O(n)$	线性	$10^6$	线性扫描、DFS/BFS
$O(n \log n)$	线性对数	$\approx 2 \times 10^7$	归并排序、堆排序
$O(n^2)$	平方	$10^{12}$ ❌	冒泡排序、朴素 DP
$O(2^n)$	指数	—	暴力枚举子集

竞赛经验： $10^8$ 次操作约耗时 1 秒。 $n \le 10^6$ 时， $O(n \log n)$ 通常安全； $n \le 10^4$ 时才能用 $O(n^2)$ 。

6. 快速判断方法

循环嵌套？  → 各层次数相乘
顺序执行？  → 取复杂度最大的那段
递归分治？  → 套主定理
图算法？    → 通常 O(n + m) 或 O(m log n)
常量次操作？→ O(1)

参考来源：OI Wiki - 复杂度简介（CC BY-SA 4.0）

算法复杂度速查手册

本文是 OI Wiki - 复杂度简介的整合精简版，所有示例均使用 C++。

1. 核心概念

概念	说明
基本操作	加减乘除、变量访问、赋值等，每次算一步
时间复杂度	算法执行步骤数随输入规模 $n$ 增长的趋势
空间复杂度	算法占用内存随输入规模 $n$ 增长的趋势
最坏复杂度	所有可能输入中，用时最长的情况（竞赛中默认用这个）
平均复杂度	所有可能输入下用时的平均值

为什么关注"趋势"而非"精确值"？
现代 CPU 每秒处理数亿次操作。
$O(n^2)$ 的算法在 $n=10^5$ 时需要 $10^{10}$ 次操作，直接超时；
$O(n \log n)$ 只需 $\approx 1.7 \times 10^6$ 次，轻松通过。趋势比常数系数更重要。

2. 渐近符号（大 O 家族）

符号	类比	含义	何时用
$\Theta(g)$	$=$	上界且下界（紧确界）	精确描述增长趋势
$O(g)$	$\le$	渐近上界	描述最坏情况（最常用）
$\Omega(g)$	$\ge$	渐近下界	证明算法不可能更快
$o(g)$	$<$	严格渐近上界	数学分析（竞赛少用）
$\omega(g)$	$>$	严格渐近下界	数学分析（竞赛少用）

记忆口诀：含"等于"用大写，不含等于用小写；相等是 $\Theta$ ，小于是 $O$ ，大于是 $\Omega$ 。

常用性质

f₁(n) + f₂(n)  = O(max(f₁, f₂))     // 取大的那个
f₁(n) × f₂(n)  = O(f₁ × f₂)         // 嵌套相乘
log_a(n)        = O(log n)            // 对数底数无所谓，可省略
f(n) = Θ(g(n)) ⟺ f = O(g) 且 f = Ω(g)

3. 复杂度计算实例

3.1 嵌套循环 → 相乘

int n, m;
std::cin >> n >> m;

for (int i = 0; i < n; ++i) {       // n 次
    for (int j = 0; j < n; ++j) {   // n 次
        for (int k = 0; k < m; ++k) // m 次
            std::cout << "hello\n";
    }
}
// 复杂度：Θ(n²m)

规则：嵌套循环各层次数相乘。

3.2 图的 DFS / BFS → 点 + 边

// 对 n 个点、m 条边的图做 DFS
void dfs(int u) {
    visited[u] = true;
    for (int v : graph[u])   // 每条边只走一次
        if (!visited[v]) dfs(v);
}
// 复杂度：Θ(n + m)

规则：每个节点和每条边各访问常数次 → $O(n+m)$ 。

3.3 常量循环 → O(1)

constexpr int N = 100000;  // N 是固定常量，与输入无关

for (int i = 0; i < N; ++i)
    std::cout << "hello\n";
// 复杂度：O(1)  —— N 不随输入变化，视为常数

关键：判断一个变量是否是"输入规模"。与输入无关的量都是常量，当 1 处理。

4. 主定理（Master Theorem）

用于快速求递归算法的复杂度。

适用形式： $T(n) = a \cdot T(n/b) + f(n)$ ，其中 $a \ge 1,\ b > 1$ 。

情况	条件	结论
情况 1	$f(n) = O(n^{\log_b a - \varepsilon})$ ， $\varepsilon > 0$	$T(n) = \Theta(n^{\log_b a})$
情况 2	$f(n) = \Omega(n^{\log_b a + \varepsilon})$ ，且满足正则条件	$T(n) = \Theta(f(n))$
情况 3	$f(n) = \Theta(n^{\log_b a} \cdot \log^k n)$ ， $k \ge 0$	$T(n) = \Theta(n^{\log_b a} \cdot \log^{k+1} n)$

正则条件（情况 2 需满足）： $a \cdot f(n/b) \le c \cdot f(n)$ ，对某常数 $c < 1$ 且足够大的 $n$ 成立。

速查示例

递推式	$a$	$b$	$\log_b a$	适用情况	结论
$T(n) = 2T(n/2) + 1$	2	2	1	情况 1	$\Theta(n)$
$T(n) = T(n/2) + n$	1	2	0	情况 2	$\Theta(n)$
$T(n) = T(n/2) + \log n$	1	2	0	情况 3， $k=1$	$\Theta(\log^2 n)$
$T(n) = T(n/2) + 1$	1	2	0	情况 3， $k=0$	$\Theta(\log n)$

对应算法举例

// 归并排序：T(n) = 2T(n/2) + n  → Θ(n log n)  [情况 3, k=0]
void mergeSort(int* arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);     // T(n/2)
    mergeSort(arr, mid+1, r);   // T(n/2)
    merge(arr, l, mid, r);      // O(n)
}

// 二分查找：T(n) = T(n/2) + 1  → Θ(log n)  [情况 3, k=0]
int binarySearch(int* arr, int l, int r, int target) {
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return binarySearch(arr, mid+1, r, target);
    return binarySearch(arr, l, mid-1, target);
}

5. 常见复杂度对比

从快到慢排列（ $n = 10^6$ 时的量级参考）：

复杂度	名称	$n=10^6$ 时操作数	典型算法
$O(1)$	常数	1	哈希表查找
$O(\log n)$	对数	$\approx 20$	二分查找
$O(\sqrt{n})$	平方根	$\approx 1000$	分块、质因数分解
$O(n)$	线性	$10^6$	线性扫描、DFS/BFS
$O(n \log n)$	线性对数	$\approx 2 \times 10^7$	归并排序、堆排序
$O(n^2)$	平方	$10^{12}$ ❌	冒泡排序、朴素 DP
$O(2^n)$	指数	—	暴力枚举子集

竞赛经验： $10^8$ 次操作约耗时 1 秒。 $n \le 10^6$ 时， $O(n \log n)$ 通常安全； $n \le 10^4$ 时才能用 $O(n^2)$ 。

6. 快速判断方法

循环嵌套？  → 各层次数相乘
顺序执行？  → 取复杂度最大的那段
递归分治？  → 套主定理
图算法？    → 通常 O(n + m) 或 O(m log n)
常量次操作？→ O(1)

参考来源：OI Wiki - 复杂度简介（CC BY-SA 4.0）

算法复杂度速查手册

1. 核心概念

2. 渐近符号（大 O 家族）

常用性质

3. 复杂度计算实例

3.1 嵌套循环 → 相乘

3.2 图的 DFS / BFS → 点 + 边

3.3 常量循环 → O(1)

4. 主定理（Master Theorem）

速查示例

对应算法举例

5. 常见复杂度对比

6. 快速判断方法

推荐阅读

头文件与IO加速完全指南

排序算法详解：从冒泡到快速排序

二分查找：从原理到竞赛应用

算法复杂度速查手册

1. 核心概念

2. 渐近符号（大 O 家族）

常用性质

3. 复杂度计算实例

3.1 嵌套循环 → 相乘

3.2 图的 DFS / BFS → 点 + 边

3.3 常量循环 → O(1)

4. 主定理（Master Theorem）

速查示例

对应算法举例

5. 常见复杂度对比

6. 快速判断方法

推荐阅读

头文件与IO加速完全指南

排序算法详解：从冒泡到快速排序

二分查找：从原理到竞赛应用