算法复习
1 插入排序

思想:

通过构建有序序列,对于未排列的数据,在已经排好序的数列中从后向前进行扫描,找到相应的位置并插入,插入排序在实现上,在从后向前扫描的过程中,需要反复把已经排序元素逐步向后移动

•Sorting problem:

  • Input: A sequence of n numbers a~1~, a~2~, …, a~n~
  • Output: A permutation (reordering) a’~1~, a’~2~, …, a’~n~ of the input sequence such that

a’~1~<=a’~2~ <= … <=a’~n~

•An instance of the sorting problem

–Input: 8 2 4 9 3 6

–Output: 2 3 4 6 8 9

•Notation:

–Sorting is a fundamental operation in CS

–A large number of good sorting algorithms have been D&R

算法描述
算法描述
伪代码
伪代码

具体python代码实现参考博客文章

时间复杂度的问题:

Worst-case: (usually)

–T(n) = maximum time of algorithm on any input of size n.

T(n)=maxI {T(n,I)}

–Time Complexity (Default )

Average-case: (sometimes)

–T(n) = expected time of algorithm over all inputs of size n.

–Need assumption of statistical distribution of inputs.

?

Best-case: (bogus虚假)

–Cheat with a slow algorithm that works fast on some input.

?
2 时间复杂度描述

$$
\Theta(n) \quad既有上界又有下界
$$

Engineering:

–Drop low-order terms; ignore leading constants.

example:
$$
3n^3 + 90n^2 –5n + 6046 = Θ(n3)
$$

$$
O(n)\quad 只有上界
$$

$$
Ω(n)\quad 只有下界
$$


3 分治思想

recursively 递归

subproblems 子问题

median 中位数

  • Merge sort

    •Problem:

    –Input: A[1,n]

    –Output: A[1,n] in sorted order

    •Divide-and-conquer paradigm

    Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each.

    Conquer: Sort the two subsequences recursively using merge sort.

    Combine: Merge the two sorted subsequences to produce the sorted answer.

1558947965911

1558947965911

  • Recursion tree递归树解决递归式问题

    例子
    $$
    Solve \quad T(n)=2T(n)+cn,\quad where c>0\quad is \quad constant
    $$

1558947965911
1558947965911
4 快速排序

思想:

​ 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

前言介绍

1558947965911
1558947965911
1
2
3
4
5
6
7
8
9
PARTITION (A,  p,  r)  # A是待排序数组
x ← A[r]
i ← p-1
FOR j ← p TO r-1
IF A[ j] ≤ x
THEN i ← i + 1
exchange A[i] ↔ A[ j]
exchange A[i+1] ↔ A[r]
RETURN i+1
1558947965911
1558947965911

the run time drops from Ω(n log n) to Ω(n^2^)

提高快速排序的方法

Median-of-three(三平均分区法)

关于这一改进的最简单的描述大概是这样的:与一般的快速排序方法不同,它并不是选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说,主要有两点优势:
  (1) 首先,它使得最坏情况发生的几率减小了。
  (2) 其次,未改进的快速排序算法为了防止比较时数组越界,在最后要设置一个哨点。

提高的方法可以说是这样的:

首先对整个列表的元素进行选取,第一个位置first,中间位置middle,最后一个位置的元素last,然后以这三个数的中位数(以middle)为基准,对列表剩余的元素进行比较采用插入排序进行sort,这样一来,左边的元素都是小于middle的元素,右边的元素都是大于middle的元素;

然后在对middle左边的元素进行上述操作,对右边进行上述操作,直至待排的元素个数为1。

至此,整个排序也就完成了;

5 Dynamic programming 动态规划

Rod cutting

Given a rod of length n inches and a table of prices pi for i = 1,2,3,…,n, determine the maximum revenue(收入) r(n) obtainable by cutting up the rod and
selling the pieces.

给定长度为n英寸的杆和i = 1,2,3,…,n的价格表p~i~,确定通过切割杆和杆可获得的最大收入r(n)来销售。

问题描述

问题描述
问题描述

Nothing

拓展阅读

6 贪心算法

是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法;比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法贪心算法在有最优子结构的问题中尤为有效;

通常情况下,贪心算法采用自顶向下的设计,因为不需要作出过多的选择求解所有子问题;

找零钱问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Change-Making Problem

Finding the number of ways of making changes
for a particular amount of cents, n, using a given
set of denominations C={c1…cd} (e.g, the US
coin system: {1, 5, 10, 25, 50, 100})

– An example: n = 4,C = {1,2,3}, solutions: {1,1,1,1},
{1,1,2},{2,2},{1,3}.
 Minimizing the number of coins returned for a
particular quantity of change (available coins
{1, 5, 10, 25})
30 Cents (solution: 25 + 5, two coins)
67 Cents ?
17 cents given denominations = {1, 2, 3, 4}?
算法
算法

活动选择

有一个需要使用每个资源的N个活动组成的集合S ={a1, a2, ···, an},资源每次只能由一个活动使用。每个活动都有一个开始时间和si和结束时间fi,且0=<si<=fi<∞,一旦被选择后,活动ai就只占据时间[si, fi],如果[si,fi]和[sj,fi]不重叠,则称ai、aj兼容。

1
2
3
4
5
6
7
8
9
10
# 活动选取的贪心算法
Greedy-Activity-Selector(s, f)
n = s.length
A = {a1}
k = 1
for m = 2 to n
if s[m] >= f[k] # 时间的比较
A = A U {am}
k = m
return A

最优子结构

如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。贪心算法要做的就是逐步求取局部最优解,以致达到全局整体最优。

赫夫曼编码

讨论赫夫曼编码问题,赫夫曼编码的思想就是变长编码;也就是说让字符表中出现概率高的字符的编码长度尽可能的小,而出现概率高的字符的编码相对较长;然后遵循前缀码的要求,即是任意一个编码都不是其他编码的前缀,便于解码。

作者:JeffCoding
原文:https://blog.csdn.net/jeffleo/article/details/53557143

赫夫曼编码是一种广泛用于数据压缩的问题,该算法的主要优势在于节约了存储和传输成本。
举一个例子:
假设要传输的数据为

Figure 0
Figure 0

那么传输成本就是:
453 + 30 3 + 29 3 + 10 3 + 8 3 + 5 3 = 381个字符

我们可以使用赫夫曼编码思想来解决
先合并最小频率的2个字符对应的子树,计算合并后的子树的频率;
重新排序各个子树;
重复步骤1
重复步骤2
对二叉树中的边赋予0、1,得到各字符的变长编码。
对于上举的例子而言就是:
EF最小,首先构造EF的生成树,重新排序

Figure 1
Figure 1

构造EF 和 D的生成树,重新排序

Figure 2
Figure 2

构造EFD 和 C 的生成树, 重新排序

Figure 3
Figure 3

构造EFDC 和 B 的生成树,重新排序

Figure 4
Figure 4

构造EFDCB 和 A 的生成树,重新排序

Figure 5
Figure 5

赫夫曼编码后的二进制数据为:

Figure 6
Figure 6

可以看见,利用赫夫曼思想设计之后,频率高的字符,二进制码短了,频率低的字符,二进制码长了,这样就有效得减少了总得二进制码数。

那么传输成本就是:
451 + 30 2 + 29 3 + 10 4 + 8 5 + 5 5 = 292个字符,节约了23%的成本!

End

7 最大流问题

流网络

digraph G=(V,E)

weights, called capacities on edge c(u,v)边缘容量

two distinct vertices (不同的顶点)

source, ‘s’; sink ‘t’

流网络
流网络

The value of a flow is the net flow out of the source:
$$
\sum p(s,v)-\sum p(v,s)
$$
流网络流出的值是净网络

网络的值
网络的值
The value of this flow is 1-0+2=3

残存网络

假定有一个流网络G=(V,E),其源点为s,汇点为t,f为G中的一个流。对即诶点对u,v,定义残存容量(residual capacity)

img
img
,有:

img
img

残存网络可能包含图G中不存在的边,残存网络中的反向边允许算法将已经发送出来的流量发送回去。一个残存网络示例图如下:

Rabin-KarpRabin-Karp

img
img

图a是一个流网络,b是a对应的残存网络,注意每条边上的值,残存网络中针对每条正向边计算出该条边在存在流的情况下的剩余容量,并画出一条反向边,反向边的容量即是发出流的大小,方便将发出的流运输回发送地,并将权重为0的边省略。

8 字符串匹配

Rabin-Karp算法

在实际应用中,Rabin-Karp算法的预处理时间为O(m),并且在最坏的情况下的时间复杂度为O((n-m+1)m),相对于朴素字符串,它的运行时是比较好的。

整个算法思想介绍如下:

数学中有霍纳法则,我们运用霍纳法则在O(m)内计算p:

p=P[m]+10(P[m-1]+10(P[m-2]+…+10(P[2]+10P1)…)))

霍纳法则的解释如下:

这里写图片描述

运用霍纳法则,类似的我们也可以根据T[s+1…s+m]计算出t.

但为了节约时间,我们可以利用一下方法在常数时间内根据ts,计算出ts+1.具体过程如下图解:

如图所示,ts=31415,ts+1=14152,则

ts+1=(ts-(T[s+1]=3)10^(m=4))10+(T[s+m+1]=2)

注:(ts-(T[s+1]=3)*10^(m=4))=31415-30000=1415

即 ts+1=10(ts-10^(m-1)T[s+1])+T[s+m+1]

在计算过程中,可能会出现p与t的值过大,可以取模运算

确定优先状态自动机

有限自动状态机
有限自动状态机

上面这个图描述的就叫一个有限状态自动机,图中两个圆圈,也叫节点,用于表示状态,从图中可以看成,它有两个状态,分别叫0和1. 从每个节点出发,都会有若干条边,当处于某个状态时,如果输入的字符跟该节点出发的某条边的内容一样,那么就会引起状态的转换。例如,如果当前状态处于0,输入是字符a,那么状态机就会从状态0进入状态1.如果当前状态是1,输入字符是b或a,那么,状态机就会从状态1进入状态0.如果当前所处的状态,没有出去的边可以应对输入的字符,那么状态机便会进入到错误状态。例如,如果当前处于状态0,输入字符是c,那么状态机就会出错,因为从状态0开始,没有哪条边对应的字符是c。

状态机会有一个初始节点,和一个接收节点,以上图为例,我们可以设置初始节点为0,接收节点为1,当进行一系列的输入,使得状态机的状态不断变化,只要最后一个输入使得状态机处于接收节点,那么就表明当前输入可以被状态机接收。例如对应字符串”abaaa”, 从初始节点0开始,状态机根据该字符串的输入所形成的状态变化序列为:{0,1,0,1,0,1}。由于最后状态机处于状态1,所以该字符串可以被状态机接收。如果输入的字符串是:abbaa, 那么状态机的变化序列为:{0,1,0,0,1,0}, 由于最后状态机处于非接收状态,因此这个字符串被状态机拒绝。

在程序中,使用二维表表示一个状态机:

输入 a b
状态0 1 0
状态1 0 0

接下来我们看看一个文本的匹配流程,假定要查找的字符串为P=”ababaca”, 被查找的文本为T=”abababacaba”. 一次读入T的一个字符,用S表示当前读入的T的字符,一开始读入一个字符,于是S=a.然后看看,从P开始,连续几个字符所构成的字符串可以成为S的后缀,由于当前S只有一个字符a,于是从P开始,连续1个字符所形成的字符串”a”,可以作为S的后缀。把这个字符串的长度记为k,于是此时k 等于1. 继续从T中读入字符,于是S=”ab”, 此时,从P开始,连续两个字符所构成的字符串”ab”可以作为S的后缀,于是k = 2.反复这么操作,于是便有以下序列:

1
2
3
4
5
6
7
8
9
10
11
S=a, k = 1, P[1] 是S的后缀
S=ab, k = 2, P[1,2] 是S的后缀
S=aba, k = 3, P[1,2,3]是S的后缀
S=abab, k= 4, P[1,2,3,4]是S的后缀
S=ababa, k = 5, P[1,2,3,4,5]是S的后缀
S=ababab, k = 4, P[1,2,3,4]是S的后缀
S=abababa, k = 5, P[1,2,3,4,5]是S的后缀
S=abababac, k = 6, P[1,2,3,4,5,6]是S的后缀
S=abababaca, k = 7, P[1,2,3,4,5,6,7]是S的后缀
S=abababacab, k =2, P[1,2] 是S的后缀
S=abababacaba, k = 3, P[1,2,3] 是S的后缀。

从上述过程中,我们可以看到第九步的时候字符串P已经成为了S的后缀,此时的S是文本T的前缀,因此可以说明在字符串T中找到了模式串P。

如果问题变化,构造一个方法,使得一次运行便能知道从P开始,连续读取几个字符能使得这几个字符构成的字符串是S的后缀。这个方法,就需要上面我们提到的有限状态自动机了

用于字符串匹配的自动机

假定字符串P和文本T只由a,b两个字符组成,也就是字符集为∑={a,b,c}, P含有m个字母,于是,我们要构造的自动机就含有m个状态节点。假设我们当前处于状态节点q, 那么当下一个输入字符是a和b时,从当前节点q该跳转到哪一个节点呢? 如果用$P_q$来表示长度为q的P的前缀,以q=4, p=”ababaca”, $P_q$ =”abab”, 那么当处于状态4, 当输入为a时,我们构造字符串 S = $P_q$ + ‘a’ = “ababa”, 然后看看字符串P从第一个字符开始,连续几个字符所构成的字符串可以成为S的后缀,就当前S为例,从第一个字符开始,连续5个字符,也就是P[1,2,3,4,5]可以作为S的后缀,于是,我们就有,当状态机处于节点4,输入为a时,跳转的下个状态就是5. 同理,当处于状态q=4,输入为字符b时,S = $P_q$ + ‘b’ = “ababb”,此时从P开始,连续读取0个字符才能形成S的后缀,于是当状态机处于状态4,如果读入字符是b, 那么跳转的下一个状态是0,同理,如果输入字符是c, 那么S = $P_q$ + ‘c’ = “ababc”, 此时从P开始,连续读取0个字符所形成的空字符串才能作为S的后缀,于是当状态机处于状态节点4,输入字符为c时,跳转到节点0. 如果q从0开始,一直到m,反复运用刚才提到的步骤,便会产生下面这个跳转表:

输入 a b c
状态0 1 0 0
状态1 1 2 0
状态2 3 0 0
状态3 1 4 0
状态4 5 0 0
状态5 1 4 0
状态6 7 0 0
状态7 1 2 0

状态I就是上面介绍的K的值,也就是P中形成的字符串可以构成S的后缀的长度;

KMP算法

算法流程

  • 假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

    • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
    • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。
      • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文中详细阐述),即移动的实际位数为:j - next[j],且此值大于等于1。

    next数组的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀,例如如果next[j]=k,代表j之前的字符串中有最大长度为k的相同前缀后缀。

此也意味着在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j 之前的某个字符,而不是跳到开头,且具体跳过了k 个字符;

步骤

寻找前缀后缀的最大公共元素长度

  • 对于P = p0 p1 …pj-1 pj,寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk = pj- k pj-k+1…pj-1 pj,那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子,如果给定的模式串为“abab”,那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示:

img

比如对于字符串aba来说,它有长度为1的相同前缀后缀a;而对于字符串abab来说,它有长度为2的相同前缀后缀ab(相同前缀后缀的长度为k + 1,k+1 = 2)。

求next数组

  • next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第①步骤中求得的值整体右移一位,然后初值赋为-1,如下表格所示

    img

比如对于aba来说,第3个字符a之前的字符串ab中有长度为0的相同前缀后缀,所以第3个字符a对应的next值为0;而对于abab来说,第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a,所以第4个字符b对应的next值为1(相同前缀后缀的长度为k,k = 1)

补充

寻找最长前缀后缀

如果给定的模式串是:“ABCDABD”,从左至右遍历整个模式串,其各个子串的前缀后缀分别如下表格所示:

img
img

也就是说,原模式串子串对应的各个前缀后缀的公共元素的最大长度表为(下简称《最大长度表》):

img
img

而且,根据这个表可以得出下述结论

失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
上文利用这个表和结论进行匹配时,我们发现,当匹配到一个字符失配时,其实没必要考虑当前失配的字符,更何况我们每次失配时,都是看的失配字符的上一位字符对应的最大长度值。如此,便引出了next 数组。

给定字符串“ABCDABD”,可求得它的next 数组如下:

img
img

把next 数组跟之前求得的最大长度表对比后,不难发现,next 数组相当于“最大长度值” 整体向右移动一位,然后初始值赋为-1。意识到了这一点,你会惊呼原来next 数组的求解竟然如此简单:就是找最大对称长度的前缀后缀,然后整体右移一位,初值赋为-1(当然,你也可以直接计算某个字符对应的next值,就是看这个字符之前的字符串中有多大长度的相同前缀后缀)。

kmp算法的复杂度是O(n+m)

参考文章

https://blog.csdn.net/tyler_download/article/details/52549315

https://blog.csdn.net/v_july_v/article/details/7041827#t5