算法期末总结

算法期末复习
前言
对照着潘老师的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 算法
状态转移方程:如果
其中第一项为增加操作的代价(从
3.3.3 分析
时间复杂度:
3.4 矩阵连乘
3.4.1 问题定义
给定n个矩阵,确定计算矩阵连乘积的计算次序,使得到正确结果需要付出的代价最少。
3.4.2 算法
状态转移方程:
对该状态转移方程的理解:首先,一个规模为
3.4.3 分析
时间复杂度:
3.5 最长公共子序列
3.5.1 问题定义
给定两个字符串 s1 和 s2,返回这两个字符串的最长公共子序列的长度。子序列的定义:由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。子序列不一定连续。
3.5.2 算法
状态转移方程:
如果
否则有
对该状态转移方程的理解:令
否则,说明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 算法
步骤:
- 按结束时间最短排序
- 一旦选了一个活动,把所有重叠的活动删掉
- 重复以上步骤
4.2.3 分析
时间复杂度:
4.2.4 衍生问题:带权重的活动选择
区别:活动带权重,目标改成了总权重最大。改用动态规划。
状态转移方程:
仍然是先对所有活动按最早结束时间排序,然后按照这个状态转移方程写动态规划。其中,p(j)是与j不冲突的结束最晚的活动。
时间复杂度:
4.3 哈夫曼编码
4.3.1 问题定义
给定一个若干个字符与出现频率,求平均编码长度最短的编码方式。
4.3.2 算法
步骤:
- 借助优先队列,将所有字符按出现频率从低到高排序
- 每次选择出现频率最小的两个构成一个新的节点,重新入队
- 重复以上步骤
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 算法
步骤:
- 先求G的反向图
- 在
上DFS,得到一个序列 (当有一个结点遍历完所有邻居的时候,就把它放进 ) - 将
反向得到L - 按以下规则对L进行DFS
- 从L的第一个结点开始
- 当一次重新开始后,从L的第一个未遍历过的顶点开始
- 输出
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 分析
时间复杂度:取决于最大流量,可能很糟,但更好的算法也没讲
- 标题: 算法期末总结
- 作者: 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 进行许可。