引言
算法(Algorithms)是用来解决问题，在解决问题的过程中需要处理数据，数据结构(Data Structure)就是用来存储信息的。所以，算法和数据结构是计算机科学的基础，也是诸多知名公司最看重员工的能力，尤其在谷歌尤为突出。
算法能解决哪些问题呢？常见如网络中的搜索和分布式文件系统，罕见如生物学的人类基因组计划和蛋白质折叠凳问题。
算法可以追踪到欧几里得的年代，从 1930s 开始系统教学，它可以被看做是计算机科学从业者的基础，更可以被视为好奇求知识的人的共识，毕竟所有学科都离不开解决问题的目标。
“ I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. ”
— Linus Torvalds (creator of Linux)
算法和数据结构是计算机科学的基石，好像再怎么强调都不为过。或者说，有没有扎实的算法和数据结构的基础是码农和工程师的分界线。
“ Algorithms + Data Structures = Programs. ”
— Niklaus Wirth
“ Algorithms: a common language for nature, human, and computer. ”
— Avi Wigderson
Union-Find
Dynamic Connectivity
通过探讨一个问题来解释算法是什么，动态连接就是这个示例。
给定 N 个对象：
定义 Union 命令是连接两个对象；
定义 Find/connected 命令是检查两个对象是否连接。
动态连接问题在实际生活中有广泛应用，例如数码相片中的像素点，网络中的计算机，社交网络中的人际关系等。
首先要定义什么是连接：
- Reflective：p 与 p 是连接的；
- Symmetic：如果 p 与 q 是连接的，则 q 与 p 是连接的；
- Transitive：如果 p 与 q 是连接的，q 与 r 是连接的，则 p 与 r 是连接的。
其次定义连接组（connected components）：
最大两两相互连接的对象群组.
image
上例中 0， 1+4+5，2+3+6+7 分别互相两两连接，形成 3 个连接组。
Quick Find
数据结构
- 使用一个容量为 N 的数组记录数字 ID；
- 两个元素如果相连则他们的数字 ID 相同，反之亦然。
image
FIND：检查两个对象的数字 ID 是否相同
UNION：union(p, q) 就将所有数字 ID 等于 p 的对象的 ID 修改为 q。
public class QuickFindUF {
private int[] id;
// 初始化数据结构，初始值是所有数字的 ID
public QuickFindUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
// FIND 命令
pulic boolean connected(int p, int q) {
return id[p] == id[q];
}
// UNION 命令
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for (int i = 0; i < N; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
}
效率分析
初始化效率是 O(N)，Union 命令效率是 O(N)，Find 命令效率是 O(1)。Union 的效率太低了。
Quick Union
数据结构
- 使用一个容量为 N 的数组记录数字 ID；
- id[i] 是 i 的 parent；
- root 是数字 ID 指向自身的对象。
image
FIND：检查两个对象的 root 是否相同；
UNION: union(p, q) 就将 p 的 root 指向 q 的 root。
public class QuickUnionUF {
private int[] id;
// 初始化
public QuickUnionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
private int root(int i) {
while(id[i] != i) {
i = id[i];
}
return i;
}
// FIND 命令
public boolean connected(int p, int q) {
return root(p) == root(q);
}
// UNION 命令
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
id[rootP] = rootQ;
}
}
效率分析
初始化效率是 O(N)，Union 命令效率是 O(N)，Find 命令效率是 O(N)，效率太低了。
Improvements
Weighting
- 提升 quick-union，避免较高的树；
- 记录每颗树的对象数量；
- 平衡树的高度，在 union 的时候将较小的树指向较大的树的 root。
public class WeightedUF {
private int[] id;
private int[] size;
// 初始化
public WeightedUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}
private int root(int i) {
while(id[i] != i) {
i = id[i];
}
return i;
}
// FIND 命令
public boolean connected(int p, int q) {
return root(p) == root(q);
}
// UNION 命令
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return;
}
...
}
}
Path Compression
压缩路径，减少查找 root 的比对。
public class PathCompressionUF {
private int[] id;
// 初始化
public PathCompressionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
private int root(int i) {
while(id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
// FIND 命令
public boolean connected(int p, int q) {
return root(p) == root(q);
}
// UNION 命令
public void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
id[rootP] = rootQ;
}
}
效率分析
在 N 个对象执行 M 次 union-find 操作的情况下，改进后的算法最坏效率是 N + M * lgN 次。
应用
渗滤
- N * N 的格子；
- 每个格子的打开概率是 p，阻塞概率是 1 - p；
- 如果从上到下有一条打开格子连通的通路，则是渗滤的。
image
网友评论