算法C复习大纲

Posted on

算法C

0、小标题写页码的需要自己去看书，因为太多了……

1、绪论

算法的概念

算法(algorithm)是一系列解决问题的明确指令，也就是说，对于符合一定规范的输入，能够在有限时间内获得要求的输出。

算法的性质

输入、输出、确定性、有限性、可行性

①算法的每一个步骤都必须没有歧义，不能有半点儿含糊。

②必须认真确定算法所处理的输入的值域。

③同一算法可以用几种不同的形式来描述。

④同一问题，可能存在几种不同的算法。

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

基本数据结构

数组（Array）

n个相同数据类型的元素构成的序列，它们连续存储在计算机的存储器中，我们只要指定数组的下标（index）就能够访问这些元素。

链表（Linked List）

是0个或多个称为节点（node）的元素构成的序列。

每个节点包含两类信息：

一类是数据；

另一类是一个或多个称为指针（pointer）的链接，指向链表中其他元素（我们用一种称为null 的特殊指针表明某个节点没有后继元素）。

栈（Stack）

一种插入和删除操作都只能在端部进行的列表，这一端称为栈顶（top），该结构按照一种“后进先出”（last-in-first-out，LIFO）的方式运转。

队列（Queue）

删除元素在列表的一头进行，这一头称为队头（front），这种删除操作称为出队（dequeue）

插入元素在表的另一头进行，这一头称为队尾（rear），这种插入操作称为入队（enqueue）

因此，队列是按照一种“先进先出”（first-in-first-out，FIFO）的方式运行。

图和树 p22-p28

太多了，自己去看

2、算法效率分析基础

符号：

最差效率（worst-case efficiency）

当输入规模为n时算法在最坏情况下的效率。

这时，相对于其他规模为n的输入，该算法的运行时间最长。

最优效率（best-case efficiency）

是指当输入规模为n时，算法在最优情况下的效率。

这时，与其他规模为n的输入相比，该算法运行得最快。

平均效率（average-case efficiency）

无论是最差效率分析还是最优效率分析，都不能提供一种必要的信息。

在“典型”或者“随机”输入的情况下，一个算法会具有什么样的行为。

3、蛮力法

是一种简单直接解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

基于交换的排序

选择排序

选择排序

时间复杂度为n^2

1
2
3
4
5
6
7
8
9
10
11
12
#Python实现选择排序
A = [64, 25, 12, 22, 11]
for i in range(len(A)):
	min_idx = i
	for j in range(i+1, len(A)):
		if A[min_idx] > A[j]:
			min_idx = j
	A[i], A[min_idx] = A[min_idx], A[i]

print("排序后的数组：")
for i in range(len(A)):
	print("{}".format(A[i]),end=" ")

冒泡排序

冒泡排序

时间复杂度为n^2

1
2
3
4
5
6
7
8
9
10
11
12
#Python实现冒泡排序
def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print("{}".format(arr[i]),end=" ")

顺序查找

顺序查找

时间复杂度为n

穷举查找

穷举查找是一种简单的蛮力方法，它要求生成问题域中的每一个元素，选出其中满足问题约束的元素，然后再找出一个期望元素（例如，使目标函数达到最优的元素）。

旅行商问题、背包问题、分配问题 P89-P92（看书，东西有点点多，应该考不了多少）

4、减治法

利用一个问题给定实例的解和同样问题较小实例的解之间的某种关系。

建立关系之后，即可以从顶至下（递归的），也可以从底至上（非递归的）运用此关系。

插入排序

插入排序

时间复杂度为n^2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print("{}".format(arr[i]),end=" ")

拓扑排序

在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。

先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度-1。

一直做改操作，直到所有的节点都被分离出来。如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

两种算法：P107-P109

折半查找

对于有序数组的查找来说，折半查找是一种性能卓越的算法。

它通过比较查找键K和数组中间元素A[m]来完成查找工作。如果它们相等，算法结束。

否则，如果K<A[m]，就对数组的前半部分执行该操作，如果K>A[m]，则对数组的后半部分执行该操作。

折半查找

时间复杂度为log2^n

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
# 返回x 在 arr 中的索引，如果不存在返回 -1
def binarySearch(arr, l, r, x):
    # 基本判断
    if r >= l:
        mid = int(l + (r - l) / 2)
        # 元素整好的中间位置
        if arr[mid] == x:
            return mid
            # 元素小于中间位置的元素，只需要再比较左边的元素
        elif arr[mid] > x:
            return binarySearch(arr, l, mid - 1, x)
            # 元素大于中间位置的元素，只需要再比较右边的元素
        else:
            return binarySearch(arr, mid + 1, r, x)
    else:
        # 不存在
        return -1
# 测试数组
arr = [2, 3, 4, 10, 40]
x = 10
# 函数调用
result = binarySearch(arr, 0, len(arr) - 1, x)
if result != -1:
    print("元素在数组中的索引为{}".format(result))
else:
    print("元素不在数组中")

5、分治法

将问题的实例划分成若干个较小的实例，对这些较小的实例递归求解，然后合并这些解，得到原始问题的解。

合并排序

单个数组合并排序

两个数组合并排序

时间复杂度为nlogn

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
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 arrays L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

        # 归并临时数组到 arr[l..r]
    i = 0  # 初始化第一个子数组的索引
    j = 0  # 初始化第二个子数组的索引
    k = l  # 初始归并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的保留元素
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的保留元素
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = int((l + (r - 1)) / 2)

        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

arr = [12, 11, 13, 5, 6, 7]
n = len(arr)

mergeSort(arr, 0, n - 1)
print("排序后的数组")
for i in range(n):
    print("{}".format(arr[i]),end=" ")

快速排序

时间复杂度为nlogn

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
def partition(arr, low, high):
    i = (low - 1)  # 最小元素索引
    pivot = arr[high]

    for j in range(low, high):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)

# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引

# 快速排序函数
def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n - 1)
print("排序后的数组:")
for i in range(n):
    print("{}".format(arr[i]),end=" ")

二叉树遍历

把二叉树定义为若干节点的一个有限集合，它要么为空，要么由一个根和两棵称为TL和TR的不相交二叉树构成，这两棵二叉树分别为根的左右子树。我们常常认为二叉树是有序树的一种特例。

1
2
3
4
5
6
Height(T)
//输出:T的高度
//输入：一棵二叉树
//输出：T的高度
if T=Øreturn-1
else return max{Height(Tleft),Height(Tright)}+l

二叉树的三种经典遍历算法：前序、中序和后序。

前序遍历（根左右）

根在访问左右子树(就是这种先左后右的次序)之前被访问。

中序遍历（左根右）

根在访问左子树后，但在访问右子树前被访问。

后序遍历（左右根）

根在访问左右子树(就是这种先左后右的次序)之后被访问。

例题：

大数乘法的原理 p145-p146

n位数的乘法需要对n/2位数做三次乘法运算

Strassen矩阵乘法 p146-p148

计算两个2x2矩阵 A 和 B 的积 C 只需要进行 7 次乘法运算，而不是蛮力算法所需要的 8 次

6、变治法

是一组基于变换思想的技术，把问题变换成一种更容易解决的类型。

预排序 P156-P158

为什么用预排序？

效率更高

霍纳法则 P182-P184

问题化简

问题化简提倡把一个给定的问题变换为另一个可以用已知算法求解的问题。

7、 时空权衡

计数排序

比较计数排序

针对待排序列表中的每一个元素，算出列表中小于该元素的元素个数，并把结果记录在一张表中。这个“个数”指出了该元素在有序列表中的位置。

也就是说，如果对于某些元素来说，这个数字是10，它应该排在有序数组第11个位置(如果我们从0开始计数，它的下标是10)上。

因此，我们可以简单地把列表的元素复制到它在有序的新列表中的相应位置上，来对列表进行排序。这个算法称为比较计数排序

1
2
3
4
5
6
7
8
9
10
11
ComparisonCountingSort(A[0..n-1]//用比较计数法对数组排序
//输入：可排序数组A[0..n-1]
//输出：将A中元素按照升序排列的数组 S[0..n-1]
for i<-0 to n-l do   Count[i] <-0
for i<-0 to n-2 do
	for j<-i+1 to n-1 do
		if A[i]<A[j]
			Counr[j]<-Count[j]+1
		else Count[i]<-Counr[i]+1
for i<-0 to n-1 do S[Count[i]]<-A[i]
return S

分布计数

让我们来考虑一种更现实的情况，即待排序的数组元素有一些其他信息和键相关联，这样一来，我们就不能改写列表的元素了。于是，我们可以把元素复制到一个新数组S[0..n-1]中。

A中元素的值如果等于最小的值l，就被复制到S的前F[0]个元素中，也就是，位置0到F[0]-1，值等于l+1的元素被复制到位置F[0]至位置(F[0]+F[1])-1，以此类推。

因为这种频率的累积和在统计中称为分布，这个方法本身也称作分布计数。

horspool方法

第一步：对于给定的长度为m的模式和在模式及文本中用到的字母表，按照上面的描述构造移动表。

第二步：将模式与文本的开始处对齐。

第三步：重复下面的过程，直到发现了一个匹配子串或者模式到达了文本的最后一个字符以外。从模式的最后一个字符开始，比较模式和文本中的相应字符，直到：

要么所有m个字符都匹配（然后停止），要么遇到了一对不匹配的字符。

在后一种情况下，如果c是当前文本中和模式的最后一个字符相对齐的字符，从移动表的第c列中取出单元格t(c)的值，然后将模式沿着文本向右移动t(c)个字符的距离。

8、动态规划（重要）

真不知道咋写，自己去看书吧，或者结合下面的链接看看

warshall算法

p235 链接

1
2
3
4
5
6
7
8
9
10
Warshall(A[1..n,1..n])
//实现计算传递闭包的Warshall算法
//输入：包括n个顶点有向图的邻接矩阵A
//输出：该有向图的传递闭包
R^(0) <- A
for k <- 1 to n do
	for i <- 1 to n do
		for j <- 1 to n do
            R^(k)[i,j]<-R^k-1[i,j] or R^(k-1)[i,k] and R^(k-1)[k,j]
	return R^(n)

floyd算法(n对n的最短路径)

解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。

根据加权图初始化邻接矩阵，确定某一点，一步步寻找最短路径。

p238 链接

1
2
3
4
5
6
7
8
9
10
Floyd (1..n,1..n])
//实现计算完全最短路径的Floyd算法
//输入：不包含长度为负的回路的图的权重矩阵W
//输出：包含最短路径长度的距离矩阵
D<-W  //如果可以改写W，这一步可以省略
for k <- 1 to n do
for i <- 1 to n do
	for j <- 1 to n do
		D[i,j]<-min{D[i,j],D[i,k]+D[k,j]}
return D

最优二叉查找树

p230 链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
OptimalBST(P[1..n])
//用动态规划算法求最优二叉查找树
//输入：一个n个键的有序列表的查找概率数组P[1..n]
//输出：在最优BST中成功查找的平均比较次数，以及最优BST中子树的根表R
for i <- 1 to n do
	C[i, i-1]<0
	C[i,i] <- P[i]
	R[i,i] <- i
C[n+l,n] <- 0
for d <- 1 to n-l do //对角线计数
	for i <- 1 to n-d do
		j <- i+d
		minval <- ∞
		for k <- i to j do
			if C[i,k-1]+C[k+1,j] < minval
				minval <- C[i,k-1]+C[k+1,j];kmin <- k
		R[i,j] <- kmin
		sum <- P[i]; for s <- i+1 to j do sum <- sum+P[s]
		C[i,j] <- minval + sum
return C[1,n],R

9、贪婪技术（重要）

通过一系列步骤来构造问题的解，每一步目前构造的部分做一次扩展，直到获得问题的完整解，核心是每一步选择都必须满足可行，局部最优和不可取消原则。

Prim算法（求最小生成树）找点

它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一棵最小生成树。

P245 链接

Kruskal算法（求最小生成树）找边

首先，将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。重复这个过程直到所有的边都探查过。

P250 链接

Dijkstra算法（求1到n的最短路径）

Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T。

初始时，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点。

然后，我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。

然后，又从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。

P256 链接

哈夫曼树

找出存放一串字符所需的最少的二进制编码

P260 链接

10、算法能力的极限

P、NP和NPC问题的概念

P是能够用（确定性的）算法在多项式的时间内求解的判定问题。

NP是一类可以用不确定多项式算法求解的判定问题。

NPC问题：NP中所有其他问题可以在多项式时间内转化为这种问题。

相互关系

P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。

NPC问题是NP问题的子集。

为什么用这些方法？各方法基于问题的属性

对8、9的folyd算法、dijkstra算法、prim算法、kruskal算法的原理、优缺点、伪代码重点考察

PS：各个排序的复杂度

来自知乎@sugarTang