这一部分是结合Coursera上边塞奇威克本人的视频来看的, 讲的确实不错.
- 定量测量程序的运行时间
- union-find 动态连通性算法
- 动态连通性算法 类似于集合的实现
- 动态连通性算法 树结构实现
- 动态连通性算法 加权树实现
- 动态连通性算法 加权+路径压缩
定量测量程序的运行时间
有一个三嵌套循环的例子:
public static void printAll(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int k = j+1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
StdOut.println(a[i] + " " + a[j] + " " + a[k]);
}
}
}
}
}
很显然这个程序是对于一个数组来说有N的3次方的复杂度. 实际上, 所有N的平方以上级别的算法都是不可接受的, 会在数据量大的时候无法在合理的时间内结束.
一般要把算法优化到log的程度, 这样规模扩大的时候, 算法运行的时间也增加很少, 或者基本上是线性的.
为了衡量算法的时间, 书还提供了一个计时器程序, 可以创建一个计时器对象, 然后在程序执行完毕的时候调用对象的elapsedTime()方法来获取逝去的时间:
public class Stopwatch {
private final long start;
public Stopwatch() {
start = System.currentTimeMillis();
}
public double elapsedTime() {
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
有了这个东西就可以来计时了.
剩下这部分的数学分析和题目留待之后再看了. 重点先是学习一些算法, 然后看能不能运用一下算法.
union-find 动态连通性算法 综述
每个点叫做触点, 两个连接的点叫做一对连接, 将一组连通的点叫做连通分量, 简称分量.
抽象出的API如下:
public class UF {
//初始化N个触点,对应一个数组的0-N-1的索引
UF(int N)
//连接p和q
void union(int p, int q)
//p所在的分量的标识符
int find(int p)
//p和q是否连通, 连通返回true, 不连通返回false
boolean connected(int p, int q)
//连通分量的数量
int count{}
}
通过这些API, 就可以在N个触点里, 连通一定的触点, 然后可以随时判断两个点是否已经连通, 以及现在有几组互相内部彼此连通的点.
动态连通性算法 类似于集合的实现
这个算法的思路是, 将每个连通分量看成一个集合. 每次连通一对点, 就将这两个点所在的连通分量合并为一个集合. 为了区分集合, 可以给这个集合一个编号, 让属于这个集合的元素的编号全部相同, 但各个集合的编号不同.
具体实现的方法是初始化数组的时候, 将每个数组元素初始化为索引的值, 这样就得到了N个只有一个触点的连通分量, 每个分量的编号都不同.
在每次执行 union 的时候, 我们规定好, 把p所在的连通分量的编号全部改成q所在的连通分量的值.
这样查找分量的编号的时候, 直接返回要触点编号为索引的元素的值, 就是分量编号. 而查询两个触点是否连通, 只需要比较两个索引的值是否相同即可.
而连通分量的数量, 在每次连通之后都减去1, 据此可以编写下列的算法实现:
import java.util.Arrays;
public class UF_QUICK_FIND {
private int N;
private int[] a;
UF_QUICK_FIND(int numbers) {
this.N = numbers;
a = new int[numbers];
//初始化数组, 值 = 索引
for (int i = 0; i < numbers; i++) {
a[i] = i;
}
}
void union(int p, int q) {
//两个触点所在的连通分量的编号不同, 将所有与a[p]相同的值设置为a[q]
if (a[p] != a[q]) {
int p_number = find(p);
int q_number = find(q);
for (int i = 0; i < a.length; i++) {
if (a[i] == p_number) {
a[i] = q_number;
}
}
//成功连通一组, 需要N减去1
N--;
}
}
//查找分量很简单, 直接返回值
int find(int p) {
return a[p];
}
//判断是否连通, 只需要比较分量编号即可
boolean connected(int p, int q) {
return find(p) == find(q);
}
int count() {
return N;
}
@Override
public String toString() {
return "UF_QUICK_FIND{" +
"N=" + N +
", a=" + Arrays.toString(a) +
'}';
}
}
这个算法有没有什么问题呢, 先来看下边的几个判断和查找函数, 都是直接数组操作, 几乎可以说是常量时间.
但是问题出在union函数上, 这个函数采取的是遍历数组然后修改内容上, 每一次union操作, 都需要遍历数组一次.
一般来说, 数组长度为N, 对于其中每个操作都遍历数组, 这就是平方级的算法, 是不可接受的.
动态连通性算法 树结构实现
在这个实现中, 不再将每个元素看做一个集合中的元素, 而是看成一棵树, 每个索引的元素中存放其连接的另外一个元素的索引.
这样就形成了一个链接, 顺着每个元素一直找下去, 最终可以找到一个元素, 这个元素的索引和值相等, 这就是根节点. 在这个路径上的所有元素, 都是互相连通的.
依照这个思路, 在每次进行连通的时候, 需要先找到两个节点的根节点, 然后判断是不是一样, 如果一样说明已经连通, 如果不一样, 就把两个根节点连起来.
依照这个思路, 相比上一个实现, 只需要修改find 和 union 方法:
import java.util.Arrays;
public class UF_QUICK_UNION {
private int N;
private int[] a;
UF_QUICK_UNION(int numbers) {
this.N = numbers;
a = new int[numbers];
//初始化数组依然不变, 保持一开始每个节点都彼此独立
for (int i = 0; i < numbers; i++) {
a[i] = i;
}
}
//find函数进行了重大修改, 如果索引与值不同, 则将值取出当成索引, 去判断下一个索引位置的值
//当索引和值相同, 就说明找到了根节点, 返回根节点的值
int find(int p) {
while (p != a[p]) {
p = a[p];
}
return p;
}
//Union函数也进行重大修改, 不再遍历数组, 而是根据 p 和 q 的根节点来判断
void union(int p, int q) {
//找到p和q对应的根节点
int p_number = find(p);
int q_number = find(q);
//如果根节点编号不同, 将p的根节点连到q的根节点
if (p_number != q_number) {
a[p_number] = q_number;
N--;
}
}
boolean connected(int p, int q) {
return find(p) == find(q);
}
int count() {
return N;
}
@Override
public String toString() {
return "UF_QUICK_FIND{" +
"N=" + N +
", a=" + Arrays.toString(a) +
'}';
}
}
这个新算法的性能相比原来如何呢, 有些难以比较. 上一个算法遍历的是数组, 而后一个算法在最差的情况下, 几乎也会遍历一条单的长直线的树, 这让二者的性能都谈不上好而且稳定, 而且最差也都是平方级.
所以还需要继续改进, 可能已经看出来了, 既然是一棵树, 就有可能朝着二叉树的方向来改进.
动态连通性算法 加权树实现
这个算法的核心是将p节点的父节点设置为q的根节点的时候, 不像原来的union方法实际上是有序的, 即固定把第一个参数的树根连到第二个参数的树根上.
现在需要把这个函数修改成不按照参数的顺序, 而是平衡两棵树的长度, 始终将短树挂到长的树上去.
那么首先要解决的问题就是, 树的长度如何获取, 难道每次还需要遍历树来获取长度, 那又会丧失性能. 这里就引入了额外的数据结构, 即再用一行数组记录某个根节点的树的长度, 然后来更新, 这样就用空间换了时间.
实际的实现中添加了一个记录长度的数组, 将其初始化为所有值都是1, 表示树的初始长度是1. 然后只需要修改union函数:
import java.util.Arrays;
public class UF_WEIGHTED {
private int N;
private int[] a;
private int[] size;
UF_WEIGHTED(int numbers) {
this.N = numbers;
a = new int[numbers];
size = new int[numbers];
//初始化数组之外, 再初始化一个数组记录各个元素作为根节点的长度.
for (int i = 0; i < numbers; i++) {
a[i] = i;
size[i] = 1;
}
}
//find函数无需修改, 因为按我们的设计, 这个函数的查找非常快, 是2的对数级别
int find(int p) {
while (p != a[p]) {
p = a[p];
}
return p;
}
//新的Union算法在连通的时候, 判断两颗树的大小, 然后去把小数的长度加到大树上
void union(int p, int q) {
//找到p和q对应的根节点
int p_number = find(p);
int q_number = find(q);
if (p_number == q_number) {
return;
}
//如果p_number 是大树的根节点, q_number是小树的根节点
if (size[p_number] > size[q_number]) {
//小树连到大树上
a[q_number] = p_number;
//小树的长度需要添加到大树上
size[p_number] += size[q_number];
//p_number是小树, q_number是大树
} else {
//依然是小树连到大树上
a[p_number] = q_number;
//小树长度添加到大树上
size[q_number] += size[p_number];
}
N--;
}
boolean connected(int p, int q) {
return find(p) == find(q);
}
int count() {
return N;
}
@Override
public String toString() {
return "UF_WEIGHTED{" +
"N=" + N +
", a=" + Arrays.toString(a) +
", size=" + Arrays.toString(size) +
'}';
}
}
这个新的算法性能如何呢. 很显然可以知道, union 算法的性能是2的对数, find 的操作也绝对不会超过2的对数级别.
根据数学计算, 这个算法的复杂度是 cMlgN 次, 其中M为连接次数, N为触点个数, 很显然, 在随着N增大的时候, 这个算法和前两个算法N平方级别的复杂度相比, 只要是对数, 就可以用来处理大规模数据了.
在实际中, 这个算法都能在常数时间内完成操作, 因为对数级别基本上可以认为是常数级的.
动态连通性算法 加权+路径压缩
还有没有继续优化的可能性, 即保证在常数时间内完成各种操作. 有一种可能就是继续压缩find的时间, 如果可以修改树让所有连通的节点都直接连到根节点, 那么find就是常数时间, 整个算法就是lgN, 也就趋于常数了.
在现实中, 由于这会在find函数中带来额外的操作, 但在实际运行情况下, 与不带路径压缩的算法没有什么区别.
而路径压缩也分为好几种, 比如可以压缩部分路径, 或者压缩全部路径, 比如一个路径压缩的实现如下:
int find(int p) {
int current = p;
while (p != a[p]) {
p = a[p];
}
//直接把当前节点改连到根节点上去
a[current] = p;
return p;
}
完整的路径压缩需要加一个循环, 如下:
int find(int p) {
int current = p;
while (p != a[p]) {
p = a[p];
}
//完整路径压缩, 需要再遍历一下所有节点
while (current != a[current]) {
int i = a[current];
a[current] = p;
current = a[i];
}
return p;
}
这个路径压缩仅压缩了部分路径, 只要操作过一个点, 这个点就会被连通到根节点上去.
实际上的数学证明, 带路径压缩的加权算法, 就是对于动态连通性问题的最佳算法.
发现很多练习还是不会做, 没关系, 刚知道, 小白第一次学算法, 需要先把所有的算法例子都搞清楚, 不用想着做题. 看题目发愁是正常的. 那后边就知道该如何做了, 先把经典的算法本身搞明白再说.