Princeton Algorithms Notes | Set 0

Posted on | | Visitors

最近在跟 Princeton 的算法课：这里
顺手写一些笔记，放到这里

第一周的主要内容是 Quick Find & Quick Union & Algorithms Analysis

Quick Find

在生活中常常会见到这么一些情景：在网上购物时的商品推荐系统，社交 APP 上的好友推荐，或者是那个很有名的六度分割理论……这些事情的背后都需要有很复杂的算法来支撑。我们把情况抽象一下，把社交关系网中的人当成点，把人与人之间的关系当成点与点之间的线，就可以把社交网络抽象成如下样子：

Union Find

此时，我们如果想知道两个人之间有没有联系，即需考虑两个点之间是否 connected。我们现在要讨论的 Quick Find 就是用来解决该问题的。

我们需要用数组来存储数据，也需要有两个方法: boolean connected(), void unoin()，前者用来判断任意两个点之间是否连接，后者用来连接两个点。

connected() 方法很容易实现，直接比较 id[p] == id[q], 看这两个数组的 entry 是否相等就可以了
union() 方法要稍微复杂一些，如果我们要 union 两个点，要遍历整个数组，把所有等于前者的 entry 全部设置成后者的值

Java 代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class QuickFind{
    private int[] id;
    public QuickFind(int N){       // constructor
	id = new int[N];
	for (int i = 0; i < N; i++){
	    id[i] = i;
	}
    }
    public boolean connected(int p, int q){
	return (id[p] == id[q]);
    }
    public void union(int p, int q){
	int pid = id[p];
	int qid = id[q];
	for (int i = 0; i < id.lenght; i++){
	    if (id[i] == pid) id[i] = qid;
	}
    }
}

这样做有好处也有坏处，好处是 connected() 方法花费 O(1) 时间。而对于 union() 方法来说，最坏情况是对于每一个 array cell，都需要将其余的 N - 1 个 cell 的值替换掉，这样时间复杂度为 O(n^2)

Quick Union

Quick Union 和 Quick Find 的区别在于，它不用把所有需要改变的 entry 值全部改变，只需要将当前要连接的值改变就可以了。它通过维护 root 来判断两个点是否连接。如果 root 相同，则 connected，反之，则 unconnected

Java 代码实现如下

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
public class QuickUnion{
    private int[] id;
    public QuickUnion(int N){
	id = new int[N];
	for (int i = 0; i < N; i++){
	    id[i] = i;
	}
    }
    public int root(int i){
	while (i != id[i]) i = id[i];
	return i;
    }
    public boolean connected(int p, int q){
	return root(p) == root(q);
    }
    public void union(int p, int q){
	int i = root(p);
	int j = root(q);
	id[i] = j;
    }
}

在这种情况下，worse case 时间复杂度为 O(n)
即所有的点都连在一起形成 path graph 的情况
这样要找到 root 会 traverse 整个图，花费 O(n) 时间

当然，也有改进办法，即对每个 connected component 加上对应的 weight
把 weight 小的图放在 weight 大的图的节点下
这样就避免了数的高度太高，利于查询 root

这样做操作起来也很简单，只需再加一个 array
比如命名为 sz[]，用来记录每个 connected component 的size
如果需要进行 union 操作，将 size 小的放到 size 大的图下

具体的 Java 代码实现如下

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
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class WeightedQuickUnion{
    private int[] id;
    private int[] sz;
    private int count;
    public WeightedQuickUnion(int N){
	count = N;
	id = new int[N];
	for (int i = 0; i < N; i++) id[i] = i;
	sz = new int[N];
	for (int i = 0; i < N; i++) sz[i] = 1;
    }
	
    public int count(){
	return count;
    }
    public boolean connected(int p, int q){
	return find(p) == find(q);
    }
    public int find(int p){
	while (p != id[p]) p = id[p];
	return p;
    }
    public void union(int p, int q){
	int i = find(p);
	int j = find(q);
	if (i == j) return;
	if (sz[p] < sz[q]){
	    id[i] = j;
	    sz[j] += sz[i];
	}
	else {
	    id[j] = i;
	    sz[i] += sz[j];
	}
	count--;
    }
	
    public static void main(String[] args){
	int n = StdIn.readInt();
	WeightedQuickUnion w = new WeightedQuickUnion(n);
	while (!StdIn.isEmpty()){
	    int p = StdIn.readInt();
	    int q = StdIn.readInt();
	    if (w.connected(p, q)) continue;
	    w.union(p, q);
	    StdOut.println(p + " " + q);
	}
	StdOut.println(w.count() + " components");
    }
}

这种方法使得 union() & find() 的时间花费都为 lgN

Analysis of Algorithms

谢谢你请我吃糖果：）