基于「算法第四版」的算法期末复习

本文最后更新于:2022年8月17日 上午

1 算法分析与union-find算法

作业: 1.4.2 1.4.4 1.4.5 1.4.6 1.4.15

1.5.1 1.5.2 1.5.3 1.5.8

  • 如果为近似则保留系数, 例如$\frac{1}{2}\text{N}^2$

    近似: tilde notation / approximations

  • 如果为数量级则不要系数, $\text{N}^2$

    数量级: order of growth

1 | 倍率实验

倍率定理:

若$\text{T}\left( \text{N} \right) \sim \text{aN}^{\text{b}}\lg\text{N}$, 那么$\frac{\text{T}\left( 2\text{N} \right)}{\text{T}\left( \text{N} \right)}\sim 2^{\text{b}}$

将输入规模不断x2, 直到相邻两次时间之比近似为$2^b$时可以估计参数b, 估计大致的增长数量级

2 | union-find算法

掌握各个版本的轨迹和数组内容, 树结构的变化

2-1 quick-find

轨迹:

思想: 每次联通时将所有id[i]均联通

对于大小为n的id数组输入的每一对整数访问id数组的次数为:

$4+\mathrm{n}+\mathrm{x}$次, 其中$\mathrm{x}$表示for循环中的写操作

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find(int p) {
return id[p];
}

void union(int p, int q) {
int pid = find(p);
int qid = find(q);
// p和q已经在相同的分量之中
if (pid == qid) return;
// 将p的分量重命名为qid
for (int i = 0; i < id.length; ++i) {
if (id[i] == pid)
id[i] = qid;
}
}

2-2 quick-union

轨迹:

思想: 每次联通时只联通根节点

访问id数组的次数:

(每调用一次root(node)需要访问数组的次数为node的树深)

1
2
3
4
5
6
7
8
9
10
11
12
13
int find (int p) {
// 找根结点
while (p != id[p])
p = id[p];
return p;
}

void union(int p, int q) {
int proot = find(p);
int qroot = find(q);
if (proot == qroot) return;
id[proot] = qroot;
}

2-3 weighted-quick-union

weighted_quickunion

思想: 利用一个sz数组记录每棵树的大小, 并总是将较小的树连接到较大的树上

访问数组的次数(id数组和sz数组):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int find (int p) {
while (p != id[p])
p = id[p];
}

void union(int p, int q) {
int proot = find(p);
int qroot = find(q);
if (proot == qroot) return;
if (sz[proot] < sz[qroot]) {
id[proot] = qroot;
sz[qroot] += sz[proot];
} else {
id[qroot] = proot;
sz[proot] += sz[qroot];
}
}

quick-union和weighted-quick-union的对比:

2-4 路径压缩+quick-union

思想: 在查找根节点的同时将每个结点直接指向上上一级结点, 以达到扁平化的效果

1
2
3
4
5
6
7
int find (int i) {
while (i != id[i]) {
id[i] = id[id[i]]; // 核心
i = id[i];
}
return i;
}

2 归并排序

作业: 2.2.2 2.2.3 2.2.4 2.2.5 2.2.8

1 | 原地归并的抽象方法

merge(int[] a, int lo, int mid, int hi) -> 将a[lo..mid]和a[mid + 1, hi]归并为有序的a[lo…hi]

思想: 利用一个辅助数组将a复制一份然后依次比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; ++k) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; ++k) {
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j] < aux[i])
a[k] = aux[j++];
else
a[k] = aux[i++];

}

2 | 自顶向下的归并排序

思路: 递归

核心代码:

1
2
3
4
5
6
7
void sort(int a[], int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort (a, lo, mid);
sort (a, mid + 1, hi);
merge(a, lo, mid, hi);
}

轨迹: (trace)

3 | 自底向上的归并排序

思路: 先两两归并, 再四四归并…..

核心代码:

1
2
3
4
5
6
7
8
void sort(int a[]) {
int N = a.size();
aux = new int[N];
for (int sz = 1; sz < N; sz *= 2) {
for (int lo = 0; lo < N - sz; lo += sz * 2)
merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, N - 1));
}
}

轨迹:

3 快速排序

作业: 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5

1 | 算法

1
2
3
4
5
6
void sort(int []a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi); //进行切分
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}

partition

切分使得数组满足如下条件:

  1. 对于某个j, a[j]已经确定
  2. a[lo]到a[j-1]的所有元素不大于a[j]
  3. a[j+1]到a[hi]的所有元素不小于a[j]

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int partition(int []a, int lo, int hi) {
int i = lo, j = hi + 1;
int v = a[lo]; // 切分元素
while (1) {
while (a[++i] < v)
if (i == hi) break; // 从左到右找到一个 >= v的元素
while (v < a[--j])
if (j == lo) break; // 从右到左找到一个 <= v的元素
if (i >= j) break;
swap(a, i, j); // 交换元素
}
swap(a, lo, j); // 将切分元素放到对应位置
return j; // 返回切分元素的索引
}

2 | 算法改进

乱序

在每次排序之前将数组打乱并随机选取切分元素保证随机性

在小数组时候切换到插入排序

对于小数组而言, 插入排序比快速排序快

1
if (hi <= lo) return;

改为

1
2
3
4
if (hi <= lo + M) {
insertion.sort(a, lo, hi); //切换到插入排序
return;
}

其中M的值自定, 一般取5 - 15

三向切分

将数组分为三个部分, 分别对应小于, 等于和大于切分元素的数组元素

  • a[lo…lt-1]上元素 < v

  • a[lt…gt]上元素 = v

  • a[gt+1…lo]上元素 > v

之后sort(lo, lt-1)sort(gt + 1, hi)即可, 避免了很多对重复元素的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
void tsort(vector<int>& a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, i = lo + 1, gt = hi;
int v = a[lo];
while (i <= gt) {
if (a[i] < v) swap(a[lt++], a[i++]);
else if (a[i] > v) swap(a[i], a[gt--]);
else ++i;
}
cout << lt << " " << gt << endl;
tsort (a, lo, lt - 1);
tsort (a, gt + 1, hi);
}

3 | 课后作业

2.3.1

2.3.2

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
/**
* author: roccoshi
* created: 2020-12-28 12:42:21
*/
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {
int i = lo, j = hi + 1;
int v = a[lo]; // 切分元素
while (1) {
while (a[++i] < v)
if (i == hi) break; // 从左到右找到一个 >= v的元素
while (v < a[--j])
if (j == lo) break; // 从右到左找到一个 <= v的元素
if (i >= j) break;
swap(a[i], a[j]); // 交换元素
}
swap(a[lo], a[j]); // 将切分元素放到对应位置
return j; // 返回切分元素的索引
}

void qsort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int j = partition(a, lo, hi);
cout << "lo: " << lo << " hi: " << hi << " j: " << j << endl;
qsort(a, lo, j - 1);
qsort(a, j + 1, hi);
}



int main () {
vector<int> a{'E','A','S','Y','Q','U','E','S','T','I','O','N'};
qsort(a, 0, a.size() - 1);
for (char i : a) {
cout << i << " ";
}
}

/*
lo: 0 hi: 11 j: 2
lo: 0 hi: 1 j: 1
lo: 3 hi: 11 j: 11
lo: 3 hi: 10 j: 4
lo: 5 hi: 10 j: 10
lo: 5 hi: 9 j: 5
lo: 6 hi: 9 j: 7
lo: 8 hi: 9 j: 9
A E E I N O Q S S T U Y
*/

2.3.3

2.3.4

顺序就是最坏情况

2.3.5

进行一次三向切分即可

4 | 各个排序的比较

4 优先队列

作业: 2.4.5 2.4.7 2.4.9 2.4.18

下面代码以最大堆为例, 给出c++的实现

1 | 下沉和上升

1
2
3
4
5
6
7
8
// 元素的上升swim
// 实现: 当子节点大于父节点时将二者交换
void swim(vector<int>& a, int k) {
while (k > 1 && a[k / 2] < a[k]) {
swap(a[k / 2], a[k]);
k = k / 2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
// 元素的下沉sink
// 实现: 当父节点值小于子节点时与子节点的较大者交换
void sink(vector<int>& a, int k) {
int N = a.size() - 1;
while (k * 2 <= N) {
int j = k * 2;
if (j < N && a[j] < a[j + 1]) ++j;
if (a[k] >= a[j]) break;
swap(a[k], a[j]);
k = j;
}
}

2 | 插入和删除最大元素的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 插入
// 实现: 数组末尾加入一个元素后进行上浮操作
void insert(vector<int>& a, int k) {
a.push_back(k);
swim(a, a.size() - 1);
}

// 删除最大元素
// 实现: 将首元素和末尾元素交换, pop最后一个空间, 然后将首元素(新)下沉
int delMax(vector<int>& a) {
int maxnum = a[1]; // 最大元素
swap(a[1], a[a.size() - 1]); // 将最大元素和最后一个结点交换
a.pop_back();
sink(a, 1); // 恢复有序性
return maxnum;
}

完整测试代码:

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
/**
* author: roccoshi
* created: 2020-12-31 12:33:53
*/
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;
void swim(vector<int>& ,int);
void sink(vector<int>& ,int);
void insert(vector<int>&, int);
int delMax(vector<int>&);

void swim(vector<int>& a, int k) {
while (k > 1 && a[k / 2] < a[k]) {
swap(a[k / 2], a[k]);
k = k / 2;
}
}

void sink(vector<int>& a, int k) {
int N = a.size() - 1;
while (k * 2 <= N) {
int j = k * 2;
if (j < N && a[j] < a[j + 1]) ++j;
if (a[k] >= a[j]) break;
swap(a[k], a[j]);
k = j;
}
}

void insert(vector<int>& a, int k) {
a.push_back(k);
swim(a, a.size() - 1);
}

int delMax(vector<int>& a) {
int maxnum = a[1]; // 最大元素
swap(a[1], a[a.size() - 1]); // 将最大元素和最后一个结点交换
a.pop_back();
sink(a, 1); // 恢复有序性
return maxnum;
}

int main() {
vector<int> heap{0}; // 从1开始
for (int i = 0; i < 10; ++i) {
int k;
cin >> k;
insert(heap, k);
for (int i : heap) cout << i << " ";
cout << endl;
if (i > 5) {
cout << "delete max num: " << delMax(heap) << endl;
for (int i : heap) cout << i << " ";
cout << endl;
}
cout << "The max num: " << heap[1] << endl;
}
return 0;
}

3 | 插入和删除元素的时间复杂度比较

无序数组: unordered array

有序数组: ordered array

无序链表: unordered linked list

有序链表: linked list

Q: is an array that is sorted in decreasing order a max-oriented heap?

A: yep.

4 | 堆排序

核心思想: 从N/2开始构造堆 (非叶子结点全部sink一遍), 然后每次将最大元素与最后一个元素交换后N—, 然后重新sink一遍

1
2
3
4
5
6
7
8
9
10
11
// c++伪代码
sort(vector<int>& a) {
int N = a.size();
for (int k = N / 2; k >= 1; k--) {
sink(a, k, N); // 构造堆, 从N/2开始
}
while (N > 1) {
exch(a, 1, N--); // 将第一个元素和最后一个元素交换
sink(a, 1, N); // N-1, 然后sink重新堆有序
}
}

轨迹

构造堆的轨迹

下沉排序的轨迹

5 符号表

作业: 3.1.10 3.1.11

1 | SequentialSearchST

顺序查找的无序链表

步骤:

2 | BinarySearchST

二分查找的有序数组

有序符号表的实现:

  • 两个平行的数组, 一个存储键(有序), 一个存储值

  • 利用rank()操作(二分查找)统计小于新增元素的元素个数 (如果新增元素在数组中已经存在, 那么小于它的元素个数就是它本身的索引, 如果不存在, 就是其需要插入到数组中的位置)

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
// rank的实现
// 1. 递归实现
int rank(vector<int>& keys, int key, int lo, int hi) {
if (hi < lo) return lo;
int mid = lo + (hi - lo) / 2;
if (key < keys[mid])
return rank(keys, key, lo, mid - 1);
else if (key > keys[mid])
return rank(keys, key, mid + 1, hi);
else
return mid;
}
// 2. 迭代实现
int rank(vector<int>& keys, int key) {
int lo = 0, hi = keys.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < keys[mid])
hi = mid - 1;
else if (key > keys[mid])
lo = mid + 1;
else
return mid;
}
return lo;
}

6 二叉查找树BST

作业: 3.2.1 3.2.4 3.2.15(abcd) 3.18

二叉查找树就是一个每个结点的键都大于其左子树任意结点的键而小于右子树任意结点的键。(假设每个结点是一个键值对, 键参与比较)

1 | 方法

max(): 最大键

min(): 最小键

floor(): 小于等于key的最大键

ceiling(): 大于等于key的最小键

select(node x, int k): 返回排名为k的结点

rank(int key): 返回给定键的排名

delete(): 删除

deleteMin()

deleteMax()

keys(): 范围查找

2 | get和put的实现

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
// 数据结构:
/*
struct node {
int key;
int val;
node left;
node right;
}
*/
// 找到结点x所对应的值
int get (node x, int key) {
if (x == null) return null;
if (key < x.key) return get(x.left, key);
else if (key > x.key) return get(x.right, key);
else
return x.val;
}
// 加入一个新结点(key, value)
void put (int key, int val) {
root = put(root, key, val);
}
void put (node x, int key, int val) {
if (x == null)
return;
if (key < x.key)
x.left = put (x.left, key, val);
else if (key > x.key)
x.right = put (x.right, key, val);
else // 如果已经存在x
x.val = val;
return x;
}

3 | select和rank的实现

select(node x, int k): 返回排名为k的结点

rank(int key): 返回给定键的排名

4 | 删除

第一种情况: 被删除的结点仅有单个或者无子结点

则删除后该位置为子结点 / NULL

第二种情况: 被删除的结点有两个子结点

则删除后该位置由右子树最小的结点代替

5 | keys()范围查找

keys(node x, queue, lo, hi)

保存在lo-hi之间的键到queue中

顺序: 先左子树, 再根节点, 再右子树 (中序)

7 最小生成树mst

最小生成树: (Minimum Spanning Tree) MST

作业: 4.3.3 4.3.13 4.3.18

1 | Prim算法

Prim算法的延时实现(lazy)

数据结构

1
2
3
marked[v] = true // 表示顶点v在树中

edgeTo[v] // 将v连接到树中的Edge对象

横切边: 目前一端在树里一端不在的边

失效边: 两端都在树里的边

流程

prim算法延时的流程:

  • 将起点和与起点相连的所有边压入最小堆优先队列
  • 选出权重最小的边
  • 判断是否已经在树中, 如不在, 压入mst, 并将其横切边都加入优先队列
  • 重复上述步骤

延时实现的特点是保留了失效边, 即当新顶点加入树中时, 没有删除优先队列中那些两端都已经在最小生成树中的边

Prim算法的即时实现(eager)

由于我们感兴趣的只是连接树顶点和非树顶点中权重最小的边, 当将顶点v添加到树中时, 非树顶点w产生的变化只可能使得w到最小生成树的距离更近了

所以我们不需要保存所有从w到树顶点的边而只需要保存最小的那条

在添加v顶点后检查是否需要更新那条最小的边即可

数据结构

1
2
3
4
// 将mst[]去除, 取代而之的是
Edge edgeTo[]
double distTo[]
// v不在树中但有和树相连的边, edgeTo[v]表示v和树相连的最短边, distTo[v]表示这条边的权重

2 | Kruskal算法

思路: 按照边的权值从小到大排列. 依次选中, 判断是否与当前mst构成环, 如果不成环则加入。

一种实现:

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
* author: roccoshi
* created: 2020-12-31 19:43:13
*/
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;

const int N = 16;
vector<int> g;
vector<int> id;

typedef struct Edge {
int v;
int w;
double weight;
}Edge;

// 小顶堆
auto cmp = [](const Edge& i, const Edge& j){return i.weight > j.weight;};
priority_queue<Edge, vector<Edge>, decltype(cmp)> pq(cmp);

int find(int w) {
while (w != id[w]) {
id[w] = id[id[w]];
w = id[w];
}
return w;
}

bool connected(int w, int v) {
return find(w) == find(v);
}

void merge(int w, int v) {
int wr = find(w), wv = find(v);
id[wr] = wv;
}

int main () {
Edge e[N];
for (int i = 0; i < N; ++i) {
int w, v;
double we;
cin >> w >> v >> we;
e[i].v = w;
e[i].w = v;
e[i].weight = we;
pq.push(e[i]);
}
// while (!pq.empty()) { // 输出优先队列测试
// Edge e = pq.top();
// pq.pop();
// cout << e.w << " " << e.v << " " << e.weight << endl;
// }
for (int i = 0; i < N; ++i) {
id.push_back(i);
}
while (!pq.empty()) {
Edge e = pq.top();
pq.pop();
int v = e.v;
int w = e.w;
if (connected(v, w)) continue;
merge(v, w);
cout << "added: " << v << " " << w << " " << e.weight << endl;
}
return 0;
}

/*
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
*/

3 | 关于三种算法的复杂度

算法 空间 时间
延时Pirm E ElogE
即时Prim V ElogV
Kruskal E ElogE

8 Dijkstra最短路

作业: 4.4.1 4.4.4 4.4.6 4.4.9

1 | Dijkstra轨迹

v distTo[v] edgeTo[v] (父链接数组)
顶点 起点到该点的加权值 连接该点和其上一级结点的路径

2 | Dijkstra核心—边的松弛

1
2
3
4
5
6
7
8
9
10
11
// 边松弛伪代码如下:
int w = e.to;
if (distTo[w] > distTo[v] + e.weight) {
distTo[w] = distTo[v] + e.weight; // 边松弛, 更新路径长度 (权值)
edgeTo[w] = e; // 更新到w的边为e
// 优先队列记录了当前所有可到达的顶点以及路径长度
if (pq.contains(w))
pq.change(w, distTo[w]); // 如果w已经在pq中就更新
else
pq.insert(w, distTo[w]); // 否则将w插入pq中
}

3 | 负环与Bellman-Ford

由下图可见, 当出现负环时, Dijkstra算法会出现错误, 且不能简单地将各个边加一个数成正数

解决方法: 使用Bellman-Ford算法解决负环问题

Bellman-Ford算法

思路, 初始化:

  • distTo[源点] = 0, distTo[其他点] = ∞
  • 对每一条边都进行松弛
1
2
3
4
5
6
for (int i = 0; i < G.V(); ++i) {
for (int v = 0; v < G.V(); ++v) {
for (DirectedEdge e : G.adj(v))
relax(e);
}
}

9 字符串排序

作业: 5.1.2

1 | 键索引计数法(key-indexed counting)

(本质就是桶排序

1
2
3
4
5
6
// 计算出现频率
for (int i = 0; i < N; ++i)
count[a[i].key() + 1]++;
// 将频率转化为索引
for (int r = 0; r < R; r++)
count[r + 1] += count[r];

数据分类与回写

1
2
3
4
5
6
// 元素分类
for (int i = 0; i < N; ++i)
aux[count[a[i].key()]++] = a[i];
// 回写
for (int i = 0; i < N; ++i)
a[i] = aux[i];

2 | 低位优先的字符串排序(LSD)

LSD: least significant digital

低位优先的字符串排序可以稳定地将定长字符串排序

思路: 将字符串从右向左地依次排序, 利用基数排序(Radix sort)的思想

LSD的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void LSD(vector<string>& a, int w) { // w表示从第w个字符开始往左排序
int N = a.size(); // 字符串的个数
int R = 256; // ascii码最大256
vector<string> aux(N);
for (int d = w - 1; d >= 0; --d) { // 从第w个字符开始往回排序
vector<int> count(R + 1, 0); // 计数, count[i]表示字符i - 1出现的次数
for (int i = 0; i < N; ++i) {
count[a[i][d] + 1]++; // a[i][d]表示第i个字符串第d位字符
}
for (int r = 0; r < R; ++r) {
count[r + 1] += count[r]; // 累加, 之后count[i]表示小于字符i - 1的字符的个数
}
for (int i = 0; i < N; ++i) { // 利用辅助数组实现稳定的排序
aux[count[a[i][d]] ++] = a[i];
}
for (int i = 0; i < N; ++i) { // 回写
a[i] = aux[i];
}
}
}

3 | 高位优先的字符串排序(MSD)

MSD: most significant digital

高位优先的字符串排序可以对非定长字符串进行排序,且稳定

思路: 首先根据首字母用建索引计数法进行排序, 然后递归地根据子数组中的字符串的首字母将子数组排序。


基于「算法第四版」的算法期末复习
https://blog.roccoshi.top/posts/34431/
作者
RoccoShi
发布于
2021年1月6日
许可协议