高级算法复习

发表于 2026-06-05 更新于 2026-06-29 分类于高级算法本文字数： 1.4k 阅读时长 ≈ 5 分钟

算法复杂度

最坏复杂度：算法在任何输入实例上运行时间的最坏情况，记为 $ T_{\text{worst}}(n) $。
- 举例：快速排序最坏情况 $ O(n^2) $（数组已有序且主元选择不当）。
平均复杂度：算法在所有可能输入实例上运行时间的期望，记为 $ T_{\text{avg}}(n) $。
- 举例：快速排序平均情况 $ O(n \log n) $。
最优复杂度：算法在“最优”输入实例上的最低运行时间。
- 举例：冒泡排序在已有序数组上为 $ O(n) $。

渐近记号定义与函数证明

定义：

$ O(g(n)) = { f(n) \mid \exists c>0, n_0>0 : 0 \leq f(n) \leq c g(n), \forall n \geq n_0 } $
$ \Omega(g(n)) = { f(n) \mid \exists c>0, n_0>0 : 0 \leq c g(n) \leq f(n), \forall n \geq n_0 } $
$ \Theta(g(n)) = O(g(n)) \cap \Omega(g(n)) $

函数证明示例：$ 3n^3 + 2n^2 + 10 \in \Theta(n^3) $

上界：$ 3n^3 + 2n^2 + 10 \leq 15n^3, \forall n \geq 1 \Rightarrow O(n^3) $
下界：$ 3n^3 + 2n^2 + 10 \geq 3n^3, \forall n \geq 0 \Rightarrow \Omega(n^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 $
通解：
$$
a_n = \begin{cases}
c_1 x_1^n + c_2 x_2^n & (x_1 \neq x_2) \
(c_1 + c_2 n) x_1^n & (x_1 = x_2)
\end{cases}
$$
代入初始条件求解 $ c_1, c_2 $

示例（斐波那契）：$ a_0=1, a_1=1, a_n = a_{n-1} + a_{n-2} $

特征方程：$ x^2 - x - 1 = 0 $
根：$ x_1 = \frac{1 - \sqrt{5}}{2}, x_2 = \frac{1 + \sqrt{5}}{2} $
通项公式：$ a_n = \frac{5 - \sqrt{5}}{10} x_1^n + \frac{5 + \sqrt{5}}{10} x_2^n $

主定理应用

一般式：$ T(n) = b T(n/c) + f(n) $

主定理：

若 $ f(n) \in O(n^{\log_c b - \epsilon}) $，则 $ T(n) \in \Theta(n^{\log_c b}) $
若 $ f(n) \in \Theta(n^{\log_c b} \log^k n) $，则 $ T(n) \in \Theta(n^{\log_c b} \log^{k+1} n) $
若 $ f(n) \in \Omega(n^{\log_c b + \epsilon}) $ 且 $ a f(n/c) \leq k f(n) $，则 $ T(n) \in \Theta(f(n)) $

示例：

$ T(n) = 2T(n/2) + n \log n \Rightarrow \Theta(n \log^2 n) $
$ T(n) = 3T(n/2) + n \log n \Rightarrow \Theta(n^{\log_2 3}) $

堆的定义与操作

完全二叉树，满足堆性质（小根堆：$ A[i] \leq A[\text{child}(i)] $）
数组表示：下标从1开始，父节点 $ \lfloor i/2 \rfloor $，子节点 $ 2i, 2i+1 $
操作：
- Insert(x)：插至末尾，向上调整，$ O(\log n) $
- ExtractMin()：取根，末尾移至根，向下调整，$ O(\log n) $

快速排序平均复杂度分析

解递归式：$ A(n) = (n-1) + \frac{2}{n} \sum_{i=1}^{n-1} A(i) $

最终可得 $ A(n) \in O(n \log n) $

对抗策略分析

通过构造最坏输入序列证明算法复杂度下界。

同时找最大和最小元素

算法（分组比较法）：

分组比较：$ \lfloor n/2 \rfloor $ 次
找全局最小值：$ \lceil n/2 \rceil - 1 $ 次
找全局最大值：$ \lceil n/2 \rceil - 1 $ 次
总比较次数：偶数时 $ \frac{3n}{2} - 2 $，奇数时 $ \lceil \frac{3n}{2} \rceil - 2 $

下界证明（对抗策略）：

初始有 $ 2n $ 个候选（每个元素可能是最大或最小）
每次比较最多减少两个候选
分组阶段最多 $ \lfloor n/2 \rfloor $ 次有效比较
最终下界为 $ 2n - 2 - \lfloor n/2 \rfloor $

找第二大元素

算法（锦标赛方法）：

找最大值：$ n-1 $ 次比较
在最大值的直接对手中找最大值：$ \lceil \log n \rceil - 1 $ 次比较
总比较次数：$ n + \lceil \log n \rceil - 2 $

下界证明：第二大元素必须直接与最大值比较过。

平摊分析

栈的 MultiPop（会计法）

Push：平摊代价 2（1 支付自身，1 为未来弹出预存）
MultiPop：平摊代价 0（使用信用支付）
总平摊代价 $ \leq 2n $，每个操作平均 $ O(1) $

DeleteLargerHalf（势能法）

操作：

Insert(x)：$ O(1) $
DeleteLargerHalf()：删除 $ \lceil n/2 \rceil $ 个最大元素，$ O(n) $

势能函数：$ \Phi = 2|S| $

Insert 平摊代价：3
DeleteLargerHalf 平摊代价：$ c n - 2d \leq (c-1)n $
总平摊代价 $ O(m) $，每个操作 $ O(1) $

图搜索算法

DFS

思想：递归探索未访问邻居，回溯时处理节点
应用：
- 拓扑排序（按结束时间逆序）
- 强连通分量（Kosaraju 算法）

BFS

思想：按层遍历，使用队列
应用：
- 无权图最短路径
- 任务调度关键路径

贪心法

思想：局部最优选择扩展至全局解
需满足贪心选择性质与最优子结构
示例：
- 换硬币（特定面额最优）
- 活动安排（选最早结束）

动态规划

需满足最优子结构。

最长公共子序列（LCS）

递归式：
$$
\text{LCS}(X_i, Y_j) = \begin{cases}
0 & i=0 \text{ 或 } j=0 \
\text{LCS}(X_{i-1}, Y_{j-1}) + 1 & x_i = y_j \
\max(\text{LCS}(X_{i-1}, Y_j), \text{LCS}(X_i, Y_{j-1})) & x_i \neq y_j
\end{cases}
$$

最优二叉搜索树（OBST）

问题定义

给定键 $ k_i $ 和搜索频率 $ p_i $（成功），区间 $ d_i $ 和频率 $ q_i $（失败）
目标：最小化期望搜索代价

搜索代价公式：
$$
E[\text{cost}] = \sum_{i=1}^n (\text{depth}(k_i)+1)p_i + \sum_{i=0}^n (\text{depth}(d_i)+1)q_i
$$

核心递归式

令 $ e[i][j] $ 为包含键 $ k_i $ 到 $ k_j $ 的 OBST 期望代价，$ w(i,j) = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_l $

$$
e[i][j] = \begin{cases}
q_{i-1} & j = i-1 \
\min_{i \leq r \leq j} { e[i][r-1] + e[r+1][j] + w(i,j) } & i \leq j
\end{cases}
$$

时间复杂度：$ O(n^3) $，Knuth 优化后 $ O(n^2) $

OBST vs Huffman 树

特性	OBST	Huffman 树
键位置	有序	无序
结构要求	BST 性质	无限制
频率类型	成功 + 失败	仅叶节点
时间复杂度	$ O(n^3) $	$ O(n \log n) $
主要用途	搜索优化	数据压缩