算法设计与分析

1. 算法分析基础

1.1 渐近记号

大O记号：上界

$f(n) = O(g(n)) \iff \exists c > 0, n_0 > 0, \forall n \geq n_0: f(n) \leq c \cdot g(n)$

Ω记号：下界

$f(n) = \Omega(g(n)) \iff \exists c > 0, n_0 > 0, \forall n \geq n_0: f(n) \geq c \cdot g(n)$

Θ记号：紧界

$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \wedge f(n) = \Omega(g(n))$

1.2 常见复杂度类

1.3 递推关系求解

主定理（Master Theorem）：

$T(n) = aT(n/b) + f(n)$

2. 分治法

2.1 基本思想

将问题分解为若干子问题，递归求解后合并：

Divide: 将问题分解为子问题
Conquer: 递归求解子问题
Combine: 合并子问题的解

2.2 经典分治算法

归并排序：

$T(n) = 2T(n/2) + O(n) = O(n \log n)$

快速排序：

• 平均：$O(n \log n)$
• 最坏：$O(n^2)$（已排序输入 + 固定主元选择）
• 随机化后期望：$O(n \log n)$

最近点对：

$T(n) = 2T(n/2) + O(n) = O(n \log n)$

Strassen 矩阵乘法：

$T(n) = 7T(n/2) + O(n^2) = O(n^{\log_2 7}) \approx O(n^{2.807})$

3. 贪心算法

3.1 贪心选择性质

局部最优选择能导致全局最优解。

3.2 经典贪心算法

活动选择问题：选择最多不重叠活动。

策略：按结束时间排序，贪心选择最早结束的活动。

Huffman 编码：

• 构建最优前缀码
• 每次合并频率最低的两个节点
• 时间复杂度：$O(n \log n)$

最小生成树：

Kruskal 算法：按边权排序，用并查集判断是否形成环。$O(E \log E)$

Prim 算法：从任一顶点出发，每次选最短边扩展。$O(E \log V)$（优先队列）

Dijkstra 最短路径：

$T = O((V + E) \log V)$

限制：不能有负权边。

3.3 贪心正确性证明

交换论证法：

1. 假设存在最优解 $O$ 与贪心解 $G$ 不同
2. 找到第一个不同的选择
3. 证明将 $O$ 的选择替换为 $G$ 的选择不会变差
4. 反复替换，最终 $O$ 变为 $G$

4. 动态规划

4.1 基本要素

最优子结构：问题的最优解包含子问题的最优解。

重叠子问题：递归求解中大量子问题被重复计算。

4.2 设计步骤

1. 定义子问题（状态）
2. 建立状态转移方程
3. 确定计算顺序（拓扑序）
4. 确定边界条件
5. 可选：空间优化

4.3 经典动态规划问题

0-1 背包：

$dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i] + v_i)$

时间：$O(nW)$，空间可优化至 $O(W)$。

最长公共子序列（LCS）：

$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } s_1[i] = s_2[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}$

编辑距离：

$dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & \text{删除} \\ dp[i][j-1] + 1 & \text{插入} \\ dp[i-1][j-1] + \text{cost} & \text{替换} \end{cases}$

矩阵链乘法：

$dp[i][j] = \min_{i \leq k < j} \{dp[i][k] + dp[k+1][j] + p_{i-1} \cdot p_k \cdot p_j\}$

4.4 状态空间优化

滚动数组：当状态转移只依赖前一行/列时，只保留两行。

单调队列优化：滑动窗口最大值问题。

斜率优化：决策单调性问题时，用凸包维护候选决策。

5. 回溯法

5.1 基本框架

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return
    for choice in choices:
        if is_valid(state, choice):
            make_choice(state, choice)
            backtrack(state, next_choices)
            undo_choice(state, choice)

5.2 剪枝策略

约束剪枝：不满足约束条件时提前返回。

限界剪枝：当前解不可能优于已知最优解时返回。

5.3 经典回溯问题

N皇后：在 $n \times n$ 棋盘放置 $n$ 个互不攻击的皇后。

子集和：从集合中选取子集使和等于目标值。

图着色：用最少的颜色给图的顶点着色，相邻顶点颜色不同。

6. 分支限界法

6.1 与回溯法的区别

6.2 优先队列式分支限界

使用优先队列按限界值排序，优先扩展最有希望的节点。

0-1 背包的分支限界：

• 上界估计：剩余物品按单位价值贪心装入
• 每次取出上界最大的节点扩展

7. NP 理论

7.1 复杂度类

7.2 NP 完全性

归约：$A \leq_p B$ 表示问题 A 可在多项式时间内归约到问题 B。

NP 完全问题：

• 属于 NP
• 所有 NP 问题可归约到它

Cook-Levin 定理：SAT 是 NP 完全的。

7.3 常见 NP 完全问题

7.4 近似算法

对于 NP 难问题，寻找近似解：

近似比：

$\rho = \max\left(\frac{\text{近似解}}{\text{最优解}}, \frac{\text{最优解}}{\text{近似解}}\right)$