(8) 算法优化技巧

在 GESP 八级考试中，最后一项考点是对 算法优化 的综合考察。这不仅仅是学会某个具体的算法，更是要求我们具备一种 “多想一步” 的思维能力：当暴力解法行不通时，如何通过数学、数据结构或算法策略来提升效率，把 $O(N^2)$ 优化到 $O(N \log N)$ 甚至 $O(N)$。

本文将从三个维度来拆解常见的优化技巧：数学优化、数据结构优化 和 算法策略优化。

一、数学优化 (Mathematical Optimization)

数学是算法的灵魂。很多看似复杂的循环，背后往往隐藏着简单的数学公式或性质。

1.1 公式代替循环 ($O(N) \to O(1)$)

这是考纲中直接提到的例子：求等差数列的和。

• 暴力做法：写一个 for 循环累加，时间复杂度 $O(N)$。
• 数学优化：利用高斯求和公式 $\text{Sum} = \frac{\text{(首项 + 末项)} \times \text{项数}}{2}$，时间复杂度 $O(1)$。

这类优化在 几何计算（如多边形面积）、排列组合（如 $C_n^m$ 公式计算）中非常常见。

1.2 前缀和与差分 ($O(N) \to O(1)$)

在 区间查询 和 区间修改 问题中，前缀和与差分是神器。

1.2.1 区间求和问题 (Range Sum Query)

问题描述：给定一个包含 $N$ 个元素的数组 $A$，有 $M$ 次询问，每次询问给定区间 $[L, R]$，求该区间内所有元素的和。

Level 1：暴力解法

• 对于每次询问，使用 for 循环从 $L$ 遍历到 $R$ 进行累加。
• 复杂度：单次询问 $O(N)$，总复杂度 $O(N \times M)$。当 $N, M$ 都在 $10^5$ 级别时，总计算量达到 $10^{10}$，必然 超时 (TLE)。

Level 2：前缀和优化 (Prefix Sum)

• 预处理：构造前缀和数组 $S$，其中 $S[i]$ 表示数组 $A$ 前 $i$ 个数的和，即 $S[i] = A[1] + A[2] + \dots + A[i]$。递推公式为 $S[i] = S[i-1] + A[i]$。
• 查询：区间 $[L, R]$ 的和可以表示为“前 $R$ 个数的和”减去“前 $L-1$ 个数的和”。
  • 公式：$\text{Sum}(L, R) = S[R] - S[L-1]$。
  • 复杂度：单次询问 $O(1)$。

1.2.2 区间修改问题 (Range Update)

问题描述：给定数组 $A$，有 $M$ 次操作，每次操作将区间 $[L, R]$ 内的所有数都加上 $v$。最后输出修改后的数组。

Level 1：暴力解法

• 对于每次操作，使用 for 循环把 $A[L] \sim A[R]$ 一个个加上 $v$。
• 复杂度：单次修改 $O(N)$，总复杂度 $O(N \times M)$，同样会 超时。

Level 2：差分数组优化 (Difference Array)

核心原理：

• 定义差分数组 $D[i] = A[i] - A[i-1]$（规定 $A[0]=0$）。
• 根据定义，$A[i]$ 其实就是 $D$ 数组的前缀和，即 $A[i] = D[1] + D[2] + \dots + D[i]$。

优化操作：

当我们需要将区间 $[L, R]$ 内的所有数加上 $v$ 时，不需要遍历修改，只需修改 $D$ 数组的两个点：

1. D[L] += v：
   • 因为 $A[L]$ 的计算包含 $D[L]$，所以 $A[L]$ 增加 $v$。
   • 同时，对于任何 $k > L$，$A[k]$ 的前缀和计算中也都包含 $D[L]$，所以从 $L$ 开始及其后面所有的数都会增加 $v$。
2. D[R+1] -= v：
   • 我们的目标是只修改到 $R$ 为止，不希望影响 $R+1$ 及其后面的数。
   • 在 $D[R+1]$ 处减去 $v$，刚好抵消掉 $D[L]$ 带来的 $+v$ 影响。
   • 这样，从 $R+1$ 往后，增加的 $v$ 和减少的 $v$ 互相抵消，数值保持不变。

如何应用（还原结果）：

• 第一步：初始化差分数组 $D$。
• 第二步：对于 $M$ 次修改操作，每次只执行 D[L] += v 和 D[R+1] -= v，单次耗时 $O(1)$。
• 第三步（很重要）：所有操作完成后，通过前缀和一次性还原出最终的 $A$ 数组：
  • A[i] = A[i-1] + D[i] （从 $1$ 到 $N$ 遍历一次）。
• 总复杂度：$O(M + N)$，远优于暴力的 $O(M \times N)$。

1.3 数论性质优化

• 最大公约数 (GCD)：
  • 暴力：从 $\min(a, b)$ 往下枚举，最坏 $O(N)$。
  • 辗转相除法 (Euclidean)：$gcd(a, b) = gcd(b, a \% b)$，复杂度 $O(\log N)$。
• 质数判定：
  • 暴力：试除 $2 \sim N-1$，复杂度 $O(N)$。
  • 优化：只需试除 $2 \sim \sqrt{N}$，复杂度 $O(\sqrt{N})$。

二、数据结构优化 (Data Structure Optimization)

选择合适的容器，能让代码事半功倍。

2.1 Map/Set 代替扫描 ($O(N) \to O(\log N)$)

• 场景：查找某个数是否存在，或者统计某个数出现的次数。
• 暴力：
  • 在 vector 或数组中遍历查找。
  • 单次查找 $O(N)$。
• 优化：
  • 使用 std::set (去重/查找) 或 std::map (统计/映射)。
  • 基于红黑树实现，单次查找/插入均为 $O(\log N)$。
  • 如果是哈希表 unordered_map，均摊甚至可以到 $O(1)$（但要注意哈希冲突和常数）。

2.2 优先队列代替排序 ($O(N \log N) \to O(N \log K)$)

• 场景：在 $N$ 个数中找出 前 $K$ 大 的数。
• 暴力：
  • 先 sort 整个数组，然后取前 $K$ 个。
  • 复杂度：$O(N \log N)$。
• 优化：
  • 核心机理：维护一个固定大小为 $K$ 的 小根堆 (min-heap)。
  • 为什么选小根堆？ 因为如果要找 前 $K$ 大，我们需要知道这 $K$ 个数里谁最小。如果新来的数比这个最小的大，说明新数有资格进前 $K$ 大，把原最小的踢出去即可。
• 操作步骤：
  1. 先让前 $K$ 个元素入堆。
  2. 从第 $K+1$ 个元素开始遍历数组，设当前元素为 x，堆顶元素为 min_val。
  3. 如果你比全班前 $K$ 名里最弱的那个人（堆顶）强，你就把他挤下去了（Pop Min, Push New）。
  4. 否则，说明你连前 $K$ 名的门槛都没摸到，也就没资格进入“精英榜”。
• 复杂度：遍历 $N$ 次，每次堆调整耗时 $O(\log K)$，总复杂度 $O(N \log K)$。当 $K \ll N$ 时优化明显。

三、算法策略优化 (Algorithmic Strategies)

当数学公式和数据结构都救不了你时，就需要改变算法本身的策略。

3.1 双指针法 (Two Pointers)

双指针通常用于将嵌套循环的 $O(N^2)$ 优化为 $O(N)$。

经典案例：2Sum 问题

• 问题：在有序数组中找两个数，使其和为 target。
• 暴力：两层循环枚举所有对，判断是否等于 target。$O(N^2)$。
• 双指针优化：左指针 $L=0$，右指针 $R=N-1$。
  • 若 A[L] + A[R] < target，说明和小了，$L++$。
  • 若 A[L] + A[R] > target，说明和大了，$R--$。
  • 因为 $L$ 和 $R$ 最多各走 $N$ 步，总复杂度 $O(N)$。

3.2 二分答案 (Binary Search on Answer)

二分不仅能查数，还能查 “答案”。

• 适用场景：答案具有 单调性。即：如果 $X$ 可行，那么比 $X$ 小的也都可行（或比 $X$ 大的都可行）。
• 策略：
  • 我们不再试图“直接计算”最优解。
  • 而是猜测一个答案 mid，然后写一个 check(mid) 函数判断这个答案是否合法。
  • 如果 check(mid) 为真，尝试更好的；否则尝试更保守的。
• 复杂度：时间复杂度从“无法直接求解”转化为 $O(\log(\text{答案范围}) \times \text{Check耗时})$。

3.3 预处理与“空间换时间”

• 场景：需要多次查询某些耗时的计算结果（如组合数、素数、阶乘）。
• 优化：
  • 不要每次询问都算一遍。
  • 在程序开始时，先算好存在数组里（打表/预处理）。
  • 询问时直接查表，复杂度 $O(1)$。

经典案例：最大子段和 (Maximum Subarray Sum)

这是一个教科书级的优化案例，体现了从“暴力”到“数学”再到“DP”的完整进化。

问题：给定数组 A，求一个连续子数组，使得其和最大。

• Level 1: 纯暴力 ($O(N^3)$)
  • 枚举起点 $i$，枚举终点 $j$，再用循环计算 $sum(i, j)$。
• Level 2: 前缀和优化 ($O(N^2)$)
  • 预处理前缀和 $S$。枚举起点 $i$，枚举终点 $j$，用 $S[j] - S[i-1]$ 算区间和。省去了一层循环。
• Level 3: 分治法 ($O(N \log N)$)
  • 策略：将数组一分为二，最大子段只可能出现在三种情况：
  1. 完全在左半边：递归求左半边的最大子段和。
  2. 完全在右半边：递归求右半边的最大子段和。
  3. 跨越中间：从中间向左扫描求最大后缀和，从中间向右扫描求最大前缀和，两者相加。
  • 合并：最终结果 max(左边最大, 右边最大, 跨越中间最大)。
• Level 4: 动态规划 / 贪心 ($O(N)$) - Kadane 算法
  • 策略：遍历数组，维护一个 current_sum。如果 current_sum 变成负数了，把它置为 0（因为负数只会拖累后面的和）。记录过程中的最大值。
  • 一趟遍历即可完成，极致的效率。

四、总结与实战建议

算法优化没有定式，但有迹可循。在考场上遇到难题（尤其是 TLE 时），请按以下顺序思考优化方向：

1. 数学公式？ 能不能 $O(1)$ 算出来？有没有重复计算的部分可以用前缀和？
2. 数据结构？ 是不是查找太慢了？能不能用 Map/Set？是不是最值找太慢了？能不能用堆？
3. 算法策略？ 能不能二分答案？能不能用双指针去掉一层循环？
4. 预处理？ 还能不能再多记点东西，让查询更快？

通过八级的学习，我们不仅仅是在学 Coding，更是在学 Problem Solving。希望大家在 GESP 考试中都能游刃有余，写出既“快”又“省”的满分代码！

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

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

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

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

GESP/CSP认证交流QQ群： 688906745

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