算法分析与设计复习讲义

第一章 算法引论

1.1 算法与程序

算法的定义：算法是解决特定问题的一组有穷的、明确的、可执行的指令序列。算法具有以下五个基本特性：

特性	含义
有穷性	算法必须在执行有限步后终止
确定性	算法的每一步必须有确切的定义，无歧义
可行性	算法的每一步都是可执行的
输入	算法有零个或多个输入
输出	算法至少有一个输出

算法与程序的区别：

• 算法：强调有穷性，是一个抽象的计算过程描述
• 程序：是算法的具体实现，理论上可以无限运行（如操作系统），不要求有穷性

1.2 算法的时间复杂度分析

算法的时间复杂度是衡量算法效率的核心指标，通常用基本操作执行次数来衡量。

最坏情况、最好情况和平均情况：

• 最坏情况复杂度（Worst-case） ：算法在所有可能输入中执行时间的最大值——最常用
• 最好情况复杂度（Best-case） ：算法在所有可能输入中执行时间的最小值
• 平均情况复杂度（Average-case） ：算法在所有可能输入中执行时间的加权平均值，需已知输入的概率分布

1.3 渐进符号

渐进符号用于描述算法复杂度在输入规模趋于无穷时的增长趋势。

符号	名称	定义（数学表述）	含义
O(f(n))	大O符号	存在c>0，n₀>0，使0≤g(n)≤c·f(n)对所有n≥n₀成立	上界：算法最坏情况不超过f(n)的常数倍
Ω(f(n))	大Ω符号	存在c>0，n₀>0，使0≤c·f(n)≤g(n)对所有n≥n₀成立	下界：算法最好情况不低于f(n)的常数倍
Θ(f(n))	大Θ符号	同时满足O(f(n))和Ω(f(n))	紧确界：算法复杂度与f(n)同阶
o(f(n))	小o符号	对任意c>0，存在n₀，使0≤g(n)<c·f(n)	严格上界，g(n)比f(n)增长慢
ω(f(n))	小ω符号	对任意c>0，存在n₀，使0≤c·f(n)<g(n)	严格下界，g(n)比f(n)增长快

基本效率类型（从低到高）：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
常数  对数     线性   线性对数    平方    立方    指数    阶乘

1.4 非递归算法的分析方法

1. 确定作为基本操作的元操作（通常是最内层循环的操作）
2. 分析基本操作执行次数与输入规模n的函数关系
3. 用渐进符号表示复杂度

典型例子——冒泡排序：基本操作为比较和交换，时间复杂度为O(n²)。

1.5 递归算法的分析方法

递归算法的分析通常通过递归方程进行，常用方法：

（1）代入法：

• 猜测解的形式，用数学归纳法证明

（2）递归树法：

• 将递归展开成树形结构，逐层累加代价

（3）主定理（Master Theorem） ：

• 适用于形式为 T(n) = a·T(n/b) + f(n) 的递归方程
• a≥1，b>1，f(n)为渐进正函数

主定理三种情况：

设T(n) = a·T(n/b) + f(n)，其中a≥1，b>1：

情况	条件	T(n)的阶
情况1	f(n) = O(n^(log_b a - ε))，ε>0	T(n) = Θ(n^(log_b a))
情况2	f(n) = Θ(n^(log_b a))	T(n) = Θ(n^(log_b a)·log n)
情况3	f(n) = Ω(n^(log_b a + ε))，且a·f(n/b) ≤ c·f(n)（c<1）	T(n) = Θ(f(n))

第二章 递归与分治策略

2.1 递归的概念

递归是指一个函数直接或间接地调用自身。递归算法具有以下基本原则：

• 基准情形：必须有一个或多个不需要递归就能直接求解的情形
• 递推关系：将问题分解为规模更小的同类子问题
• 终止条件：确保递归能最终到达基准情形

递归算法的优缺点：

• 优点：结构清晰、可读性强、易于证明正确性
• 缺点：效率较低（函数调用开销大，可能重复计算）

2.2 分治法的基本思想

分治法（Divide and Conquer） 的基本思想：

将规模为n的问题分解为k个规模较小的、相互独立的、与原问题形式相同的子问题；递归地求解这些子问题；然后将各子问题的解合并得到原问题的解。

三个步骤：

1. 分解（Divide） ：将原问题划分为若干子问题
2. 解决（Conquer） ：递归求解子问题（子问题规模足够小时直接求解）
3. 合并（Combine） ：将子问题的解合并为原问题的解

典型时间复杂度：分治法通常满足递归式 T(n) = a·T(n/b) + O(n^d)

2.3 分治法应用举例

经典问题	分治策略	时间复杂度
二分查找	每次将查找范围缩小一半	O(log n)
归并排序	分两半分别排序后合并	O(n log n)
快速排序	选取基准将序列分区，递归排序	平均O(n log n)，最坏O(n²)
棋盘覆盖	将棋盘分为四块，处理特殊方格	O(n²)（n为棋盘规模）
线性时间选择	选择划分基准，递归查找	O(n)（最坏情况）
最接近点对	按x坐标分治，合并时检查带状区域	O(n log n)

第三章 动态规划

3.1 动态规划的基本思想

动态规划（Dynamic Programming, DP） 用于求解具有最优子结构和重叠子问题性质的问题。

两个基本要素：

要素	含义	判断方法
最优子结构	问题的最优解包含子问题的最优解	证明原问题最优解可由子问题最优解组合得到
重叠子问题	递归求解时会重复计算相同的子问题	递归树中存在相同子问题节点

动态规划与分治法的区别：

• 分治法的子问题是独立的（不重叠）
• 动态规划的子问题是重叠的（多次出现）

3.2 设计动态规划算法的步骤

1. 刻画最优子结构：分析最优解的结构特征
2. 递归定义最优值：建立最优值的递推关系
3. 自底向上计算最优值：按规模从小到大依次求解
4. 构造最优解：根据计算过程中的记录构造最优解

备忘录法：自顶向下的递归方式，为每个子问题维护一张表记录已求解结果，避免重复计算。

3.3 动态规划应用举例

经典问题	递推关系要点	时间复杂度
矩阵连乘	最优加括号位置，状态转移 m[i][j] = min{m[i][k]+m[k+1][j]+p[i-1]p[k]p[j]}	O(n³)
最长公共子序列（LCS）	c[i][j] = c[i-1][j-1]+1（x_i=y_j），else max(c[i-1][j], c[i][j-1])	O(mn)
最大子段和	dp[i] = max(dp[i-1]+a[i], a[i])	O(n)
0-1背包	dp[j] = max(dp[j], dp[j-w[i]]+v[i])（一维优化）	O(nW)，W为背包容量
最优二叉搜索树	e[i][j] = min{e[i][k-1]+e[k+1][j]+w[i][j]}	O(n³)

第四章 贪心算法

4.1 贪心算法的基本思想

贪心算法（Greedy Algorithm） 在每一步选择中都采取当前状态下最好或最优的选择，希望由此导致全局最优解。

贪心算法的两个基本要素：

要素	含义
贪心选择性质	全局最优解可以通过局部最优选择得到
最优子结构	问题的最优解包含子问题的最优解

贪心算法与动态规划的比较：

• 贪心：每一步选择局部最优，不回溯，不依赖于子问题的解
• 动态规划：考虑所有子问题的最优解，做出全局最优决策

4.2 贪心算法应用举例

经典问题	贪心策略	正确性关键
活动安排	按结束时间排序，选择最早结束的相容活动	最早结束者留下最多时间
最优装载	按重量从小到大装船	重量越轻越能装得多
哈夫曼编码	每次合并频率最小的两棵子树	最优前缀码
Prim算法	每次选择连接当前树的最短边	最小生成树
Kruskal算法	按权重从小到大选边，不形成环	最小生成树
Dijkstra算法	每次选择距离源点最近的未确定点	单源最短路径（非负权重）

第五章 回溯法

5.1 回溯法的基本思想

回溯法（Backtracking） 是一种深度优先搜索策略，系统性地搜索问题的所有解。

基本框架：

1. 定义解空间（问题的所有可能解）
2. 确定搜索解空间的组织结构（子集树、排列树等）
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

两种剪枝函数：

• 约束函数：剪去不满足约束条件的子树
• 限界函数：剪去不可能得到最优解的子树

5.2 解空间树结构

树类型	适用问题	节点数	典型例题
子集树	解为子集的问题（n个元素的子集）	2^(n+1)-1	0-1背包、子集和
排列树	解为排列的问题（n个元素的排列）	(n+1)! - 1	n后问题、旅行商

5.3 回溯法应用举例

经典问题	解空间	约束条件/限界
n后问题	n×n棋盘上放n个皇后，任意两个不在同行/列/对角线	排列树
0-1背包	物品选或不选的子集树	重量约束，价值上界剪枝
图着色问题	图中顶点着色的排列	相邻顶点颜色不同
装载问题	集装箱装入两艘船	容量约束
批处理作业调度	作业的排列	完成时间和最小化

第六章 分支限界法

6.1 分支限界法的基本思想

分支限界法（Branch and Bound） 以广度优先或最小耗费优先方式搜索解空间树，用限界函数剪枝。

两种主要形式：

类型	搜索策略	数据结构	特点
队列式（FIFO）	先进先出广度优先	普通队列	按层序扩展
优先队列式	按优先级（限界值）选择扩展	优先队列（堆）	更早找到最优解

分支限界法与回溯法的比较：

对比项	回溯法	分支限界法
搜索策略	深度优先（DFS）	广度优先/优先队列
目标	找所有解或任一解	找最优解
存储空间	较小（递归栈）	较大（需存储活结点表）
剪枝方式	约束函数+限界函数	限界函数为主

6.2 分支限界法应用举例

经典问题	限界函数要点
装载问题	上界 = 已装重量 + 剩余集装箱总重量
0-1背包	上界 = 当前价值 + 剩余物品按单位重量价值装包的背包价值
旅行商（TSP）	下界 = 已走路径长度 + 剩余顶点的最小出边之和
单源最短路径	当前路径长度，优先扩展最短路径节点

第七章 图算法与网络流

7.1 图的遍历

算法	策略	时间复杂度	应用
深度优先搜索（DFS）	尽可能深入搜索，回溯	O(V+E)	连通分量、拓扑排序、强连通分量
广度优先搜索（BFS）	逐层向外扩展	O(V+E)	无权图最短路径

7.2 最小生成树

算法	策略	时间复杂度	适用
Prim算法	从单点扩展，每次选最近边	O(E log V)（堆优化）	稠密图
Kruskal算法	按权排序，并查集判环	O(E log E)	稀疏图

7.3 最短路径

算法	适用	时间复杂度	特点
Dijkstra算法	单源，非负权重	O(E log V)（堆优化）	贪心策略
Floyd算法	所有点对，可负权（无负环）	O(V³)	动态规划
Bellman-Ford算法	单源，可负权	O(VE)	可检测负环

7.4 网络流

最大流问题：给定有向图，每条边有容量，求源点到汇点的最大流量。

Ford-Fulkerson方法的核心思想：不断在残量网络中寻找增广路径，直到不存在增广路径。

最大流-最小割定理：最大流的值等于最小割的容量。这是网络流理论的核心结论。

第八章 计算复杂性理论

8.1 P、NP、NPC、NP-hard

类别	全称	定义
P类	Polynomial Time	能在多项式时间内解决的问题
NP类	Nondeterministic Polynomial Time	能在多项式时间内验证解是否正确的问题
NPC类	NP-Complete	是NP问题，且所有NP问题都可多项式归约到它
NP-hard	NP-Hard	所有NP问题可归约到它，但不一定是NP问题（可不属于NP）

关系：P ⊆ NP；NPC = NP ∩ NP-hard。

8.2 NP完全性证明

证明一个问题L是NPC的步骤：

1. 证明L是NP问题（可在多项式时间内验证解）
2. 选取一个已知的NPC问题L'，构造从L'到L的多项式归约

经典NPC问题：

• 旅行商问题（TSP）
• 哈密顿回路问题
• 顶点覆盖问题
• 子集和问题
• 最大团问题

8.3 近似算法与概率算法

近似算法：用于解决NP-hard问题的近似最优解算法，评价指标为近似比（近似解/最优解的比值上限）。

近似算法	问题	近似比
顶点覆盖贪心	最小顶点覆盖	2倍
旅行商最近邻	TSP（满足三角不等式）	2倍
子集和近似	子集和问题	任意精度（FPTAS）

概率算法：

类型	特点	典型例子
舍伍德（Sherwood）	总能给出正确答案，改善平均性能	随机化快速排序
蒙特卡罗（Monte Carlo）	可能给出错误答案，但错误概率可控	素数判定
拉斯维加斯（Las Vegas）	总能给出正确答案，运行时间不确定	随机化选择

8.4 可计算性

• 可计算问题：存在算法能求解的问题
• 不可计算问题：不存在任何算法能求解的问题（如停机问题）
• 易解问题：存在多项式时间算法的问题（P类）
• 难解问题：指数时间算法、NP-hard问题

附录：考试形式与备考建议

参考书目

1. 《算法导论》（原书第3版） ，Thomas H. Cormen等，机械工业出版社——最权威的经典教材
2. 《计算机算法设计与分析》（第5版） ，王晓东，电子工业出版社——国内主流教材
3. 《算法设计与分析》 ，王红梅、胡明，清华大学出版社——部分高校指定参考书

考试内容结构

根据多所高校考研大纲，典型试卷结构为：

• 客观题（约30%） ：选择题、填空题、判断题
• 主观题（约70%） ：算法分析题、算法设计题、论述题

复习重点提醒

• 重中之重：动态规划（0-1背包、LCS、矩阵连乘）、贪心算法（活动安排、最小生成树、Dijkstra）、回溯法（n后、0-1背包）
• 高频考点：主定理求递归复杂度、渐进符号判断、NP完全性证明思路
• 图算法必考：最小生成树、最短路径、最大流
• 分析设计题：通常给一个新问题，要求选择合适策略设计算法并分析复杂度