(7) 算法的时间和空间效率分析

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

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

一、考纲要求纵览与重点

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

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 八级分析重点

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

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

二、基本概念快速复习

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

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$ 次基本运算。

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

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

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

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

DFS / BFS 遍历

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

1. 访问点 $u$。
2. 找到 $u$ 的所有邻居 $v$。
3. 对 $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)。

• 全排列 ($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)。

核心公式：

归并排序 (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 的复杂度分析其实最简单，想象你在 填一张表格。不管是几维的表格，道理都一样：

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

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 空间优化技巧

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

五、总结与实战建议

备考建议：

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

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

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