YongSir

专业程序员伪装者

algs003-《算法》4th笔记

算法分析

如何评价一个算法？我们用什么标准来评价？具体是怎样分析的？

  • 科学的方式？

Observe some feature of the natural world, generally with precise measurements

Hypothesize a model that is consistent with the observations

Predict events using the hypothesis

Verify the predictions by making further observations

Validate by repeating until the hypothesis and observations agree

The experiments we design must be reproducible and the hypotheses that we formulate must be falsifiable

设计实验可以重复的，结果也是可以重复的
直觉告诉我们，计算性任务的困难程度可以由问题的规模来衡量，越是规模大的问题所需时间就越长，故从探讨：如何将问题规模和运行时间的关系量化是很合适的起点

使用ThreeSum程序，根据输入问题的规模来实验：
猜测复合幂函数分布，并预测了跟大规模的用时，通过比较验证了程序的运行时间根问题规模基本呈幂函数分布

对于一段程序对其运行时间的数学建模往往需要一下步骤：

  • 确定输入，定义问题规模
  • 识别内循环
  • 根据内循环操作，确定成本模型
  • 对于给定的输入，判断操作的执行频率

并查集Union Find

并查集，是一种常见的数据结构方式，用以解决诸如集合合并查找类的问题，一开始并不关注其使用
还是照着老路子，我们要从基本的数据单元得到最合适的API及其实现

使用一个网络连接布线的例子，也称为动态连通性问题，如果两个触点之间已经可以连通，就不需要布线了，使用数值代表触点，并有以下约定：

  1. 使用0-9来代表10个集合编号并且每个集合内的元素就是集合号本身－－也就是触点
  2. 如果假定集合4和3拥有共同的某种属性，我们就称之为集合3等同于集合4，使用3＝4标记－－就是3 4 触电连接
  3. 如果3=4，同时4=5，5=7，1=9的话，［1 3 4 5 7 9］可归并为同一个集合，拥有相同的集合名称 －－ 触电连接可传递

约定本篇不再区分触点和集合，连通和合并，归并等术语，设计的API如下：

1
2
3
4
5
6
public calss UF 的API：
	UF(int N)				初始化0 .. N-1 共N个集合
	void union(int p, int q)             	在p和q连通，也叫2个集合合并
	int find(int p)				查找p所在的集合的编号
	boolean connected(int p, int q)		p和q是否连通
	int count()				连通分量数，就是集合数

使用数组id[]作为基本数据结构，一开始有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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class UF {
	private int[] id;
	private int count;

	// 初始化：N个分量N个触点，每个触点一个分量
	public UF(int N) {
		count = N;
		id = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
		}
	}

	public int count() {return count;}

	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}

	public int find(int p)  // 留待
	public void union(int p, int q) // 留待

	// 测试及输出说明
	// 输入N个触点，通过每队整数调用find()方法：
	//	 若已连通，忽略；
	//	 若不连通，则调用union()方法连通；
	// 最终输出各个连通分量对和总共的连通数
	public static void main(String[] args) {
		int N = StdIn.radInt();
		UF uf = new NF(N);
		while!(StaIn.isEmpty()) {
			int p = StdIn.readInt();
			int q = StdIn.readInt();
			if(uf.connected(p , q)) continue; // 访问2次
			uf.union(q,p);
			StdOut.println(p + "连接" + q);
		}
		StdOut.println(uf.count() + "条连接");
	}
}

剩下的就在于find()和union()的实现了，而其中很多地方如connected()本质上都需要find()方法，故它的具体实现会直接决定我们算法的效率，而各种查找算法真是本书的一大章节，这篇不会详细介绍留待后边，由于我们特殊的限定（即i就是触点名）这里选用最朴素的方式直接返回即可； 然后不妨在来考虑union()的实现，由于我们使用id[i]表示触点，i为触点号，所以对于任意的两个触点连通就意味着2个触点同属一个触点的不同分量，所以对于id[x] = id [y] = SetName就完成了触点的归并，如果若B触点都拥有多个分量值，只要B中有一个分量与A触点连通，根据连通传递的特性，那么B中所有分量都与A连通，故有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void union(int q, int p) {
	int pID = find(p); // 访问一次数组
	int qID = find(q); // 访问一次数组

	// 如果在已经连通，忽略
	if(pID == qID) return;

	// 合并2个触点的所有分量，即让所有分量同名
	for(int i = 0; i < id.length; i++ ) { // 遍历一次
		if(id[i] == pID) id[i] = qID;
	}
	count--;
}

// 直接返回即可
public Int find(int q) {
	return id[q];
}

定性的分析以下可知，find()一次会访问数组一次，整个测试中connected()和union()中又多次find,特别是在union中有对数组的完整遍历要访问N次，如果全部触点都连通的话，在main中又会有N次union(),所以综合来看动态连通性问题的quick－find算法会是N^2级别的数组访问次数，在处理大型数据时并不能接受，是否还能提高呢？

quick-union

它是针对于上述quick-find的改进，它使用的并不是单纯的数组，而是使用树结构,一开始每一个树都只有一层一个节点，自然自己跟自己是连通的；如果p和q的root节点不同，表示两者不连通，如果两者root节点相同表示连通；如果两个不连通的树，调用union之后，会将一个树作为另一个树的分支，合并为拥有一个root节点的大树，通过这些描述，我们有了实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int find(int q){
	while( !id[q] == q ) { // 查找分量名
		q = id[q];
	}
	return  q;
}

public void union(int q, int p) {
	int pRoot = find(p);
	int qRoot = find(q);
	// 如果连通，忽略；不连通，就连通
	if(pRoot == qRoot) return;
	id[pRoot] = qRoot;
	count--;

}

个人在理解的时候，倒是find()给我造成了些困惑，其实需要牢记先前的初始化是的一个约定，一个触点／集合的名称编号为数组的i，而集合的分量是在变动的,注意参考图示
如：

quick-union

但是，对比quick-find,quick-union真的好吗？我们来分析它们的效率

对于前者，如果需要添加一个新的连通时，如a连通b，那么由于并不直到根b连通的已经有多少，只能遍历整个数组N，保证让a，b以及各自连通的分量都使用一个名称a，这样如果添加了N个每个都要N次，那么就是N^2级别的

对于后者，在最坏的情况下，即按顺序的查找如0－1，0－2，0-3…这样的顺序，最终会得到的树没有分支，就是一整条链表，如果这时从链表最底部的开始查询，需要遍历真个数组N级别的，然后如果完成全部连通，也是N^2级别的
但在其他情形之下，由于树都是有分支的，

…