算法期末总结

jkm Lv2

算法期末复习


前言

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

一、时间复杂度

1.1 主定理(简化形式)

对形如 的递归式:



二、分治

2.1 最大连续子数组

2.1.1 问题定义

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

2.1.2 算法

MCS

2.1.3 分析

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

2.2 逆序对的个数

2.2.1 问题定义

给定一个序列有n个数,求n个数中逆序对的个数,逆序对的定义:Misplaced &i < j\ &&\ a[i] > a[j]

2.2.2 算法

CountingInversion1
CountingInversion2

2.2.3 分析

时间复杂度:

2.3 快速排序

2.3.1 问题定义

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

2.3.2 算法

QuickSort
Partition

2.3.3 分析

时间复杂度:

三、动态规划

3.1 0-1背包问题

3.1.1 问题定义

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

3.1.2 算法

状态转移方程
Knapsack

3.1.3 分析

时间复杂度:

3.2 钢条切割问题

3.2.1 问题定义

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

3.2.2 算法

状态转移方程
RodCutting

3.2.3 分析

时间复杂度:

3.3 最小编辑距离

3.3.1 问题定义

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

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

3.3.2 算法

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

其中第一项为增加操作的代价(从),第二项为删除操作的代价(从),第三项为替换操作的代价。
MED1
MED2

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个矩阵相乘得到的矩阵的维度是,所以两部分合起来的次数是
MatrixMult

3.4.3 分析

时间复杂度:

3.5 最长公共子序列

3.5.1 问题定义

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

3.5.2 算法

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

3.5.3 分析

时间复杂度:

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

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

四、贪心

4.1 分数背包问题

4.1.1 问题定义

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

4.1.2 算法

每个物品按照单位价值(价值比上重量)排序,紧着性价比高的选。

FractionKnapsack

4.1.3 分析

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

4.2 活动选择问题

4.2.1 问题定义

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

4.2.2 算法

步骤:

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

ActivitySelection

4.2.3 分析

时间复杂度:

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

区别:活动带权重,目标改成了总权重最大。改用动态规划。
状态转移方程
WeighedActivitySelection
仍然是先对所有活动按最早结束时间排序,然后按照这个状态转移方程写动态规划。其中,p(j)是与j不冲突的结束最晚的活动。
时间复杂度

4.3 哈夫曼编码

4.3.1 问题定义

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

4.3.2 算法

步骤:

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

4.3.3 分析

时间复杂度:

五、图

5.1 BFS

5.1.1 问题定义

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

5.1.2 算法

BFS

5.1.3 分析

时间复杂度:

5.2 DFS

5.2.1 问题定义

深度优先搜索

5.2.2 算法

DFS1
DFS2

5.2.3 分析

时间复杂度:

5.3 拓扑排序

5.3.1 问题定义

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

5.3.2 算法

TopoSort

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. 输出
    SCC

5.4.3 分析

时间复杂度:

5.5 Prim算法

5.5.1 问题定义

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

5.5.2 算法

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

5.5.3 分析

时间复杂度:

5.6 Kruskal算法

5.6.1 问题定义

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

5.6.2 算法

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

5.6.3 分析

时间复杂度:

5.7 Dijkstra

5.7.1 单源最短路径

有向带权图,单源最短路径

5.7.2 算法

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

5.7.3 分析

时间复杂度:

5.8 Bellman-Ford

5.8.1 问题定义

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

5.8.2 算法

如果有负环就返回false。
BellmanFord
Relax

5.8.3 分析

时间复杂度:

5.9 Floyd

5.9.1 问题定义

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

5.9.2 算法

动态规划,状态转移方程:

遍历k次,每次选第k个结点作为中间节点
Floyd
输出结果的算法
Path

5.9.3 分析

时间复杂度:

5.10 Ford-Fulkson

5.10.1 问题定义

求最大流问题

5.10.2 算法

augmenting path增广路径
Augment
FolkFulkerson

5.10.3 分析

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

  • 标题: 算法期末总结
  • 作者: jkm
  • 创建于 : 2024-08-24 20:41:00
  • 更新于 : 2024-08-24 23:17:48
  • 链接: https://goldenkm.github.io/2024/08/24/Algorithm-Summary/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。