Welcome!

0 %
Yun Peng
A first-year Ph.D. student in CUHK
  • Chinese Name
    彭昀
  • Major
    Computer Science
  • City
    Hong Kong
  • Age
    20
  • Mail
    normal@yunpeng.work
Research Interest
Software Engineering
Computer Security
Artificial Intelligence

算法导论总结

April 16, 2021
算法基础期末总结

算法基础期末总结

算法分析

一、排序算法

1、插入排序:

最坏情况: 当数组逆序时发生

最好情况: 当数组顺序时发生

算法时间复杂度主要来自对数组的遍历以及元素的移动,修改搜索算法并不能改进时间复杂度

稳定

2、归并排序:

递归式:

稳定

3、堆排序:

与堆排序相关的过程的时间复杂度:

MAX-HEAPIFY:

BUILD-MAX-HEAP:

MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY:

HEAP-MAXIMUM:

在一个包含n个元素的堆中,所有优先队列的操作都可以在时间内完成

不稳定

4、快速排序:

最坏情况: 当每次都将数组划分为n-1和0个元素的时候发生

最好情况: 当每次划分都将数组均分时产生

平均情况: 当划分是常数比例或者好划分和差划分同时出现时产生

随机快速排序算法期望运行时间:

主要看partition过程中比较元素时有没有加等号来确定稳定性,加了等号即稳定(算法导论中的算法稳定)

5、计数排序:

稳定

k表示数的上界,若,则计数排序的时间复杂度为

适用于的整数排序

6、基数排序:

子过程必须使用稳定的排序算法

按r位一起排序:

并不一定比基于比较的排序算法好,因为基数排序并非原址排序且常数项因子大小不同

稳定

7、桶排序:

假设数据服从均匀分布

平均情况下:

算法导论中描述的桶排序稳定

在最坏情况下,任何排序算法都需要做次比较

堆排序和归并排序是渐进最优的比较排序算法,因为它们的时间上界为

二、递归算法

1、求Fibonacci数

一般递归算法:

改进后的递归算法:

2、二分查找

3、全排列生成

4、Strassen矩阵乘法

三、选择算法

1、最大最小值算法

单独找最大最小值,需要比较n-1次

一起找最大最小值,需要比较

一起找最大值和次大值或者一起找最小值和次小值,需要比较

2、寻找数组中第i小元素的算法

RANDOMIZED-SELECT:

期望时间:

最坏情况: 当划分与快速排序中最坏情况划分一致时

SELECT:

最坏情况:

递归式:

元素必须互异

四、动态规划算法

适用动态规划算法的问题需具备的性质:①、最优子结构 ②、重叠子问题

分治法适用于每一步生成的子问题都不同的问题

最优子结构:原问题的最优解包含子问题的最优解,子问题间的解无关

重叠子问题:有些子问题不止被求解一次

1、多段图规划:

2、矩阵链乘法:

递归式:

3、最大子段和:

递归式:

4、最长公共子序列:

递归式:

五、贪心算法

适用于贪心算法的问题需具备的性质:①、最优子结构 ②、贪心选择性质

贪心选择性质:直接作出在当前问题看来最优的解,不考虑子问题的解

与动态规划算法的比较:

①、在每一步中,动态规划算法在得知子问题的解后做出选择,而贪心算法先做出局部最优的选择而不考虑子问题的解

②、动态规划自底向上,贪心算法自顶向下

③、动态规划比贪心算法更复杂,效率更低

0-1背包问题不满足贪心选择性质,小数背包问题满足

1、小数背包问题:

按价值率最大贪心,主要运行时间来自价值率的排序,若不需要排序,则运行时间为

2、活动选择问题:

按活动结束时间贪心,主要运行时间来自排序,若不需要排序,则运行时间为

3、最优装载问题:

按货物重量贪心,主要运行时间来自排序,若不需要排序,则运行时间为

4、找钱问题: (n为面额种类)

先按最大面额找,不能满足再换小一点的面额,如此循环

六、回溯算法

回溯法是一种深度优先的带有跳跃性算法

适用于求解组合数较大的问题

优化方法:

①、用约束函数剪去不满足约束的子树

②、用限界函数剪去不能得到最优解的子树

子集树框架:(可以选择某一个值取或者不取)

循环:

试探当前层的所有取值,检查是否合法,合法即进入下一层试探

排列树框架:(所有值必须取,且只能取一次)

循环:

交换当前层的值与其它层的值,检查是否合法,合法进入下一层试探,恢复交换

需要有一个初始的解

1、n皇后问题

子集树框架

2、排列生成问题

排列树框架

3、TSP问题

排列树框架

4、0-1背包问题

子集树框架

七、摊还分析

分析一个n个操作的序列的平均代价,得到更加紧确的时间上界(虽然有些操作代价很高,但是大部分操作代价很低的情况尤为适用)

1、聚合分析

计算整个操作序列的总代价,除以n,即

2、记账/核算法

给每个操作赋予一个代价

3、势能法

不将预付代价表示为信用,而表示为势能,通过势能的释放来支付代价

势函数为(),每个操作的摊还代价为,实际代价为

八、图论算法

1、BFS:

黑色结点:已经访问过的结点

灰色结点:还没访问过但是已经发现的结点

白色结点:尚未发现的结点

算法的时间复杂度由一开始的结点初始化和后面的对边的扫描产生

前驱子图是一棵广度优先树

2、DFS:

两个时间戳:

表示被修改为灰色的时间

表示被修改为黑色的时间

算法的时间复杂度由一开始的结点初始化和后面的对点的扫描产生

前驱子图形成一个由多棵深度优先树构成的深度优先森林

在深度优先森林中,的后代当且仅当在发现结点的时间,存在一条从结点到结点的全部由白色结点构成的路径

边的分类:

树边:深度优先森林里的边

后向边:从一个节点连接到它在深度优先树上的一个祖先的边

前向边:从一个节点连接到它在深度优先树上的一个后代的边

横向边:其他所有的边

第一次探索时:

为白色结点->为树边

为灰色结点->为后向边

为黑色结点->为前向边或横向边

无向图进行深度优先搜索时,每条边要么是树边,要么是后向边

3、最小生成树算法

①、Kruskal:

在所有连接森林中两棵不同的树的边里,找到权重最小的边

算法只要使用不相交集合操作完成

主要时间复杂度来自于对边权重的排序和循环中的UNION操作

②、Prim:

在连接集合A中的点和集合A以外的点的边中,找到权重最小的边

在使用二叉堆作为优先队列的实现方式时:

EXTRACT-MIN总时间:

修改之后维护优先队列总时间:

初始化结点总时间:

三者相加即是总时间

若用Fibonacci堆作为有限队列的实现方式,则算法的时间复杂度为

Kruskal算法适用于边数不多的稀疏图,Prim算法适用于边数很多的稠密图

3、单源最短路径算法

①、Bellman-Ford算法:

把每一条边松弛

允许环的存在,存在有负值的回路时会返回FALSE

②、DAG算法:

将结点拓扑排序,按拓扑序松弛结点

算法时间复杂度主要来自于拓扑排序和for循环

拓扑排序:使用深度优先搜索,将结点按完成时间从大到小排序

允许负权值的边存在,但是不允许负值回路

③、Dijkstra算法:

使用最小优先队列,一开始将所有节点加入最小优先队列,每次取出最小的结点,松弛这一节点相邻的结点,直到优先队列为空

EXTRACT-MIN总时间:

RELAX总时间(加上维护优先队列):

若使用Fibonacci堆作为最小优先队列,时间复杂度为

该算法解决有向无环图的最短路径问题,要求权重为非负值

4、所有结点对的最短路径算法

①、矩阵算法:

表示结点到结点的至多包含条边的任意路径的最小值

递归式:

计算一个矩阵耗时

原始算法(计算)总时间:

改进算法(计算)总时间:

不能包含权重为负值的回路

2、Floyd-Warshall算法:

递归式:

不能包含权重为负值的回路

3、Johnson算法:

新加一个节点,以为源节点,使用Bellman-Ford算法,求出每个节点与之间的最短路径长度

修改路径权重

使用次Dijkstra算法

允许负值的权重和权重为负值的回路

若使用Fibonacci堆来实现优先队列,则算法总时间为

适用于稀疏图

九、数论算法

是线性组合集中的最小正元素

定理:

,则

,则

1、Euclid算法:

递归式:

EXTENDED-EUCLID:

递归式:

2、线性模方程解法

当且仅当时,方程对于未知量有解,解为

乘法逆元:的解,其中

3、线性同余方程组的求解

是除以外的所有的乘积

4、RSA公钥加密算法

选择两个大素数

计算

选择一个与互质的小奇数

对模,计算的乘法逆元

公钥为,私钥为

加密:

解密:

知道之后破解的两个素数

因为,所以很容易确定

可以得到

5、素数测试算法

素数定理:

①、简单素数测试方法:

中的某个数整除,则不是素数

②、随机算法:在n附近获取一个素数,大概要检查个数

素数均满足

③、伪素数测试算法:测试一个数是否满足上式,不满足则一定是合数,满足不一定是素数,可能是伪素数

④、Miller-Rabin随机性素数测试算法:

对伪素数测试算法的改进:采用多个(个)基,在计算的过程中是否存在模余1的非平凡平方根

位数,算法进行次算术运算和次位运算

算法误判率不超过

十、字符串匹配算法

1、朴素算法:

最坏情况在模式串和待测串都是同一个元素组成的时候产生(每一次匹配都成功)

2、Rabin-Karp算法

将模式串看成一个整数,待测串中相同位数的串看成整数,比较两个整数的模n的值

整数的计算:

预处理时间:

最坏情况:

平均情况:

3、有限自动机

预处理时间: 为一个元素可选的输入总数

运行时间:

4、KMP算法

预处理时间:

运行时间:

前缀函数:是能构成真后缀的最长前缀长度

十一、主定理

对递归式

,则

,则

(c < 1, n足够大),则

数据结构

1、红黑树

性质:一棵有n个内部节点的红黑树的高度至多为

LEFT-ROTATE、RIGHT-ROTATE:

RB-INSERT、RB-DELETE:

RB-INSERT的三种调整情况:

当z的父母为红色时:

①、z的叔节点是红色的

z颜色不变,z的父母和叔节点全部改为黑色,z的父母的父母改为红色

z置为z的父母的父母

②、z的叔节点是黑色的且z是右孩子

z变为z的父母,左旋,使z变为左孩子,转③

③、z的叔节点是黑色的且z是左孩子

z的父母的父母右旋,且颜色改为红色,z的父母改为黑色

一次循环至多2次旋转,②->③

RB-DELETE:

删除z时,若z的子节点少于2个,则将z删除,z的子节点补位,补位节点颜色不改变,若z原来是黑色的,则以补位节点为参数进入调整

若z的子节点为2个,则找到z的右子树中的最左节点,取出它,处理它的子树后用它补位,补位节点颜色与原节点一致,若补位节点原来是黑色的,则以补位节点原右子树的根为参数进入调整

四种调整情况:

当x是黑色时:

①、x的兄弟节点是红色的

x的兄弟节点改为黑色,x的父母改为红色并左旋

x不动,x的兄弟节点发生变化,重新求x的兄弟节点,转②或③或④

②、x的兄弟节点是黑色的,而且x的兄弟节点的子节点都是黑色

将x的兄弟节点改为红色

x变为x的父母

③、x的兄弟节点是黑色的,而且x的兄弟节点的左孩子是红色,右孩子是黑色

x的兄弟节点的左孩子改为黑色,x的兄弟节点改为红色并右旋,转④

④、x的兄弟节点为黑色,而且x的兄弟节点的右孩子为红色

x的父母改为黑色,x的兄弟节点改为红色,x的兄弟节点的右孩子改为黑色,x的父母左旋

x变为根

x的颜色为红色或x为根节点时退出循环,x的颜色要改为黑色

一次循环至多3次旋转,①->③->④

2、动态顺序统计树

OS-SELECT、OS-RANK:

INSERT、DELETE:

3、区间树

INTERVAL-SEARCH:

4、二项树

二项树由两棵二项树构成,一棵树的根是另一棵树的根的最左孩子

性质:

①、共有个结点

②、高度为

③、在深度处恰好有个结点

④、根的度数为,大于其他任何结点的度数,根的孩子从左到右依次为的根

⑤、在一棵包含个结点的二项树中,任意结点的最大度数为

5、二项堆

二项堆由满足下列两条性质的一组二项树构成:

①、每个二项树满足最小堆性质,结点的关键字大于等于父母结点的关键字

②、对于任意非负整数,在二项堆中最多有一颗二项树的根结点的度数为,故在一个有个结点的二项堆中,最多包含棵二项树

INSERT、MINIMUM、UNION:

EXTRACT-MIN、DECREASE-KEY、DELETE:

与二叉堆时间复杂度不同的操作是MINIMUM(二叉堆:二项堆:)、UNION(二叉堆:二项堆:)

UNION操作的情况:

①、x和next-x指向的两棵二项树度数不一样

不需要连接,直接跳过

②、x和next-x指向的两棵二项树度数一样,但是next-x的后一棵二项树的度数也一样

不需要连接前两棵树,跳过一个,连接后两棵树

③、x和next-x指向的两棵二项树度数一样

根据x的根和next-x的根的大小情况,确定怎样形成一棵新树,注意当x为表头时要更改

INSERT:

将插入的新节点当成一个新堆,合并两个新堆

EXTRACT-MIN:

将包含最小关键字的二项树从原来的堆上删除,将取出的二项树的根节点删掉,剩下的变为一个二项堆,合并两个二项堆

DECREASE-KEY:

修改一个节点的关键字之后让其冒泡上升

DELETE:

将要删除的关键字减小到正无穷

调用EXTRACT-MIN

6、不相交集合

可用于求强连通分量

使用链表表示:

MAKE-SET:

具有n个MAKE-SET操作的m个包含MAKE-SET、UNION、FIND-SET操作的序列集合的时间复杂度为:

未经过任何优化:

采用加权合并式的启发策略(总是将表长较小的集合合并到表长较大的集合中):

使用森林表示:

按秩合并、路径压缩

具有n个MAKE-SET操作的m个包含MAKE-SET、UNION、FIND-SET操作的序列集合的时间复杂度为:

单独使用按秩合并:

单独使用路径压缩: 为FIND-SET操作总数

同时使用按秩合并和路径压缩:

 

特殊公式

1.

2.

3.

4.

 

Posted in TechnologyTags:
Write a comment
© 2021 All Rights Reserved.