算法期末总结

算法期末复习

---

前言

对照着潘老师的ppt每个算法的逐个总结，非官方出品。不得不说潘老师的英文ppt看着真是有点痛苦，能去童老师蹭课还是去蹭一下吧，不要像我当年一样懒，期末啃了半天算法还是考的稀烂。但不得不说北航的算法考的还是比较友好的，除了最后一个题有点难度其他基本是送分，当然平时作业好好理解的话都拿下也是完全可能的。

一、时间复杂度

1.1 主定理（简化形式）

对形如 的递归式：

二、分治

2.1 最大连续子数组

2.1.1 问题定义

找一个数组中和最大的子数组

2.1.2 算法

2.1.3 分析

依据主定理，两个递归式的时间复杂度分别为，总的时间复杂度递推式为，时间复杂度为。（用动态规划可以缩小到）

2.2 逆序对的个数

2.2.1 问题定义

给定一个序列有n个数，求n个数中逆序对的个数，逆序对的定义：。

2.2.2 算法

2.2.3 分析

时间复杂度：

2.3 快速排序

2.3.1 问题定义

核心思想就是每次选一个pivot，将所有小于pivot的元素放在pivot左边，将所有大于pivot的元素放在pivot右边。最后能得到pivot左右两边各有一个子数组，重复该步骤。具体过程比较复杂，课件上的例子也没有，直接背代码就完事了。

2.3.2 算法

2.3.3 分析

时间复杂度：

三、动态规划

3.1 0-1背包问题

3.1.1 问题定义

给定背包容量W，和每个物品的价值v和重量w，每个物品只有一件，求怎么装价值最大。

3.1.2 算法

状态转移方程：

3.1.3 分析

时间复杂度：

3.2 钢条切割问题

3.2.1 问题定义

给定一条绳子的总长度，和不同长度的绳子对应的价值，求怎么切价值最大

3.2.2 算法

状态转移方程：

3.2.3 分析

时间复杂度：

3.3 最小编辑距离

3.3.1 问题定义

两个单词 word1 和 word2，返回将 word1 转换成 word2 所使用的最少操作数。
操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

3.3.2 算法

状态转移方程：如果, substitutionCost = 0，否则substitutionCost = 1，最终的转移方程为：

其中第一项为增加操作的代价（从到），第二项为删除操作的代价（从到），第三项为替换操作的代价。

3.3.3 分析

时间复杂度：，其中m为word1的长度，n为word2的长度。

3.4 矩阵连乘

3.4.1 问题定义

给定n个矩阵，确定计算矩阵连乘积的计算次序，使得到正确结果需要付出的代价最少。

3.4.2 算法

状态转移方程：
对该状态转移方程的理解：首先，一个规模为 的矩阵与一个规模为 的矩阵相乘，乘积次数为 。该状态转移方程由三部分构成，把第i个矩阵到第j个矩阵从第k个矩阵分开，第一部分为第i到k个矩阵相乘的次数，第二部分为第k到j个矩阵相乘的次数，第三部分也是最难理解的部分，是把前两部分得到的两个矩阵再相乘的次数。第i个矩阵的维度是，第i到k个矩阵相乘得到的矩阵的维度是，第k到j个矩阵相乘得到的矩阵的维度是，所以两部分合起来的次数是。

3.4.3 分析

时间复杂度：

3.5 最长公共子序列

3.5.1 问题定义

给定两个字符串 s1 和 s2，返回这两个字符串的最长公共子序列的长度。子序列的定义：由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。子序列不一定连续。

3.5.2 算法

状态转移方程：
如果，有 ；
否则有
对该状态转移方程的理解：令表示LCS。如果，说明是和的最大公共子序列，所以和的LCS长度就等于和的LCS长度+1。
否则，说明LCS并不以或结尾，此时的既是、的LCS，也是、的LCS，我们取二者之间较大的那个。

3.5.3 分析

时间复杂度：

3.5.4 类似问题：最大公共子串

区别：子序列不要求连续，子串要求连续。
改进状态转移方程：
如果，有 ；
否则有

四、贪心

4.1 分数背包问题

4.1.1 问题定义

与0-1背包的区别：每个物品可以取它的一部分，不再是只有取或不取。同样是求总价值最大。

4.1.2 算法

每个物品按照单位价值（价值比上重量）排序，紧着性价比高的选。

4.1.3 分析

排序的时间复杂度是，装填的时间复杂度是，总时间复杂度是。

4.2 活动选择问题

4.2.1 问题定义

给定若干个活动，活动有开始时间和结束时间，活动之间不能重叠，求怎么安排能去的活动最多。

4.2.2 算法

步骤：

1. 按结束时间最短排序
2. 一旦选了一个活动，把所有重叠的活动删掉
3. 重复以上步骤

4.2.3 分析

时间复杂度：。

4.2.4 衍生问题：带权重的活动选择

区别：活动带权重，目标改成了总权重最大。改用动态规划。
状态转移方程：

仍然是先对所有活动按最早结束时间排序，然后按照这个状态转移方程写动态规划。其中，p(j)是与j不冲突的结束最晚的活动。
时间复杂度：

4.3 哈夫曼编码

4.3.1 问题定义

给定一个若干个字符与出现频率，求平均编码长度最短的编码方式。

4.3.2 算法

步骤：

1. 借助优先队列，将所有字符按出现频率从低到高排序
2. 每次选择出现频率最小的两个构成一个新的节点，重新入队
3. 重复以上步骤
   

4.3.3 分析

时间复杂度：

五、图

5.1 BFS

5.1.1 问题定义

广度优先搜索，用队列，每次弹出一个顶点，把邻接结点入队

5.1.2 算法

5.1.3 分析

时间复杂度：

5.2 DFS

5.2.1 问题定义

深度优先搜索

5.2.2 算法

5.2.3 分析

时间复杂度：

5.3 拓扑排序

5.3.1 问题定义

一个有向无环图（DAG），按照结点先后顺序排序（拓扑序不唯一）。
步骤：每次找一个入度为0的点，删去所有以它为端点的边，重复直到删去所有点。

5.3.2 算法

5.3.3 分析

时间复杂度：

5.4 强连通分量

5.4.1 问题定义

强连通分量：有向图中，任意两点都有路径。（不能单向路径，必须有来回）

5.4.2 算法

步骤：

1. 先求G的反向图
2. 在上DFS，得到一个序列（当有一个结点遍历完所有邻居的时候，就把它放进）
3. 将反向得到L
4. 按以下规则对L进行DFS
   1. 从L的第一个结点开始
   2. 当一次重新开始后，从L的第一个未遍历过的顶点开始
5. 输出
   

5.4.3 分析

时间复杂度：

5.5 Prim算法

5.5.1 问题定义

无向有权图，求最小生成树

5.5.2 算法

步骤：每次都将已经构造出的树看成一个顶点，求将邻接顶点中权值最小的边放进最小生成树。需要维护一个优先队列

5.5.3 分析

时间复杂度：

5.6 Kruskal算法

5.6.1 问题定义

无向有权图，求最小生成树

5.6.2 算法

步骤：先对所有边排序，每次都选择最小的边加入最小生成树，如果加入这条边构成了一个环，就删掉这条边。是否成环需要用并查集判断。

5.6.3 分析

时间复杂度：

5.7 Dijkstra

5.7.1 单源最短路径

有向带正权图，单源最短路径

5.7.2 算法

借助优先队列，遍历到一个结点，看从它到它的邻接顶点的距离是否小于原来的距离，如果小于就更新。

5.7.3 分析

时间复杂度：

5.8 Bellman-Ford

5.8.1 问题定义

单源最短路径，可以带负权

5.8.2 算法

如果有负环就返回false。

5.8.3 分析

时间复杂度：

5.9 Floyd

5.9.1 问题定义

所有点的最短路径，图可以带负权，但不能带负环

5.9.2 算法

动态规划，状态转移方程：

遍历k次，每次选第k个结点作为中间节点

输出结果的算法

5.9.3 分析

时间复杂度：

5.10 Ford-Fulkson

5.10.1 问题定义

求最大流问题

5.10.2 算法

augmenting path增广路径

5.10.3 分析

时间复杂度：取决于最大流量，可能很糟，但更好的算法也没讲