算法导论总结

2020年2月6日 0 条评论 145 次阅读 1 人点赞

算法分析

一、排序算法

1、插入排序:

最坏情况:$\Theta (n^2)$ 当数组逆序时发生

最好情况:$\Theta(n)$ 当数组顺序时发生

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

稳定

2、归并排序:$\Theta (nlogn)$

递归式:$T(n) = 2T(\frac{n}{2}) + \Theta(n)$

稳定

3、堆排序: $O (nlogn)$

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

MAX-HEAPIFY: $O(logn)$

BUILD-MAX-HEAP: $O(n)$

MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY: $O(logn)$

HEAP-MAXIMUM:$O(1)$

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

不稳定

4、快速排序:

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

最好情况: $O(nlogn)$ 当每次划分都将数组均分时产生

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

随机快速排序算法期望运行时间: $O(nlogn)$

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

5、计数排序:$\Theta(k+n)$

稳定

k表示数的上界,若$k=\Theta(n)$,则计数排序的时间复杂度为$\Theta ( n)$

适用于$k=\Theta(n)$的整数排序

6、基数排序:$ \Theta (d(n+k) ) $

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

按r位一起排序:$\Theta((\frac{d}{r})(n+2^r))$

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

稳定

7、桶排序:$O(n)$

假设数据服从均匀分布

平均情况下:$O( n)$

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

在最坏情况下,任何排序算法都需要做$\Omega(nlogn)$次比较

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

二、递归算法

1、求Fibonacci数

一般递归算法:$\Omega ((\frac{3}{2})^n)$

改进后的递归算法:$\Theta (n)$

2、二分查找 $O (logn)$

3、全排列生成 $O(n!)$

4、Strassen矩阵乘法 $\Theta(n^{log7})$

三、选择算法

1、最大最小值算法

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

一起找最大最小值,需要比较$3\lfloor \frac{n}{2} \rfloor$次

一起找最大值和次大值或者一起找最小值和次小值,需要比较$n+\lceil logn \rceil - 2$次

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

RANDOMIZED-SELECT:

期望时间:$O(n)$

最坏情况:$\Theta(n^2)$ 当划分与快速排序中最坏情况划分一致时

SELECT:

最坏情况:$O(n)$

递归式:$T(n) \leq T(\lceil \frac{n}{5} \rceil) + T(\frac{7n}{10} + 6) + O(n)$

元素必须互异

四、动态规划算法

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

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

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

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

1、多段图规划:$O (n+e)$

2、矩阵链乘法:$O(n^3)$

递归式:$m[i,j] = min{i \leq k \lt j}{m[i,k] + m[k+1,j] + p{i-1}p_kp_j}$ $m[i,i] = 0$

3、最大子段和:$O (n)$

递归式:$b[j] = max{b[j-1]+a_j,0}$

4、最长公共子序列:$O(mn)$

递归式:$c[i,j] = c[i-1,j-1] + 1 (i,j > 0且x_i = y_j)$ $c[i,j] = max(c[i,j-1],c[i-1,j]) (i,j > 0 且 x_i \neq y_j)$

$c[i,j] = 0 (i = 0 或 j = 0)$

五、贪心算法

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

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

与动态规划算法的比较:

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

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

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

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

1、小数背包问题:$O (nlogn)$

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

2、活动选择问题:$O (nlogn)$

按活动结束时间贪心,主要运行时间来自排序,若不需要排序,则运行时间为$\Theta(n)$

3、最优装载问题:$O (nlogn)$

按货物重量贪心,主要运行时间来自排序,若不需要排序,则运行时间为$\Theta(n)$

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

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

六、回溯算法

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

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

优化方法:

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

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

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

循环:

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

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

循环:

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

需要有一个初始的解

1、n皇后问题

子集树框架

2、排列生成问题

排列树框架

3、TSP问题

排列树框架

4、0-1背包问题

子集树框架

七、摊还分析

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

1、聚合分析

计算整个操作序列的总代价,除以n,即$T(n)/n$

2、记账/核算法

给每个操作赋予一个代价

3、势能法

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

势函数为$\Phi$($\Phi(D_n) \geq \Phi(D_0)$),每个操作的摊还代价为$\hat{c}$,实际代价为$c$

$\hat{c} _1 = c_i + \Phi(Di) - \Phi(D {i-1})\$

$\sum ^n {i=1} \hat{c} = \sum ^n {i=1} c + \Phi(D_n) - \Phi(D_0)$

八、图论算法

1、BFS:$O( V+E )$

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

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

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

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

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

2、DFS:$\Theta(V+E)$

两个时间戳:

$v.d$表示被修改为灰色的时间

$v.f$表示被修改为黑色的时间

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

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

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

边的分类:

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

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

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

横向边:其他所有的边

第一次探索$(u,v)$时:

$v$为白色结点->$(u,v)$为树边

$v$为灰色结点->$(u,v)$为后向边

$v$为黑色结点->$(u,v)$为前向边或横向边

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

3、最小生成树算法

①、Kruskal:$O( ElogV)$

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

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

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

②、Prim:$O( ElogV)$

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

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

EXTRACT-MIN总时间:$O(VlogV)$

修改$v.key$之后维护优先队列总时间:$O(ElogV)$

初始化结点总时间:$O(V)$

三者相加即是总时间

若用Fibonacci堆作为有限队列的实现方式,则算法的时间复杂度为$O(E + VlogV)$

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

3、单源最短路径算法

①、Bellman-Ford算法:$O(VE)$

把每一条边松弛$|V|-1$次

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

②、DAG算法:$\Theta(V+E)$

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

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

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

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

③、Dijkstra算法:$O (ElogV) $

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

EXTRACT-MIN总时间:$O(VlogV )$

RELAX总时间(加上维护优先队列):$O(Elog V)$

若使用Fibonacci堆作为最小优先队列,时间复杂度为$O(VlogV+E)$

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

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

①、矩阵算法:

$l ^{(m)} _{ij} $表示结点$i$到结点$j$的至多包含$m$条边的任意路径的最小值

递归式:$l ^{(m)} {ij} = min(l ^{(m-1)} {ij}, min {1 \leq k \leq n}{l ^{(m-1)} {ik} + w_{kj}})$

计算一个$L$矩阵耗时$O(n^3)$

原始算法(计算$L_1,...,L_n$)总时间:$O(n^4)$

改进算法(计算$L_1,L_2,L_4,...,L_n$)总时间:$O(n^3logn)$

$\delta(i,j) = l ^{(n-1)} {ij} = l ^{(n)} {ij} = ...$

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

2、Floyd-Warshall算法:$\Theta(n^3)$

递归式:$d ^{(k)} {ij} = min(d ^{(k-1)} {ij}, d ^{(k-1)} {ik} + d ^{(k-1)} {kj})$

$\delta(i,j) = d ^{(n)} _{ij}$

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

3、Johnson算法:$O (VElogV)$

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

修改路径权重$w$:$\hat{w}(u,v) = w(u,v) + h(u) - h(v)$

使用$V$次Dijkstra算法

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

若使用Fibonacci堆来实现优先队列,则算法总时间为$O(V^2logV + VE)$

适用于稀疏图

九、数论算法

$gcd(a,b)$是线性组合集${ax+by:x,y \in Z}$中的最小正元素

定理:

若$d|a,d|b$,则$d|gcd(a,b)$

$gcd(na,nb)=ngcd(a,b)$

若$n|ab$且$gcd(a,n) = 1$,则$n|b$

1、Euclid算法:$O (logb)$

递归式:$gcd(a,b) = gcd(b,a mod b)$

EXTENDED-EUCLID:

递归式:$(d,x,y) = (d',y',x'- \lfloor \frac{a}{b} \rfloor y')$

2、线性模方程解法

当且仅当$gcd(a,n)|b$时,方程$ax=b(modn)$对于未知量$x$有解,解为$x_i = x_0 + i(n/gcd(a,n))$$i=0,1,...,gcd(a,n)-1$

$gcd(a,n) = ax' + ny'$,$x_0 = x'(b/gcd(a,n))mod n$

乘法逆元:$ax=1(modn)$的解$x$,其中$gcd(a,n) = 1$

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

$m_i$是除$n_i$以外的所有$n$的乘积

$c_i = m_i \cdot (m_i ^{-1} mod n_i)$

$n=n_1n_2...n_k$

$x= (a_1c_1 + a_2c_2 + ... + a_kc_k)(modn)$

4、RSA公钥加密算法

选择两个大素数$p,q$

计算$n=pq$

选择一个与$(p-1)(q-1)$互质的小奇数$e$

对模$(p-1)(q-1)$,计算$e$的乘法逆元$d$

公钥为$(e,n)$,私钥为$(d,n)$

加密:$P(M)=M^e mod n$

解密:$S(C) = C^d mod n$

知道$ed$之后破解$n$的两个素数$p,q$:

$ed-1=k(p-1)(q-1)$

因为$e,d \lt (p-1)(q-1)$,所以很容易确定$k$

$p+q = n -(ed-1)/k +1$

$ed-1=k(p-1)(p+q-p-1)$

可以得到$p$

5、素数测试算法

素数定理:$lim _{n->\infty} \frac{\pi(n)}{n/lnn} = 1$

①、简单素数测试方法:$\Theta(\sqrt{n})$

若$n$被$2,3,...,\lfloor \sqrt{n} \rfloor$中的某个数整除,则$n$不是素数

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

素数$n$均满足$a^{n-1} = 1(modn)$

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

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

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

若$n$为$\beta$位数,算法进行$O(s \beta)$次算术运算和$O(s\beta ^3)$次位运算

算法误判率不超过$2^{-s}$

十、字符串匹配算法

1、朴素算法:$O ((n-m+1)m)$

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

2、Rabin-Karp算法

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

整数的计算:

$ t_{s+1} = (d(t_s - T[s+1]h) + T[s+m+1])modq$

预处理时间:$\Theta (m)$

最坏情况:$O((n-m+1)m)$

平均情况:$O(m+n)$

3、有限自动机

预处理时间:$O(m |\sum|)$ $|\sum|$为一个元素可选的输入总数

运行时间:$\Theta( n)$

4、KMP算法

预处理时间:$O(m)$

运行时间:$\Theta(n)$

前缀函数:$\pi[q]$是能构成$P_q$真后缀的最长前缀长度

十一、主定理

对递归式$T(n) = aT(\frac{n}{b}) + f(n)$:

若$f(n) = O(n^{log_ba-\epsilon})$ ,则$T(n) = \Theta (n^{log_ba})$

若$f(n) = \Theta (n^{log_ba})$,则$T(n) = \Theta (n^{log_ba}logn)$

若$f(n) = \Omega(n^{log_ba + \epsilon})$ 且$af(\frac{n}{b}) \leq cf(n)$(c < 1, n足够大),则$T(n) = \Omega(f(n))$

数据结构

1、红黑树

性质:一棵有n个内部节点的红黑树的高度至多为$2log(n+1)$

LEFT-ROTATE、RIGHT-ROTATE:$O(1)$

RB-INSERT、RB-DELETE:$O(logn)$

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:$O(logn) $

INSERT、DELETE:$O(logn )$

3、区间树

INTERVAL-SEARCH:$O(logn )$

4、二项树

二项树$Bk$由两棵二项树$B{k-1}$构成,一棵树的根是另一棵树的根的最左孩子

性质:

①、共有$2^k$个结点

②、高度为$k$

③、在深度$i$处恰好有$C ^i _k$个结点

④、根的度数为$k$,大于其他任何结点的度数,根的孩子从左到右依次为$B{k-1},B{k-2},...,B_0$的根

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

5、二项堆

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

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

②、对于任意非负整数$k$,在二项堆中最多有一颗二项树的根结点的度数为$k$,故在一个有$n$个结点的二项堆中,最多包含$\lfloor logn \rfloor +1$棵二项树

INSERT、MINIMUM、UNION:$\Omega(logn)$

EXTRACT-MIN、DECREASE-KEY、DELETE:$\Theta(logn)$

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

UNION操作的情况:

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

不需要连接,直接跳过

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

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

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

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

INSERT:

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

EXTRACT-MIN:

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

DECREASE-KEY:

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

DELETE:

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

调用EXTRACT-MIN

6、不相交集合

$S_i \bigwedge S_j = \emptyset$

可用于求强连通分量

使用链表表示:

MAKE-SET:$O( 1 )$

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

未经过任何优化:$O(n^2)$

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

使用森林表示:

按秩合并、路径压缩

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

单独使用按秩合并:$O(mlogn)$

单独使用路径压缩:$\Theta(n + f \cdot (1 + log _{2+\frac{f}{n}} n))$ $f$为FIND-SET操作总数

同时使用按秩合并和路径压缩:$O(m \cdot \alpha(n))$

特殊公式

1.$\lim_{n\to\infty}(1+\frac{x}{n})^n = e^x$

2.$\frac{x}{1+x}\leq ln(1+x) \leq x$

3.$log(n!) = \Theta (nlogn)$

4.$\sum ^n _{k=0} k^2= \frac{n(n+1)(2n+1)}{6}$

smartdub

这个人太懒什么东西都没留下

文章评论(0)

你必须 登录 才能发表评论