算法导论总结

算法基础期末总结

算法分析

一、排序算法

1、插入排序：

$\Theta (n^2)$ 当数组逆序时发生

$\Theta(n)$ 当数组顺序时发生

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

稳定

$\Theta (nlogn)$

$T(n) = 2T(\frac{n}{2}) + \Theta(n)$

稳定

$O (nlogn)$

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

$O(logn)$

$O(n)$

$O(logn)$

$O(1)$

$O(logn)$ 时间内完成

不稳定

4、快速排序：

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

$O(nlogn)$ 当每次划分都将数组均分时产生

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

$O(nlogn)$

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

$\Theta(k+n)$

稳定

$k=\Theta(n)$ $\Theta ( n)$

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

$\Theta (d(n+k) )$

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

$\Theta((\frac{d}{r})(n+2^r))$

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

稳定

$O(n)$

假设数据服从均匀分布

$O( n)$

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

$\Omega(nlogn)$ 次比较

$\Omega(nlogn)$

二、递归算法

1、求Fibonacci数

$\Omega ((\frac{3}{2})^n)$

$\Theta (n)$

$O (logn)$

$O(n!)$

$\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)$

元素必须互异

四、动态规划算法

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

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

最优子结构：原问题的最优解包含子问题的最优解，子问题间的解无关

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

$O (n+e)$

$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$

$O (n)$

$b[j] = max\{b[j-1]+a_j,0\}$

$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背包问题不满足贪心选择性质，小数背包问题满足

$O (nlogn)$

$\Theta (n )$

$O (nlogn)$

$\Theta(n)$

$O (nlogn)$

$\Theta(n)$

$O (n)$ (n为面额种类)

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

六、回溯算法

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

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

优化方法：

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

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

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

循环：

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

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

循环：

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

需要有一个初始的解

1、n皇后问题

子集树框架

2、排列生成问题

排列树框架

3、TSP问题

排列树框架

4、0-1背包问题

子集树框架

七、摊还分析

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

1、聚合分析

$T(n)/n$

2、记账/核算法

给每个操作赋予一个代价

3、势能法

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

$\Phi$ $\Phi(D_n) \geq \Phi(D_0)$ $\hat{c}$ $c$

$\hat{c_1} = c_i + \Phi(D_i) - \Phi(D_{i-1})$

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

八、图论算法

$O( V+E )$

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

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

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

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

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

$\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、最小生成树算法

$O( ElogV)$

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

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

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

$O( ElogV)$

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

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

$O(VlogV)$

$v.key$ $O(ElogV)$

$O(V)$

三者相加即是总时间

$O(E + VlogV)$

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

3、单源最短路径算法

$O(VE)$

$|V|-1$ 次

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

$\Theta(V+E)$

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

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

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

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

$O (ElogV)$

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

$O(VlogV )$

$O(Elog V)$

$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} = ...$

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

$\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}$

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

$O (VElogV)$

$s$ $s$ $s$ $h(v)$

$w$ $\hat{w}(u,v) = w(u,v) + h(u) - h(v)$

$V$ 次Dijkstra算法

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

$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$

$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$ 不是素数

$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}$

十、字符串匹配算法

$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)$ $T(n) = \Omega(f(n))$

数据结构

1、红黑树

$2log(n+1)$

$O(1)$

$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、动态顺序统计树

$O(logn)$

$O(logn )$

3、区间树

$O(logn )$

4、二项树

$B_k$ $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$ 棵二项树

$\Omega(logn)$

$\Theta(logn)$

$O( 1)$ $O(log n)$ $O( n )$ $O(log n)$ )

UNION操作的情况：

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

不需要连接，直接跳过

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

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

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

$head[H]$

INSERT：

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

EXTRACT-MIN：

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

DECREASE-KEY：

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

DELETE：

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

调用EXTRACT-MIN

6、不相交集合

$S_i \bigwedge S_j = \emptyset$

可用于求强连通分量

使用链表表示：

$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))$

特殊公式

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

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

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

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

Welcome!

Yun Peng

Chinese Name

Major

City

Age

Email

Research Interest

Software Engineering

Artificial Intelligence

算法导论总结

算法基础期末总结

算法分析

一、排序算法

二、递归算法

三、选择算法

四、动态规划算法

五、贪心算法

六、回溯算法

七、摊还分析

八、图论算法

九、数论算法

十、字符串匹配算法

十一、主定理

数据结构

特殊公式