【GESP】C++八级考试大纲知识点梳理 (7) 算法的时间和空间效率分析

发表于 2026/02/08

作者 OneCoder

次浏览 25 分钟阅读

GESP C++ 八级考试大纲知识点梳理系列文章：
计数原理：加法与乘法
排列与组合
杨辉三角与组合数
倍增法
代数与平面几何
图论算法：最小生成树与最短路
算法的时间和空间效率分析

作为一名优秀的 C++ 程序员，仅仅会写代码让程序跑起来是不够的。如果你的程序在处理大量数据时慢如蜗牛（TLE），或者直接内存溢出（MLE），那么这依然是一个不及格的程序。

算法复杂度分析在 GESP 考纲中反复出现，从四级到八级，要求逐级递进。到了八级，我们需要掌握的是“较为复杂算法”的分析能力。

考纲要求： (7) 算法的时间和空间效率分析。能够掌握 较为复杂算法 的时间和空间复杂度分析方法，能够分析各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及 动态规划算法 等）的时间和空间复杂度。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

一、考纲要求纵览与重点

这其实已经是大纲中 第三次 明确提出对算法复杂度的要求了。我们先来回顾一下前序等级的要求，以便明确八级的 “进阶” 到底体现在哪里。

1.1 前序等级要求回顾

四级考纲 (9)：简单算法复杂度的估算，含多项式、指数复杂度。
重点：初步认识 $O(N)$、$O(N^2)$ 与 $O(2^N)$ 的巨大差异。
- 【GESP】C++四级考试大纲知识点梳理 (9) 简单算法复杂度的估算
五级考纲 (5)：掌握算法复杂度估算方法（含多项式、对数）。
重点：引入了 $O(\log N)$ 和 $O(N \log N)$，主要结合 二分查找 和 高效排序（快排、归并）。
- 【GESP】C++五级考试大纲知识点梳理 (5) 算法复杂度估算

1.2 八级分析重点

对比八级考纲要求可见，八级的核心在 “复杂算法” 和 “空间”：

对象更复杂：不再是简单的循环嵌套，而是涉及 递归、图论、DP 等非线性结构的分析。
维度更全面：明确强调了 空间复杂度 的分析（以往容易忽视，但搜索和 DP 中极易 MLE）。
方法更深入：需要掌握递归树、状态转移等更深层的分析逻辑。

二、基本概念快速复习

既然已学过四五级，这里我们只做快速回顾。

2.1 大 O 符号与运算

$O(f(N))$：描述最坏情况下的渐进上界。
忽略原则：忽略常数系数（$2N \to N$）、忽略低阶项（$N^2+N \to N^2$）。

2.2 数据规模的“1秒定律”

在 C++ 竞赛中（通常 1秒时限），一般认为计算机能执行 $10^7 \sim 10^8$ 次基本运算。

N 的规模	复杂度上限	对应算法
$\le 20$	$O(2^N), O(N!)$	搜索、状压 DP
$\le 100 \sim 500$	$O(N^3)$	Floyd、区间 DP
$\le 2000 \sim 5000$	$O(N^2)$	朴素 DP、最短路(稠密)
$\le 10^5 \sim 10^6$	$O(N \log N)$	排序、堆、二分、线段树
$\ge 10^7$	$O(N)$	线性筛、双指针

三、复杂算法的时间复杂度分析

这是八级的重头戏。我们针对考纲提到的几类算法分别解析。

3.1 树与图的遍历 (Graph/Tree Traversal)

在图论算法中，时间复杂度通常与 点数 $V$ (Vertices) 和 边数 $E$ (Edges) 有关。我们要看算法到底遍历了什么。

DFS / BFS 遍历

核心逻辑：无论用什么存图，算法的步骤都是：

访问点 $u$。
找到 $u$ 的所有邻居 $v$。
对 $v$ 进行递归 (DFS) 或入队 (BFS)。

邻接矩阵 (Adjacency Matrix)

什么是邻接矩阵？ 用一个二维数组 G[N][N] 存图。G[i][j] = 1 表示 $i$ 到 $j$ 有边。
为什么慢？ 为了找到点 $u$ 的邻居，不管它实际连了几条边，程序必须 扫描 $u$ 这一整行 (从 $0$ 到 $V-1$)，逐个检查 if (G[u][v] == 1)。

代码体现：

  
// 访问点 u，试图找它的邻居 v
for (int v = 0; v < V; v++) { // 必须循环 V 次！
    if (G[u][v] != INF) { ... }
}

复杂度推导：每个点都要做一次 $O(V)$ 的扫描。总复杂度 = $V \times O(V) = $ $O(V^2)$。

邻接表 (Adjacency List)

什么是邻接表？ 用 vector<int> adj[N] 存图。adj[u] 里只存 $u$ 实际相连的邻居。
为什么快？ 找 $u$ 的邻居时，直接遍历 adj[u] 即可，不需要扫描不存在的边。

代码体现：

  
// 访问点 u，试图找它的邻居 v
for (int v : adj[u]) { // 只循环实际边数次
  ...
}

复杂度推导：所有点的 adj[u] 大小之和等于总边数 (无向图 $2E$，有向图 $E$)。总复杂度 = $V$ (访问所有点) + $E$ (扫描所有边) = $O(V + E)$。

推导结论：稀疏图 ($E \ll V^2$) 邻接表完胜；稠密图 ($E \approx V^2$) 两者相当。

最短路算法：Dijkstra 的两种形态

Dijkstra 算法是解决单源最短路径的经典算法，它的效率取决于 如何找到当前距离最小的那个点。

朴素 Dijkstra ($O(V^2)$)

实现方式：
- 使用一个数组 dist[N] 记录起点到各点的最短距离（初始化为无穷大，起点为 0）。
- 使用一个数组 visited[N] 记录该点的最短路是否已经确定。
- 算法核心是一个 $V$ 次的循环：每次在所有 未标记 (!visited) 的点中，扫描 dist[] 数组，找到值最小的那个点 $u$，标记它，并用它去更新邻居。
复杂度分析：
- 找最小点：$O(V)$，共需找 $V$ 次 $\rightarrow O(V^2)$。
- 更新邻居：每条边会被松弛一次 $\rightarrow O(E)$。
- 总复杂度：$O(V^2 + E) = O(V^2)$。
- 适用场景：稠密图 ($E \approx V^2$)。例如 $V=1000, E=10^6$，此时 $V^2$ 比 $E \log V$ 更快且常数小。

堆优化 Dijkstra ($O(E \log V)$)

与朴素法的核心区别：
- 朴素法：为了找到那个“当前距离最小的点”，采取了最笨的办法——全班点名（遍历数组），耗时 $O(V)$。
- 堆优化：利用数据结构维护秩序。所有候选点都在堆里排好队，队首就是最小的。我们不需要“找”，拿出来就是最小的。
实现细节与代价：
- 入队 (Push)：每当我们发现一条更短的路（松弛成功），就把新的 {距离, 点} 扔进堆里。这一步需要维持堆序，耗时 $O(\log V)$。
- 出队 (Pop)：每次取出堆顶元素。耗时 $O(\log V)$。
- 懒惰删除：因为 C++ priority_queue 无法直接修改堆中间的元素，我们允许堆里存在同一个点的多个“旧数据”。当我们从堆顶取出一个点时，如果发现它的距离比 dist[] 记录的实际最短距离大，说明它是“过期的”，直接扔掉即可。
总账计算：
- 每条边最多引起一次入队操作（松弛），共 $E$ 次。
- 总复杂度：$E \times O(\log V) = O(E \log V)$。
- 对比：在 稀疏图（如 $V=10^5, E=10^5$）中，$E \log V \approx 1.7 \times 10^6$，而 $V^2 = 10^{10}$。效率提升了近万倍！

3.2 搜索算法 (Search)

搜索算法（DFS/BFS/回溯）的复杂度通常是指数级的。估算核心模型是 分支系数 $b$ (Branching Factor) 与 搜索深度 $d$ (Depth)。

\[\text{总状态数} \approx O(b^d)\]

全排列 ($N!$)
- 第一层有 $N$ 个分支，第二层 $N-1$ 个… 第 $N$ 层 1 个。
- 总节点数：$N \times (N-1) \times \dots \times 1 = N!$。
子集生成 / 0-1 背包暴力 ($2^N$)
- 每个物品只有 2 种选择（选或不选）。分支系数 $b=2$，深度 $d=N$。
- 总节点数：$2^N$。
斐波那契数列递归
- fib(n) = fib(n-1) + fib(n-2)。
- 每个节点分裂为 2 个（近似），深度为 $N$。
- 复杂度：$O(2^N)$。

3.3 分治与递归 (Divide and Conquer)

分析分治算法（如归并排序、快速排序）的最佳方法是 递归树法 (Recursion Tree Method)。

核心公式： $\text{总工作量} = \sum (\text{每一层的节点数} \times \text{每个节点的工作量})$

归并排序 (Merge Sort)

核心思想：

分 (Divide)：把数组拦腰切断，分成左右两半。递归地去处理这两半，直到每个部分只剩 1 个元素（天然有序）。
治 (Conquer/Merge)：将两个已经有序的子数组，像洗扑克牌一样合并成一个大的有序数组。合并操作需要遍历两个子数组，复杂度与长度成正比。

复杂度推导：

第 0 层：1 个问题，规模 $N$。合并耗时 $O(N)$。
第 1 层：2 个问题，规模 $N/2$。合并耗时 $2 \times (N/2) = O(N)$。
第 2 层：4 个问题，规模 $N/4$。合并耗时 $4 \times (N/4) = O(N)$。
…
层数（树高）：每次除以 2，直到规模为 1。深度 $d = \log_2 N$。
总复杂度：$\text{层数} \times \text{每层工作量} = \log N \times N = O(N \log N)$。

快速排序 (Quick Sort)

核心思想：

选基准 (Pivot)：随便找个数（比如中间那个）作为基准。
分区 (Partition)：把比基准小的扔左边，比基准大的扔右边。这一步需要遍历当前区间，复杂度 $O(N)$。
递归：对左右两个分区重复上述过程。

复杂度推导 (平均情况)：

第 0 层：1 个问题，规模 $N$。分区耗时 $O(N)$。
第 1 层：2 个问题，规模 $N/2$。分区耗时 $2 \times (N/2) = O(N)$。
第 2 层：4 个问题，规模 $N/4$。分区耗时 $4 \times (N/4) = O(N)$。
…
总复杂度：同样是 $O(N \log N)$。
特例（最坏情况）：如果每次选的基准都是最值（比如有序数组选第一个数做基准），每次只分出来 0 个和 $N-1$ 个，树高退化为 $N$，总复杂度退化为 $O(N^2)$。这也是为什么快排通常要随机选基准。

3.4 动态规划 (Dynamic Programming)

DP 的复杂度分析其实最简单，想象你在 填一张表格。

核心公式解析

DP 的复杂度分析其实最简单，想象你在 填一张表格。不管是几维的表格，道理都一样：

\[\text{时间复杂度} = \text{表格总格子数 (状态总数)} \times \text{填好一个格子需要的操作次数 (状态转移代价)}\]

我们套用这个公式来分析几个经典模型：

1. 最长公共子序列 (LCS)

问题简介：给定两个字符串（如 “ABCDE” 和 “ACE”），求它们最长的公共子序列的长度（这里是 “ACE”，长度 3）。注意子序列可以不连续，但顺序不能乱。

核心策略：

如果 A[i] == B[j]，说明这个字符可以作为公共子序列的一部分，长度加 1。
如果 A[i] != B[j]，说明这两个字符不能同时选，那就在“A 缩短一点”或者“B 缩短一点”的情况里挑个好的。

复杂度分析：

Step 1: 数格子 (状态总数)
- 定义 dp[i][j] 为 A 串前 $i$ 个和 B 串前 $j$ 个的 LCS。
- $i$ 的范围是 $0 \sim N$，$j$ 的范围是 $0 \sim M$。
- 表格大小 = $N \times M$。
Step 2: 算单次代价 (转移代价)
- 求 dp[i][j] 时，要么继承 dp[i-1][j]，要么继承 dp[i][j-1]，要么是 dp[i-1][j-1] + 1。
- 这只是 3 次常数级别的比较和加法。
- 单次代价 = $O(1)$。
结论：总复杂度 = $NM \times 1 =$ $O(NM)$。

2. 最长上升子序列 (LIS) - 朴素版

问题简介：给定一个序列（如 [10, 9, 2, 5, 3, 7]），求它的最长上升子序列的长度（这里是 [2, 3, 7]，长度 3）。

核心策略：

对于每个数字 a[i]，我们想知道：如果以它结尾，能组成多长的上升子序列？
答案就是：找到所有比 a[i] 小的前面的数 a[j]，取它们对应的 LIS 长度的最大值，再加上 1（即 a[i] 本身）。

复杂度分析：

Step 1: 数格子 (状态总数)
- 定义 dp[i] 为以第 $i$ 个数结尾的 LIS 长度。
- $i$ 的范围是 $1 \sim N$。
- 表格大小 = $N$。
Step 2: 算单次代价 (转移代价)
- 为了求 dp[i]，我们需要回头看 $1 \sim i-1$ 的所有位置 $j$。
- 如果 a[i] > a[j]，尝试更新 dp[i] = max(dp[i], dp[j] + 1)。
- 这需要一个循环，平均遍历次数约为 $N/2$。
- 单次代价 = $O(N)$。
结论：总复杂度 = $N \times N =$ $O(N^2)$。

3. Floyd 全源最短路算法

问题简介：给定一个带权有向图（允许负权边，但无负权环），求任意两点之间的最短路径。

核心策略：

我们定义 dp[k][i][j] 为：只允许经过编号在 $1 \sim k$ 之间的点作为中转站，从点 $i$ 到点 $j$ 的最短路径长度。
状态转移时，我们考虑第 $k$ 个点：
- 不经过 $k$：最短路就是 dp[k-1][i][j]。
- 经过 $k$：最短路就是 dp[k-1][i][k] + dp[k-1][k][j]。
取两者最小值即可。

复杂度分析：

Step 1: 数格子 (状态总数)
- 原始状态定义是 dp[k][i][j] (只允许经过前 $k$ 个点，从 $i$ 到 $j$ 的最短路)。
- $k, i, j$ 的范围都是 $1 \sim N$。
- 表格大小 = $N \times N \times N = $ $N^3$。
Step 2: 算单次代价 (转移代价)
- dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])。
- 这就是一次简单的比较和加法。
- 单次代价 = $O(1)$。
结论：总复杂度 = $N^3 \times 1 = $ $O(N^3)$。

四、空间复杂度分析 (Space Complexity)

八级考纲中特别强调了空间。在高级算法中，MLE (Memory Limit Exceeded) 是非常容易出现的错误。

4.1 静态空间 (数据结构)

这部分比较显性，主要看开了多大的数组或容器。

int a[N]：$O(N)$。
int dp[N][N]：$O(N^2)$。
vector<int> adj[N]：$O(V+E)$。
- $V$ 的含义：你需要开一个长度为 $N$ 的数组来存这些 vector 的“头”，这占用了 $O(V)$ 的空间。
- $E$ 的含义：所有的 vector 里存的元素总数。这占用了 $O(E)$ 的空间。

警惕：$10^8$ 个 int 大约占用 381 MB。 GESP 或 CSP 常见的内存限制是 128MB 或 256MB（有的题甚至 512MB）。
128MB 安全界限：int 数组大小不超过 $3 \times 10^7$。
256MB 安全界限：int 数组大小不超过 $6 \times 10^7$。
如果你需要 int dp[10000][10000]，那就是 $10^8$ 个 int，必 MLE。

4.2 动态空间 (递归栈与队列)

这部分是隐性的，也是初学者容易“爆栈”的原因。

DFS 递归栈：
- 空间复杂度取决于 递归的最大深度。
- 在树中，最坏情况（退化成链）深度为 $N$，空间 $O(N)$。
- 平衡树或分治算法中，深度通常为 $\log N$，空间 $O(\log N)$。
- 系统栈限制：Windows 下通常较小（几MB），Linux/评测机通常较大（与堆内存共享或即使限制也有8-10MB）。深度达到 $10^5 \sim 10^6$ 级时极易 Stack Overflow。
BFS 队列：
- 空间复杂度取决于 队列中同时存在的最大元素个数（即图的最大宽度）。
- 最坏情况下（如星型图中心点扩展），可能达到 $O(V)$。
- BFS 虽然不会爆栈，但会消耗大量堆内存。

4.3 空间优化技巧

滚动数组：DP 中，如果 dp[i] 只依赖于 dp[i-1]，可以将 $O(N^2)$ 空间降为 $O(N)$ 甚至 $O(1)$。
邻接表代替邻接矩阵：将 $O(V^2)$ 降为 $O(V+E)$。
迭代代替递归：防止爆栈，虽然空间复杂度理论不变（手写栈），但堆空间通常比系统栈空间大得多。

五、总结与实战建议

算法类型	关键分析点	时间复杂度参考	空间复杂度参考
二分/分治	每次规模减半	$O(\log N)$ / $O(N \log N)$	$O(1)$ / $O(\log N)$
排序	快排/归并/堆排	$O(N \log N)$	$O(\log N)$ / $O(N)$
图遍历 (DFS/BFS)	点数 V，边数 E	$O(V+E)$ (邻接表)	$O(V)$
最短路 (Dijkstra)	堆优化	$O(E \log V)$	$O(V+E)$
最短路 (Floyd)	三重循环	$O(V^3)$	$O(V^2)$
树的遍历	节点数 N	$O(N)$	$O(N)$ 或 $O(\log N)$
动态规划	状态数 $\times$ 转移	视状态而定 ($N^2, N^3…$)	视状态而定 (可滚动优化)
全排列	阶乘	$O(N!)$	$O(N)$

备考建议：

看数据范围猜算法：这是做题的第一直觉。看到 $N=100$，敢写 Floyd ($N^3$)；看到 $N=10^5$，只能想 $O(N \log N)$ 或 $O(N)$。
重视空间计算：写二维数组前，先按计算器算一下是否超 128MB。
警惕递归深度：DFS 深度过深时，考虑是否需要改写或扩栈（如果在允许环境下）。

通过八级的考核，你应当不仅是一个代码的“翻译工”，更是一个懂得计算代价、懂得权衡资源的“架构师”。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 八级

GESP C++ 考试大纲复杂度分析算法

本文由作者按照 CC BY-NC-SA 4.0 进行授权

一、考纲要求纵览与重点

1.1 前序等级要求回顾

1.2 八级分析重点

二、基本概念快速复习

2.1 大 O 符号与运算

2.2 数据规模的“1秒定律”

三、复杂算法的时间复杂度分析

3.1 树与图的遍历 (Graph/Tree Traversal)

DFS / BFS 遍历

邻接矩阵 (Adjacency Matrix)

邻接表 (Adjacency List)

最短路算法：Dijkstra 的两种形态

朴素 Dijkstra ($O(V^2)$)

堆优化 Dijkstra ($O(E \log V)$)

3.2 搜索算法 (Search)

3.3 分治与递归 (Divide and Conquer)

归并排序 (Merge Sort)

快速排序 (Quick Sort)

3.4 动态规划 (Dynamic Programming)

核心公式解析

1. 最长公共子序列 (LCS)

2. 最长上升子序列 (LIS) - 朴素版

3. Floyd 全源最短路算法

四、空间复杂度分析 (Space Complexity)

4.1 静态空间 (数据结构)

4.2 动态空间 (递归栈与队列)

4.3 空间优化技巧

五、总结与实战建议

热门标签