算法设计与分析基础

• 第一章 绪论
• • 1.1 什么是算法
  • 1.2 算法问题求解基础
  • • 1.2.1 理解问题
    • 1.2.2 了解计算设备的性能
    • 1.2.3 在精确解法和近似解法之间做出选择
    • 1.2.4 算法的设计技术
    • 1.2.5 确定适当的数据结构
    • 1.2.6 算法的描述
  • 1.4 基本数据结构
  • • 1.4.2 图
• 第三章 蛮力法
• • 3.1 选择排序和冒泡排序
  • • 3.1.1 选择排序
    • 3.1.2 冒泡排序
  • 3.2 顺序查找和蛮力字符串匹配
  • • 3.2.1 顺序查找
    • 3.2.2 蛮力字符串匹配
  • 3.4 穷举查找
  • • 3.4.1 旅行商问题
    • 3.4.2 背包问题
  • 3.5 深度优先查找和广度优先查找
  • • 3.5.1 深度优先查找
    • 3.5.2 广度优先查找
• 第四章 减治法
• • 4.1 插入排序
  • 4.4 减常因子算法
  • • 4.4.1 折半查找
• 第五章 分治法
• • 5.1 合并算法
• 第九章 贪婪技术
• • 9.1 Prim算法
  • 9.2 Kruskal算法
  • 9.3 Dijkstra算法
• 其他
• • 斐波那契数列
  • 装配线调度

第一章 绪论

1.1 什么是算法

1. 算法是一系列解决问题的明确指令。

2. (1)算法的每一个步骤都必须没有歧义，不能有半点儿含糊；

   (2)必须认真确定算法所处理的输入的值域；

   (3)同一算法可以用几种不同的形式来描述；

   (4)同一问题，可能存在几种不同的算法；

   (5)针对同一问题的算法可能基于完全不同的解题思路，而且解题速度也会有显著不同。

1.2 算法问题求解基础

1.2.1 理解问题

1. 算法的输入，确定了该算法所解问题的一个实例。
2. 严格确定算法需要处理的实例范围非常重要。
3. 正确的算法能正确处理所有合法的输入。

1.2.2 了解计算设备的性能

1. 顺序算法：指令逐条运行，每次执行一步操作。
2. 并行算法：可以在同一时间执行多条操作，即并行计算。

1.2.3 在精确解法和近似解法之间做出选择

1. 精确算法：精确解题。
2. 近似算法：近似解题。

1.2.4 算法的设计技术

1. 算法设计技术(也称为“策略”或者“范例”)是用算法解题的一般性方法，用于解决不同计算领域的多种问题。

1.2.5 确定适当的数据结构

1.2.6 算法的描述

1. 伪代码：伪代码是自然语言和类编程语言组成的混合结构。

1.4 基本数据结构

1.4.2 图

哈密顿回路：一个对图的每个顶点都只穿越一次的回路。

第三章 蛮力法

3.1 选择排序和冒泡排序

3.1.1 选择排序

1. 选择排序开始的时候，找到它的最小元素，然后和第一个元素交互，将最小元素放到它在有序表中的最终位置上。然后从第二个元素开始扫描列表，找到最后n-1个元素中的最小元素，再和第二个元素交换位置，把第二小的元素放在它的最终位置上。一般来说，在对该列表做第i遍扫描的时候(i的值从0到n-2)，该算法在最后n-i个元素中寻找最小元素，然后拿它和Ai交换。

   SelectionSort(A[0..n - 1])

//用选择排序对给定的数组排序
//输入：一个可排序的数组A[0..n - 1]
//输出：升序排列的数组A[0..n - 1]
for i = 0 to n - 2 do
begin
	min = i
	for j = i + 1 to n - 1 do
		if A[j] < A[min] then
			min = j
	swap A[i] and A[min]
end
           

1. 时间复杂度：O(n2)

3.1.2 冒泡排序

1. 比较表中的相邻元素，如果它们是逆序的话就交换它们的位置。重复多次后，最大的元素就“沉到”列表的最后一个位置。第二遍操作将第二大的元素沉下去。直到n-1遍以后，该列表就排序好了。

   BubbleSort(A[0..n - 1])

//用冒泡排序对给定的数组排序
//输入：一个可排序的数组A[0..n - 1]
//输出：升序排列的数组A[0..n - 1]
for i = 0 to n - 2 do
begin
	for j = n - 1 downto i + 1 do
		if(A[j] < A[j - 1]) then
		swap A[j] and A[j - 1]
end
           

1. 时间复杂度：O(n2)

3.2 顺序查找和蛮力字符串匹配

3.2.1 顺序查找

1. 简单地将给定列表中的连续元素和给定的查找键进行比较，直到遇到一个匹配的元素(成功查找)，或者在遇到匹配元素前就遍历了整个列表(失败查找)。

   SequentialSearch(A[0..n], K)

//顺序查找的算法实现，使用查找键来作限位器
//输入：一个n个元素的数组A和一个查找键K
//输出：第一个值等于K的元素的位置，如果找不到这样的元素，返回-1
A[n] = K
i = 0
while A[i] ≠ K do
	i = i +1
if i < n then
	return i
else 
	return -1
           

//输入：一个n个元素的数列A和一个数字K
//输出：确定X是否在数列A中
i = 0
while i < n do
begin
	if K == a[i] then
		report "Found!" and stop
	else
		i = i + 1
end
report "Not Found!"
           

1. 时间复杂度

   (1)最好情况：K为第一个数字，O(1)。

   (2)最坏情况：K为最后一个数字或未找到，O(n)。

2. 改进：如果已知给定的数组是有序的，只要遇到一个大于或等于查找键的元素，就停止查找。

3.2.2 蛮力字符串匹配

1. 给定一个n个字符组成的串(称为文本)，一个m(m≤n)个字符的串(称为模式)，从文本中寻找匹配模式的子串。
2. 将模式对准文本的前m个字符，然后从做到右匹配每一对相应的字符，直到m对字符全部匹配(算法停止)或者遇到一对不匹配的字符。在后一种情况下，模式向右移一位，然后从模式的第一个字符开始，继续把模式和文本中的对应字符进行比较。注意在文本中最后一轮子串匹配的起始位置是n-m(假设文本位置的下标是从0到n-1)。

   BruteForceStringMatch(T[0..n - 1], P[0..m - 1])

//实现蛮力字符串匹配
//输入：一个n个字符的数组T[0..n - 1]，代表一段文本
//          一个m个字符的数组P[0..m - 1]，代表一个模式
//输出：如果查找成功，返回文本的第一个匹配子串中第一个字符的位置，否则返回-1
for i = 0 to n - m do
begin
	j = 0
	while (j < m) and (P[j] == T[i + j]) do
		j = j + 1
	if j == m then
		return i
end
return -1
           

1. 时间复杂度

   (1)最好情况：模式在文本开头，O(m)。

   (2)最坏情况：模式在文本末尾或未找到，O(nm)。

3.4 穷举查找

3.4.1 旅行商问题

1. 要求找出一条n个给定的城市间的最短路径，使我们在回到出发的城市之前，对每个城市都只访问一次。
2. 这个问题可以用加权图来建模，用图的定点代表城市，用边的权重表示城市间的距离。这样该问题就可以表述为求一个图的最短哈密顿回路问题。
3. 哈密顿回路：一个对图的每个顶点都只穿越一次的回路。
4. 哈密顿回路可以定义为n+1个相邻顶点V1、V2……Vn、V1的一个序列。其中序列的第一个顶点和最后一个顶点是相同的，而其他n-1个顶点都是互不相同的。假设所有回路都开始和结束于相同的特定顶点。可以通过生成n-1个中间城市的组合来得到所有的旅行线路，计算这些线路的长度，然后求得最短的线路。

3.4.2 背包问题

1. 给定n个重量为w1、w2……wn，价值为v1、v2……vn的物品和一个承重为W的背包，求这些物品中一个最有价值的子集，并且要能够装到背包中。
2. 考虑给定的n个物品集合的所有子集，为了找出可行的子集(总重量不超过背包承重能力的子集)，要计算出每个子集的总重量，然后在它们中间找到价值最大的子集。

3.5 深度优先查找和广度优先查找

3.5.1 深度优先查找

1. 从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。但在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。这个过程一直持续，直到遇到一个终点——该顶点的所有邻接顶点都已被访问过。在该终点上，该算法远着来路后退一条边，并试着继续从那里访问未访问的顶点。在后退到起始顶点，并且起始顶点也是一个终点时，该算法停止。起始顶点所在的连通分量的所有顶点都被访问过了。如果未访问过的顶点仍然存在，该算法必须从其中任一顶点开始，重复上述过程。

   DFS(G)

//实现给定图的深度优先查找遍历
//输入：图G = <V,E>
//输出：图G的顶点，按照被DFS遍历访问到的先后次序，用连续的整数标记
将V中的每个顶点标记为0，表示还“未访问”
count = 0
for each vertex v in V do
	if v is marked with 0
		dfs(v)

dfs(v)
//递归访问所有和v相连接的未访问顶点，然后按照全局变量count的值
//根据访问它们的先后顺序，给它们赋上相应的数字
count = count + 1
mark v with count
for each vertex w in V adjacent to v do
	if w is marked with 0
		dfs(w)
           

3.5.2 广度优先查找

1. 按照一种同心圆的方式，首先访问所有和初始顶点邻接的顶点，然后是离它两条边的所有未访问的顶点，以此类推，直到所有与初始顶点同在一个连通分量中的顶点都访问过了为止。如果仍然存在未被访问的顶点，该算法必须从图的其他连通分量中的任意顶点重新开始。
2. 使用队列来跟踪广度优先查找的操作是比较方便的。该队列先从遍历的初始顶点开始，将该顶点标记为已访问。在每次迭代的时候，该算法找出所有和对头顶点邻接的未访问顶点，把它们标记为已访问，再把它们入队。然后，将对头顶点从队列中移去。

   BFS(G)

//实现给定图的广度优先查找遍历
//输入：图G = <V,E>
//输出：图G的顶点，按照被BFS遍历访问到的先后次序，用连续的整数标记
将V中的每个顶点标记为0，表示还“未访问”
count = 0
for each vertex v in V do
	if v is marked with 0
		bfs(v)

bfs(v)
//访问所有和v相连接的未访问顶点，然后按照全局变量count的值
//根据访问它们的先后顺序，给它们赋上相应的数字
count = count + 1
mark v with count and initialize a queue with v
while the queue is not empty do
	for each vertex w in V adjacent to the front vertex do
		if w is marked with 0
			count = count + 1
			mark w with count
			add w to the queue
	remove the front vertex from the queue
           

第四章 减治法

4.1 插入排序

1. 假设对较小数组A[0…n - 2]排序的问题已经解决，得到了一个大小为n - 1的有序数组。利用这个较小规模的解，将元素A[n - 1]考虑进来，从右到左扫描这个有序数组，直到遇到第一个小于等于A[n - 1]的元素，然后把A[n - 1]插在该元素的后面。

   InsertionSort(A[0..n - 1])

//用插入排序对给定的数组排序
//输入：n个可排序元素构成的一个数组A[0..n - 1]
//输出：升序排列的数组A[0..n - 1]
for i = 1 to n - 1 do
begin
	key = A[i]
	pos = i -1
	while pos >= 0 and A[pos] > key do
		A[pos + 1] = A[pos]
		pos = pos - 1
	A[pos + 1] = key
end
           

1. 时间复杂度：O(n2)

4.4 减常因子算法

4.4.1 折半查找

1. 对于有序数组的查找来说，折半查找是一种性能卓越的算法。
2. 比较查找键K和数组中间元素A[m]来完成查找工作。如果它们相等，算法结束。如果K＜A[m]，对数组的前半部分执行该操作。如果K＞A[m]，对数组的后半部分执行该操作。

   BinarySearch(A[0..n-1], K)

//实现非递归的折半查找
//输入：一个升序数组A[0..n - 1]和一个查找键K
//输出：一个数组元素的下标，该元素等于K；如果没有这样一个元素，返回-1
first = 0, last = n - 1
while (first <= last) do
begin
	mid = ⌊ (first + last) / 2 ⌋ //⌊⌋ 是floor函数，表示向下取整
	if(K == A[mid]) then 
		return mid
	else if(K < A[mid]) then
		last = mid - 1
	else
		first = mid + 1
end
return -1
           

1. 时间复杂度

   (1)最好情况：K是中间数，O(1)。

   (2)最坏情况：O(log n)。

2. 顺序查找的时间复杂度是O(n)，折半查找的时间复杂度是O(log n)，折半查找比顺序查找更有效率。

第五章 分治法

1. 分治法可能是最著名的通用算法设计技术。

2. 分治法按照以下方案工作：

   (1)将一个问题划分为同一类型的若干子问题，子问题最好规模相同。

   (2)对这些字问题求解(一般使用递归方法，但问题规模足够小时，有时也会利用另一个算法)。

   (3)有必要的话，合并这些子问题的解，以得到原始问题的答案。

3. 递归折半查找

   RecurBinarySearch(A[0..n-1], first, last, K)

//实现递归的折半查找
begin
	if(first > last) then
		return false
	mid = ⌊ (first + last) / 2 ⌋
	if(K == A[mid]) then
		return true
	if(K < A[mid] then
		return RecurBinarySearch(A, first, mid-1, K)
	else
		return RecurBinarySearch(A, mid+1, last, K)
end
           

5.1 合并算法

1. 对于一个需要排序的数组A[0…n-1]，合并排序把它一分为二：A[0…⌊n/2⌋-1]和A[⌊n/2⌋…n-1]，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。

   MergeSort(A[0..n-1])

   Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])

//递归调用MergeSort来对数组A[0..n-1]排序
//输入：一个可排序的数组A[0..n-1]
//输出：升序排列的数组A[0..n-1]
if n > 1 then begin
	copy A[0..⌊n/2⌋-1] to B[0..⌊n/2⌋-1]
	copy A[⌊n/2⌋..n-1] to C[0..⌊n/2⌋-1]
	MergeSort(B[0..⌊n/2⌋-1])
	MergeSort(C[0..⌊n/2⌋-1])
	Merge(B, C, A)
           

1. 初始状态下，两个指针(数组下标)分别指向两个待合并数组的第一个元素。然后比较这两个元素的大小，将较小的元素添加到一个新创建的数组中。被复制数组中的指针后移，指向该较小元素的后继元素。上述操作一直持续到两个数组中的一个被处理完为止。然后将未处理完的数组中剩下的元素复制到新数组的尾部。

   Merge(B[0..p-1], C[0..q-1], A[0..p+q-1])

//将两个有序数组合并为一个有序数组
//输入：两个有序数组B[0..p-1]和C[0..q-1]
//输出：A[0..p+q-1]中已经有序存放了B和C中的元素
i = 0, j = 0, k = 0
while i < p and j < q do
	if B[i] <= C[j] then
		A[k] = B[i]
		i = i + 1
	else 
		A[k] = C[j]
		j = j + 1
	k = k + 1
if i = p then
	copy C[j..q-1] to A[k..p+q-1]
else
	copy B[i..p-1] to A[k..p+q-1]
           

1. 时间复杂度：O(n log n)

第九章 贪婪技术

1. 贪婪法：通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。所做的每一步选择都必须满足以下条件：

   (1)可行的：即它必须满足问题的约束。

   (2)局部最优：它是当前步骤中所有可行选择中的最佳的局部选择。

   (3)不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。

2. 通过一系列局部的最优选择，可能整个问题的(全局的)不是最优解。
3. 生成树：连通图的一棵生成树是包含图的所有顶点的连通无环子图(也就是一棵树)
4. 最小生成树：加权连通图的一棵最小生成树是图的一棵权重最小的生成树，其中树的权重定义为所有边的权重总和。

9.1 Prim算法

1. 通过一系列不断扩张的子树来构造一棵最小生成树。从图的顶点集合V中任意选择的一个单顶点，作为序列中的初始子树。每一次迭代时，以一种贪婪的方式来扩张当前的生成树，即把不在树中的最近顶点添加到树中(最近顶点是指一个不在树中的顶点，它以一条权重最小的边和树中的顶点相连，而树的形状是无所谓的)。当图的所有顶点都包含在所构造的树中以后，该算法停止。迭代总次数是n-1，其中n是图中顶点的个数。
2. 时间复杂度：O(|E| log |V|)

9.2 Kruskal算法

1. 该算法通过对子图的一系列扩展来构造一棵最小生成树，这些子图总是无环的，但在算法的中间阶段，并不一定是连通的
2. 该算法在开始的时候，按照权重的非递减顺序对图中的边进行排序。然后，从一个空子图开始，它会扫描这个有序列表，并试图把列表中的下一条边加到当前的子图中。这种添加不应导致一个回路，如果产生了回路，则把这条边跳过。
3. 时间复杂度：O(|E| log |E|)

9.3 Dijkstra算法

1. 单起点最短路径问题：对于加权连通图的一个称为起点的给定顶点，求出它到所有其他顶点直接的一系列最短路径。
2. 该算法只能应用于不含负权重的图。
3. 首先它求出从起点到最接近起点的顶点之间的最短路径，然后求出第二近的，以此类推。在第i次迭代开始一起，该算法已经确定了i-1条连接起点和离起点最近顶点之间的最短路径。这些顶点、起点和从起点到顶点的路径上的边，构成了给定图的一棵子树Ti。因为所有边的权重都是非负数，可以从与Ti的顶点相邻的顶点中找到下一个和起点最接近的顶点。和Ti顶点相邻的顶点集合称为“边缘顶点”，以他们为候选对象，Dijkstra算法可以从中选出下一个最接近起点的顶点。
4. 时间复杂度：O(|E| log |V|)

其他

斐波那契数列

1. 0 1 1 2 3 5 8 13 21 34 55 89……

2. F(n) = 1 n=0或1

   F(n-1) + F(n-2) n>1

3. F(n)

Procedure F(n)
	if n==0 or n==1 then
		return 1
	else return F(n-1) + F(n-2)
//指数级

Procedure F(n)
	Set A[0] = A[1] = 1
	for i = 2 to n do
		A[i] = A[i-1] + A[i-2]
	return A[n]
//时间复杂度：O(n)
           

装配线调度