高级算法复习总览
2026高级算法复习核心总结
1. 算法复杂度与最优性
| 概念 | 含义 | 举例 |
|---|---|---|
| 最坏复杂度 | 算法在所有可能输入中所需的最大时间/空间 | 快排最坏 $O(n^2)$（每次选到最差 pivot） |
| 平均复杂度 | 算法在所有可能输入上的期望时间/空间 | 快排平均 $O(n\log n)$ |
| 最优性 | 某算法的复杂度达到该问题的下界，无法再改进 | 比较排序下界 $\Omega(n\log n)$，归并排序达到该下界 → 最优 |
2. 渐近符号定义与证明
| 符号 | 定义（存在正常数） | 直观含义 |
|---|---|---|
| $O(g(n))$ | $0 \le f(n) \le c\cdot g(n)$，对 $n \ge n_0$ | 上界（不超过） |
| $\Omega(g(n))$ | $0 \le c\cdot g(n) \le f(n)$，对 $n \ge n_0$ | 下界（至少） |
| $\Theta(g(n))$ | $c_1 g(n) \le f(n) \le c_2 g(n)$ | 紧界（同阶） |
| $o(g(n))$ | $f(n)/g(n) \to 0$ | 严格上界 |
| $\omega(g(n))$ | $f(n)/g(n) \to \infty$ | 严格下界 |
证明套路：找合适的常数 $c, n_0$，验证不等式对所有 $n \ge n_0$ 成立。
3. 递归关系求解：齐次线性递推
标准形式：$a_n = r_1 a_{n-1} + r_2 a_{n-2}$
解法步骤：
- 写出特征方程：$x^2 - r_1 x - r_2 = 0$
- 求特征根 $x_1, x_2$
- 通项形式：
- 若 $x_1 \ne x_2$：$a_n = A x_1^n + B x_2^n$
- 若 $x_1 = x_2 = x$：$a_n = (A + Bn)x^n$
- 由初始值 $a_0, a_1$ 解出 $A, B$
🔸 斐波那契举例：$F_n = F_{n-1} + F_{n-2}$，$F_0=0, F_1=1$
特征方程：$x^2 - x - 1 = 0$，得 $x_1 = \frac{1+\sqrt5}{2}$，$x_2 = \frac{1-\sqrt5}{2}$
通项：$F_n = \frac{1}{\sqrt5}\left[\left(\frac{1+\sqrt5}{2}\right)^n - \left(\frac{1-\sqrt5}{2}\right)^n\right]$
4. 主定理（Master Theorem）
形式：$T(n) = bT(n/c) + f(n)$，其中 $b \ge 1, c > 1$
令 $E = \log_c b$（即 $n^E = n^{\log_c b}$），比较 $f(n)$ 与 $n^E$：
| 情况 | 条件 | 结论 |
|---|---|---|
| 情况1 | $f(n) = O(n^{E - \varepsilon})$，$\varepsilon > 0$ | $T(n) = \Theta(n^E)$ |
| 情况2 | $f(n) = \Theta(n^E \log^k n)$，$k \ge 0$ | $T(n) = \Theta(n^E \log^{k+1} n)$ |
| 情况3 | $f(n) = \Omega(n^{E + \varepsilon})$，且满足正则条件 $b f(n/c) \le \delta f(n)$，$\delta < 1$ | $T(n) = \Theta(f(n))$ |
🔸 举例：
- $T(n) = 2T(n/2) + n$：$E=1$，$f(n)=n=\Theta(n^1)$ → 情况2，$T=\Theta(n\log n)$
- $T(n) = 2T(n/2) + n^2$：$E=1$，$f(n)=n^2=\Omega(n^{1+1})$ → 情况3，$T=\Theta(n^2)$
平滑函数：主定理要求 $f(n)$ 满足“平滑性”（即 $f(n)$ 随 $n$ 单调且变化不太剧烈），保证递归树各层求和可控制。
5. 堆（Heap）
| 概念 | 说明 |
|---|---|
| 定义 | 完全二叉树，满足堆序：大根堆（父 ≥ 子）或小根堆（父 ≤ 子） |
| 数组表示 | 根在 A[1]，节点 i 的左子 = 2i，右子 = 2i+1，父 = ⌊i/2⌋ |
| 核心操作 | MaxHeapify(A, i)：$O(\log n)$，将节点 i 下沉到正确位置 |
| 建堆 | 从 ⌊n/2⌋ 到 1 调用 MaxHeapify，$O(n)$ |
| 插入 | 放到末尾，上浮调整，$O(\log n)$ |
| 删除最大值 | 根与末尾交换，删除末尾，再 MaxHeapify 根，$O(\log n)$ |
6. 快排平均复杂度分析方法
快排平均复杂度满足递归式：
$$
A(n) = (n - 1) + \frac{2}{n}\sum_{i=1}^{n-1} A(i)
$$
其中 $(n-1)$ 为划分比较次数，$\frac{2}{n}\sum_{i=1}^{n-1}A(i)$ 表示 pivot 等概率选在各位置时，左右两子问题平均规模。
求解思路：
- 将 $n$ 换成 $n-1$ 写出另一式
- 两式相减消去求和
- 转化为差分方程求解
最终得 $A(n) = \Theta(n\log n)$。此方法可推广到其他随机分治算法。
7. 对抗策略（Adversary Argument）
核心思想：构造一个“对手”，根据算法当前已知信息动态调整输入，迫使算法做尽可能多的比较，从而得出问题下界。
| 经典问题 | 下界结论 | 对抗思路 |
|---|---|---|
| 同时求最大和最小 | 至少 $3n/2 - 2$ 次比较 | 每个元素维护状态（未比较/赢过/输过），对手每次让比较结果尽可能不提供新信息，需每个元素至少输一次、赢一次（除最大最小） |
| 求第二大元素 | 至少 $n + \lceil \log n \rceil - 2$ 次比较 | 先锦标赛找最大（$n-1$ 次），最大元素打败过的 $\lceil \log n \rceil$ 个元素中找最大（再 $\lceil \log n \rceil - 1$ 次） |
8. 线性时间选择算法（BFPRT / Median of Medians）
目标：在 $O(n)$ 时间内找到数组中第 k 小的元素。
算法步骤：
- 将数组分成每组 5 个元素
- 对每组排序，找出每组中位数
- 递归调用本算法，找出所有组中位数的中位数 $m$（作为 pivot）
- 用 $m$ 划分数组，得到左半部分长度 $L$
- 若 $k \le L$，递归左半部分；否则递归右半部分
复杂度：最坏 $O(n)$，因为 pivot 保证至少 $3n/10$ 元素在其两侧，递归规模可控。
9. 平摊分析（Amortized Analysis）
核心思想：求一系列操作的平均代价，而非单次操作的最坏代价。三种方法：
| 方法 | 思路 |
|---|---|
| 聚集法 | 直接求 n 次操作总代价，除以 n |
| 会计法 | 每次操作多存“信用币”，用于支付后续昂贵操作 |
| 势能法 | 定义势函数 $\Phi$，平摊代价 = 实际代价 + $\Delta\Phi$ |
🔸 MultiPop Stack：
- Push：代价 1，Pop：代价 1，MultiPop(k)：弹出最多 k 个元素
- 用势能法：$\Phi$ = 栈中元素数
- Push 平摊代价 = $1 + 1 = 2$，Pop/MultiPop 平摊代价 = $1 + (-1) = 0$
- 总体平摊 $O(1)$ 每次操作
🔸 DeleteLargerHalf：每次删除集合中较大的半数元素，用势能法可证平摊 $O(1)$。
🔸 栈模拟队列：用两个栈实现队列，每个元素入栈/出栈各一次，平摊 $O(1)$。
10. DFS / BFS 与图搜索问题
| 算法 | 核心思想 | 数据结构 | 时间复杂度 |
|---|---|---|---|
| BFS | 按层扩展，先访问距离近的 | 队列 | $O(V+E)$ |
| DFS | 一条路走到黑，回溯 | 栈（递归） | $O(V+E)$ |
| 经典问题 | 解决方法 |
|---|---|
| 拓扑排序 | DFS 后序 + 逆序（或 Kahn 算法，基于 BFS 入度为 0 的队列） |
| 任务调度 | 拓扑排序，按依赖顺序执行 |
| 关键路径 | 拓扑序上 DP：最早开始时间 = max(前驱最早 + 边权)，最迟开始时间 = min(后继最迟 - 边权) |
| 强连通分量（SCC） | Kosaraju：正图 DFS → 逆图按 finish time 递减 DFS；或 Tarjan（单次 DFS） |
11. 贪心法
核心思想：每一步做当前看起来最优的选择，不回溯，期望得到全局最优。
适用条件（需证明）：
- 最优子结构：全局最优包含子问题最优
- 贪心选择性质：局部最优选择不会影响全局最优解的存在
| 经典问题 | 贪心策略 | 证明思路 |
|---|---|---|
| 换硬币 | 每次用最大面额（货币系统需满足 canonical 性质） | 交换论证：若最优解中不用最大面额，可换成等值的大面额硬币不增加数量 |
| 单源最短路径（Dijkstra） | 每次选择距离源点最近的未确定顶点 | 剪枝证明：任何经过其他未确定顶点的路径都不短于当前选中的路径 |
12. 动态规划
核心思想：将大问题分解为重叠子问题，用表格记录子问题解，避免重复计算。
适用条件：最优子结构 + 重叠子问题。
DP 四步法：
- 定义子问题状态
- 写出状态转移方程（递归式）
- 确定初始条件/边界
- 确定计算顺序（通常自底向上）
| 经典问题 | 状态定义 | 递归式 |
|---|---|---|
| 最长公共子序列（LCS） | $dp[i][j]$ = $s1[1..i]$ 和 $s2[1..j]$ 的 LCS 长度 | 若 $s1[i]=s2[j]$：$dp[i][j]=dp[i-1][j-1]+1$；否则 $=\max(dp[i-1][j], dp[i][j-1])$ |
| 抽牌拿取最大值（区间 DP） | $dp[i][j]$ = 在区间 [i,j] 能拿到的最大分数 | $dp[i][j] = $$max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])$ （双方最优） |
| 回文分割 | $dp[i]$ = s[1..i] 的最少分割数 | $dp[i] = \min_{0 \le j < i, s[j+1..i] 回文} (dp[j] + 1)$ |
🔸 回文判断：$isPal[i][j] = (s[i]==s[j]) \land (j-i \le 1 \lor isPal[i+1][j-1])$