算法设计与分析

1. 算法分析基础

1.1 渐近记号

大O记号：上界

$f(n)=O(g(n))⟺\exists c>0,n_0>0,\forall n\ge n_0:f(n)\le c\cdot g(n)$

Ω记号：下界

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

Θ记号：紧界

$f(n)=\Theta (g(n))⟺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{array}{ll}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{array}$

编辑距离：

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

矩阵链乘法：

$dp[i][j]={\min }_{i\le 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{\le }_{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)$