大三算法设计与分析笔记总结与知识点整理

笔记总结

第一章 算法引论

1.1 算法与程序

  • 算法定义:解决问题的方法或过程
  • 算法的性质:
    • (1)输入:有零个或多个外部量作为算法的输入
    • (2)输出:算法产生至少一个量作为输出
    • (3)确定性:组成算法的每条指令是清晰的,无歧义的
    • (4)有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限
    • 有时还会加入通用性或可行性
  • 程序的定义:是算法用某种程序设计语言的具体实现。
  • 程序与算法的区别:程序可以不满足算法的第四点性质即有限性。例如操作系统,是在无限循环中执行的程序。

1.2 表达算法的抽象机制

  • 为了将顶层算法与底层算法隔开,使二者在设计时不互相牵制,互相影响,必须对二者的接口进行抽象。让底层只通过接口为顶层服务,顶层也只通过接口调用底层运算。这个接口就是抽象数据类型(ADT)。

1.3 描述算法

  • 有多种方式,如:自然语言方式,表格方式,高级程序语言方式等…

1.4 算法复杂性分析

  • 算法分析的目的:分析算法占用计算机资源的情况,对算法做出比较和评价,设计出更好的算法
  • 算法的复杂性是算法运行时所需的计算机资源的量,需要时间资源的量称为时间复杂性,需要空间资源的量称为空间复杂性
  • C=F(N,I,A),用N,I,A分别表示算法要解的问题的规模,算法的输入和算法本身,F表示是上诉N,I,A的确定的三元函数,C表示复杂性
  • 一般只考虑3种情况下的时间复杂性,即最坏情况,最好情况,平均情况
  • 实践表明,可操作性最好且最有实际价值的是最坏情况下的时间复杂性
  • 复杂性渐进性态:
    1
    对于T(N),如果存在~T(N),使得当N→∞时有(T(N)-~T(N))/T(N)→0,那么就说~T(N)是T(N)当N→∞时的渐进性态。
  • 如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界,且g(N)是它的一个上界,记为f(N)=O(g(N))。这时还说f(N)的阶不高于g(N)的阶。
  • 对于符号O,有如下运算规则:
    • O(f)+O(g)=O(max(f,g))
    • O(f)+O(g)=O(f+g)
    • O(f)O(g)=O(fg)
    • 如果g(N)=O(f(N)),则O(f)+O(g)=O(f)
    • O(Cf(N))=O(f(N)),其中C是一个正的常数
    • f=O(f)

第二章 递归与分治策略

2.1 递归的概念

  • 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数

  • 递归函数的两个要素:边界条件递归方程

  • 阶乘函数:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include<iostream>
    using namespace std;

    int factorial(int n){
    if(n==0) return 1;
    else{
    return n*factorial(n-1);
    }
    }
  • Fibonacci数列:

    1
    2
    3
    4
    5
    6
    7
    #include<iostream>
    using namespace std;

    int fibonacci(int n){
    if(n<=1) return 1;
    else return fibonacci(n-1)+fibonacci(n-2);
    }
  • hanoi塔:

    1
    2
    3
    4
    5
    6
    def hanoi(n,a,b,c):
    #将a上的n个圆盘经过c移动到b
    if(n>0):
    hanoi(n-1,a,c,b)
    move(a,b)
    hanoi(n-1,c,b,a)
  • 递归算法的优点:结构清晰,可读性强,容易用数学归纳法来证明算法的正确性

  • 递归算法的缺点:运行效率低,无论是耗费的计算时间还是占用的存储空间都比非递归算法多。

  • 消除递归的方法:①采用一个用户定义的栈来模拟系统的递归调用工作栈,从而达到将递归算法改为非递归算法的目的②用递推来实现递归函数

2.2 分治法的基本思想

  • 分治法的基本思想:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
  • 分治法的适用条件:
    • ①该问题的规模缩小到一定程度容易解决。
    • ②该问题可以分解为若干个规模较小的相同问题。即该问题具有最优子结构性质。
    • ③该问题分解出的子问题的解可以合并为该问题的解。
    • ④子问题间不包含公共的子问题(各子问题相互独立)
  • 分治法的步骤:
    • 划分
    • 解决
    • 合并

2.3 二分搜索技术

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binarySearch(a,x):
#a是数组,x是要搜索的数
a=sorted(a)
#a要求有序(从小到大)
n=len(a)
left,right=0,n-1
while(left<=right):
middle=(left+right)//2
if(x==a[middle]):
return middle
elif(x>a[middle]):
left=middle+1
else:
right=middle-1
#未找到
return -1
  • 最坏情况下,时间复杂度是O(logn)

2.4 大整数乘法

  • 设x和y都是n位的二进制整数,现在要计算他们的乘积xy。如果直接相乘,需要O(n^2)步,而其分治法是:将n位二进制整数X和Y都分为2段,每段的长为n/2位:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    X=[A][B],Y=[C][D],其中X,Y有n位;A,B,C,D均有n/2位
    由此可以得到:
    X=A*2^(n/2)+B , Y=C*2^(n/2)+D

    XY=(A*2^(n/2)+B)(C*2^(n/2)+D)
    =A*C*2^n+(A*D+C*B)*2^(n/2)+B*D
    =A*C*2^n+((A-B)(D-C)+A*C+B*D)*2^(n/2)+B*D

    最后一个式子看起来似乎复杂了,但是它仅需做3次n/2位整数的乘法,6次加减法和2次移位

2.5 Strassen矩阵乘法

  • 对于方阵(n*n)A,B,C,有C=A*B,将它们都分块成4个大小相等的子矩阵,每个子矩阵都是(n/2)*(n/2)的方阵
  • MhaKxS.png

2.7 合并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def merge(arr,left,mid,right):
#left,right为需要合并的数组范围
#mid为中间下标,左边比中值小,右边比中值大
i=left
j=mid+1
#复制一个临时数组
aux=arr[:]
for k in range(left,right+1):
#如果左指针超过mid,即右边还有剩余
if(i>mid):
arr[k]=aux[j]
j=j+1
#如果右指针超过right,即左边还有剩余
elif(j>right):
arr[k]=aux[i]
i=i+1
#如果左边小,则左边合并
elif(aux[i]<aux[j]):
arr[k]=aux[i]
i=i+1
#如果右边小
else:
arr[k]=aux[j]
j=j+1


def mergeSort(arr,left,right):
#如果已经遍历完
if(left>=right):
return ;
#取中值,拆成左右两边
mid=(left+right)//2
#对左半边进行归并排序
mergeSort(arr,left,mid)
#对右半边进行归并排序
mergeSort(arr,mid+1,right)
#合并算法
merge(arr,left,mid,right)
  • 最坏情况下的时间复杂度为O(nlogn)

2.8 快速排序

  • 步骤:分解,递归求解,合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    def quicksort(arr,low,high):
    if low<high :
    index=getindex(arr,low,high)
    quicksort(arr,low,index-1)
    quicksort(arr,index+1,high)

    #快速排序算法核心
    #作用:将小于基准值的数放在其左边,大于在右边
    def getindex(arr,low,high):
    #默认第一个数字为标准值
    temp=arr[low]
    #当未遍历完,即左右指针未相遇
    while(low<high):
    #如果右边大于标准值,右指针左移
    while((low<high)and(arr[high]>=temp)):
    high=high-1
    #此时右指针对应值小于标准值,将其复制给左指针位置
    arr[low]=arr[high]
    #当左边小于标准值,左指针右移
    while((low<high)and(arr[low]<=temp)):
    low=low+1
    #此时左指针对应值大于标准值,将其复制给右指针位置
    arr[high]=arr[low]
    #将标准值赋值给左右指针相遇的位置
    arr[low]=temp
    #此时low左边全部小于等于arr[low],low右边全部大于等于arr[low]
    return low
  • 快排平均情况下的时间复杂度是O(nlogn),最坏情况下的时间复杂度是O(n^2)

2.9 线性时间选择

  • 找出一组数中,第X大(小)的数
  • 采用了随机划分算法

2.10 最近点对问题

  • 时间复杂度分析O(nlogn)

第三章 动态规划

  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解,但与分治法不同的是,适用于动态规划法求解的问题,经分解得到的子问题往往不是相互独立的。
  • 动态规划算法的步骤:
    • ①找出最优解的性质,并刻画其结构特征
    • ②递归地定义最优值
    • ③以自底向上的方式计算出最优值
    • ④根据计算最优值时得到的信息,构造最优解
  • 动态规划算法的两个基本要素:最优子结构重叠子问题
    • 最优子结构性质:问题的最优解包含子问题的最优解
    • 重叠子问题:在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次
    • 无后效性:一个问题被划分阶段后,阶段I中的状态只能由I+1中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系
  • 动态规划算法有一个变形方法——备忘录方法,这种方法不同于动态规划算法“自底向上”的填充方向,而是“自顶向下”的递归方向,为每一个解过的子问题建立一个记录项(备忘录)以备需要时查看,也可以避免相同子问题的重复求解

3.1 矩阵连乘问题

  • MIK2dK.png
  • m(i,j)是指从A[i]到A[j](1≤i≤j≤n)的最少数乘次数
  • 矩阵可乘条件:A的列数等于B的行数,若A是一个p×q矩阵,B是一个q×r矩阵,则AB总共需要pqr次数乘。

3.3 最长公共子序列

  • MI179S.png
    建立递归关系:
  • MI399U.png

3.4 凸多边形最优三角剖分

  • 和矩阵连乘相似

3.9 0-1背包问题

  • MIGH1O.png
  • 其中m(i,j)是指背包容量为j,可选择物品为i,i+1,···,n时0-1背包问题的最优值

3.10 最优二叉搜索树

  • 二叉搜索树:存储于每个结点中的元素x大于其左子树中任一结点所存储的元素,小于其右子树中任一结点所存储的元素

第四章 贪心算法

  • 贪心算法:总是做出在当前看来最好的选择,也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择。
  • 使用贪心算法需满足:
    • 贪心选择性:指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到
    • 最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质
  • 贪心算法适合的问题:有n个输入,其解就由这n个输入满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。显然可行解一般来说是不唯一的。那些使目标函数取极值的可行解,成为最优解。
  • 贪心算法是一种分级处理方法,它首先根据题意,选取一种度量标准,然后按这种度量标准对这n个的输入排序,并按序依次输入,如果不满足条件,则不把此输入加到解当中。
  • 贪心算法设计求解的核心问题:选择能产生问题最优解的最优量度标准。
  • 贪心算法正确性的证明:
    • ①证明算法所求的问题具有优化子结构
    • ②证明算法所求解的问题具有贪心选择性
    • ③算法按照②种的贪心选择性进行局部最优选择

4.2 活动安排问题

  • 为了选择最多的相容活动,每次选择fi最小的活动,使能够选择更多的活动
  • 度量标准:按照结束时间的非减序排列
  • 如果有序,则O(n),如果无序,O(nlogn)

4.3 最优装载问题

  • O(nlogn)

    4.4 哈夫曼编码

  • 循环地选择具有最低频率的两个结点,生成一棵子树,直至形成树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#构建二叉树类型
class BinaryTree:
def __init__(self,data,left,right,code):
self.data=data
self.left=left
self.right=right
self.code=code

def getdata(self):
return self.data

#哈夫曼树
class Huffman:
def __init__(self,tree,ww):
self.tree=tree
self.w=ww

def getweight(self):
return self.w

def huffmanTree(f):
#f是出现频率权值字典
H=[]
n=len(f)
#根据value对键进行从大到小排序
for i in sorted(f,key=f.__getitem__,reverse=True):
tree = BinaryTree(i,0,0,"")
w = Huffman(tree,f[i])
H.append(w)

for i in range(1,n):
#取出最后两位
x=H.pop()
y=H.pop()
#取权重小的做左孩子,大的是右孩子
t=BinaryTree(i,x.tree if x.w<y.w else y.tree,y.tree if y.w>x.w else x.tree,"")
h=Huffman(t,x.w+y.w)
H.append(h)
#根据权重从大到小排序
H=sorted(H,key=lambda x:x.w,reverse=True)

return H.pop()

4.5 单源最短路径

  • 设置顶点集合S并不断地作贪心选择来扩充这个集合,一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知,初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其他顶点之间的最短路径长度

4.6 最小生成树

  • 设G =(V,E)是无向连通带权图,即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树

  • 最小生成树性质(MST性质):设G=(V,E)是连通带权图,U是V的真子集。如果(u,v)∈E,且u∈U,v∈V-U,且在所有这样的边中,(u,v)的权为c[u][v]最小,那么一定存在G的一颗最小生成树,它以(u,v)为其中一条边

  • Prim算法:

    • 首先置S={1},然后,只要S是V的真子集,就作如下的贪心选择:
    • 选取满足条件i∈S,j∈V-S,且c[i][j]最小的边,将顶点j添加到S中。这个过程一直进行到S=V时为止。
    • 在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
      MIjycj.png
  • Kruskal算法:

    • 首先,将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。
    • 然后,从第一条边开始,依边权递增的顺序查看每一条边,并按下述方法连接2个不同的连通分支:
      • 当查看到第k条边(v,w)时,如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时,就用边(v,w)将T1和T2连接成一个连通分支,然后继续查看第k+1条边;
      • 如果端点v和w在当前的同一个连通分支中,就直接再查看第k+1条边。
      • 这个过程一直进行到只剩下一个连通分支时为止。
        MIvIdP.png

第五章 回溯法

  • 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该节点为根的子树的搜索,逐层向其祖先结点回溯,否则,进入该子树,继续按深度优先策略搜索

  • 具有剪枝函数的深度优先生成法

  • 扩展结点:正在产生儿子的结点称为扩展结点

  • 活结点:自身已生成但其儿子还没有全部生成的结点

  • 回溯法的步骤:

    • (1)针对所给问题,定义问题的解空间;
    • (2)确定易于搜索的解空间结构;
    • (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索
  • 子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。通常有2n个叶子节点,其节点总个数为2n+1-1。如:0-1背包问题

  • 排列树:当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。排列树通常有n!个叶子节点。如:旅行售货员问题。

  • 回溯算法的效率在很大程度上依赖于以下因素:

    • (1)产生x[k]的时间;
    • (2)满足显约束的x[k]值的个数;
    • (3)计算约束函数constraint的时间;
    • (4)计算上界函数bound的时间;
    • (5)满足约束函数和上界函数约束的所有x[k]的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此,在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。

5.2 装载问题

  • 如果一个给定装载问题有解,则采用下面的策略可得到最优装载方案。
    • (1)首先将第一艘轮船尽可能装满;
    • (2)将剩余的集装箱装上第二艘轮船。
  • 解空间:子集树
  • 可行性约束函数(选择当前元素):
  • 上界函数(不选择当前元素):当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw

5.6 0-1背包问题

  • n=3, C=30, w={16, 15, 15}, v={45, 25, 25}
  • Mo9ygU.png

第六章 分支限界法

  • 分支限界法以广度优先或以最小耗费(最大效益)优先的方式搜索解空间树。其搜索策略是:在扩展结点处,先生成其所有儿子结点,然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一格活结点处,计算一个函数值(限界),并根据函数值,从当前活结点表中,选择一个最有利的结点作为扩展结点,使搜索朝着解空间上最优解的分支推进,以便尽快找出一个最优解。
  • 常见两种分支限界法:①队列式(FIFO/LIFO)分支限界法②优先队列式分支限界法
  • 与回溯法对比:
    • (1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。
    • (2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
      MoPuFI.png

6.5 0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Q:
def __init__(self,_id,qq):
self.id=_id
self.d=qq

class BBnode:
def __init__(self,par,ch):
self.par=par
self.ch=ch

class HeapNode:
def __init__(self,bNode,up,pp,ww,lev):
self.liveNode=bNode
self.up=up
self.p=pp
self.w=ww
self.lev=lev

#插入队列
def addlivenode(heap,up,pp,ww,lev,par,ch):
b=BBnode(par,ch)
node=HeapNode(b,up,pp,ww,lev)
heap.append(node)

#上界函数,贪心
def bound(i):
global cw,cp,n,p,c,w
cleft=c-cw
bound=cp
while(i<=n and w[i]<=cleft):
cleft-=w[i]
bound+=p[i]
i+=1

if(i<=n):
bound+=p[i]*cleft/w[i]
return bound

def knapsack():
global bestp,cw,cp,n,p,c,w,bestx
i=1
up=bound(i)
heap=[]
cnode=BBnode(None,None)
while(i!=n+1):
#左孩子
cleft=cw+w[i]
if(cleft<c):
if(cp+p[i]>bestp):
bestp=cp+p[i]
addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,True)
#右孩子
up=bound(i+1)
if(up>=bestp):
addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,False)
#取下一扩展结点
node=heap.pop(0)
#更新数据
cnode=node.liveNode
cw=node.w
cp=node.p
up=node.up
i=node.lev

#最优解
for j in range(1,n+1)[::-1]:
bestx[j]=1 if cnode.ch==True else 0
cnode=cnode.par

知识点整理

  • 算法的特征:输入,输出,确定性,有限性

  • θ记号在算法复杂性的表示法中表示紧致界

  • 由分治法产生的子问题往往是原问题的较小模式,这就为使用递归提供了方便

  • 建立计算模型的目的:为了使问题的计算复杂性分析有一个共同的客观尺度

  • 基本计算模型:RAM,RASP,TM

  • 拉斯维加斯算法找到的解一定是正确

  • 贪心算法常采用自顶向下的方式求解最优解

  • 采用高级语言的主要好处:

    ①更接近算法语言,易学,易掌握②提供了结构化程序设计的环境和工具,使得设计出的程序可读性高,可维护性强,可靠性高③不依赖于机器语言,因此写出的程序可移植性好,重用率高③自动化程度高,开发周期短,程序员可以集中精力从事更重要的创造性劳动,提高程序质量

  • 贪心算法的特点:

    ①不能保证最后求得的解是最优的②策略易发现,运用简单,被广泛运用③策略多样,结果也多样④常用到辅助算法:排序

  • 平衡子问题思想:通常分治法在分割原问题,形成若干子问题时,这些子问题的规模都大致相同

  • Prim算法采用贪心策略求解最小生成树问题,其时间复杂度是O(n^2)。

  • 动态规划算法适用于解具有某种最优性质的问题。

  • 贪心算法做出的选择只是适用于在某种意义上的局部最优选择

  • 在动态规划算法中,通常不同子问题的个数随问题规模呈多项式级增长

  • 动态规划是解决多阶段决策过程的最优化问题

  • 选择能产生最优解的贪心准则是设计贪心算法的核心问题

  • 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树

  • 为什么用分治法设计的算法一般有递归调用?因为子问题的规模还很大时,必须继续使用分治法,反复分治,必然要用到递归

  • 请简述分支限界法找最优解比回溯法高的原因:在分支限界法中,每一个点只有一次机会称为扩展结点。

  • 回溯法的算法框架按照问题的解空间一般分为子集树算法框架(如解0-1背包问题)和排列树算法框架(如解批处理作业调度问题)

  • MIEmhn.png

  • 常见的多项式阶:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

  • 回溯和分支限界:

    • 相同点:都是以构造一颗状态空间树为基础的,树的结点反映了对一部分解所作的特定选择
    • 不同点:①他们处理的问题类型不同,回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。②生成状态空间树的顺序不同③对节点存储的常用数据结构以及节点存储特性也各不相同,除由搜索方式决定的不同的存储结构外,分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索
  • MoFWQK.png

  • MoFHJI.png

  • NP问题是指还未被证明是否存在多项式算法能够解决的问题,而其中NP完全问题又是最有可能不是P问题的问题类型。所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。