(二)基础(Fundamentals):算法分析

观察

运行时间和输入本身相对无关,主要取决于问题规模
例:统计文件中三个数和为0的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ThreeSum{
public static int count(int a[]){
int N = a.length, cnt = 0;
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)
cnt += 1;
}
}
}
}
}

一种表示计时器的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
public class StopWatch{
private final long start;
public StopWatch(){
start = System.currentTimeMillis();
}
public double elapsedTime(){
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}

数学模型

程序运行总时间主要和两点有关:

  • 执行每条语句的耗时(取决于计算机、Java编译器和操作系统)
  • 执行每条语句的频率(取决于程序本身和输入)

对于执行频率,有些分析很容易,如在 Three.count() 中将 cnt 设为 0 的语句只会执行一次;有些需要深入分析,如 Three.count() 中的 if 语句会执行 $\frac{N(N-1)(N-2)}{6}$ 次。

近似

用 ~f(N) 表示所有随着N增大除以f(N)的结果趋近于1的函数。用g(N)~f(N)表示随着g(N)/f(N) 随着N增大趋近于1。

一般用到的近似方式都是 $g(N)\sim f(N)$,其中 $f(N)=N^b(logN)^c$,其中a,b和c均为常数,将f(N)称为g(N)的增长数量级。
常见的增长数量级函数:

描述 函数 B
常数级 1
对数级 $logN$
线性级 $N$
线性对数级 $NlogN$
平方级 $N^2$
立方级 $N^3$
指数级 $2^N$

执行最频繁的执行决定了程序执行的总时间——称这些指令为程序的内循环

成本模型

成本模型来评估算法的性质,这个模型定义了所研究算法中的基本操作。例如,3-Sum问题的成本模型是访问数组元素的次数。

构建运行时间的数学模型所需步骤:

  1. 确定输入模型,定义问题规模
  2. 识别内循环
  3. 根据内循环中的操作确定成本模型
  4. 对给定输入,判断这些操作的执行频率

如二分查找,它的输入模型是大小为N的数组a[],内循环是while循环中所有语句,成本模型是比较操作(比较两个数组元素的值)

设计更快的算法

2-Sum 问题

假设所有整数各不相同,这个问题很容易在平方级别——双重循环来解决,下面利用归并排序和二分查找在线性对数级别解决 2-Sum 问题:

思路:当且仅当 -a[i] 存在于数组中(且a[i]非0)时,a[i] 存在于某个和为0的整数对中。

1
2
3
4
5
6
7
8
9
10
11
12
public class TwoSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
if(BinarySearch.rank(-a[i], a) > i)
cnt++;
}
return cnt;
}
}

归并排序所需时间与 NlogN 成正比,二分查找所需时间和 logN 成正比,因此整个算法运行时间和 NlogN 成正比。

3-Sum 问题

同样假设所有整数各不相同,同上面一样,当且仅当 -(a[i] + a[j]) 在数组中(不是 a[i] 也不是 a[j])时,整数对(a[i]a[j])为某个和为0的三元组的一部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ThreeSumFast{
public static int count(int[] a){
//先排序
Arrays.sort(a);
int cnt = 0;
for(int i = 0; i < a.length; i++){
for(int j = i + 1; j < a.length; j++)
if(BinarySearch.rank(-(a[i] + a[j]), a) > j)
cnt++;
}
return cnt;
}
}

内存

对象

数组

字符串对象

当调用 substring() 方法时,就创建了一个新的 String 对象(40字节),但仍然重用了相同的 value[] 数组,因此该字符串的子字符串只会使用40字节的内存,也就是说,一个子字符串的额外内存是一个常数,构造一个子字符串所需时间也是常数。

举例:union-find 算法

动态连通性

问题的输入是一列整数对,其中每个整数都表示一个某种类型的对象,一对整数p q可以被理解为“p和q是相连的”,具有如下性质;

  • 自反性:p 和 p 是
  • 对称性:若 p 和 q 相连,则 q 和 p 也相连
  • 传递性:若 p 和 q 相连且 q 和 r 相连,则 p 和 r 也相连

union-find 算法API

方法名 操作
UF(int N) 以整数标识(0 到 N-1)初始化N个触点
void union(int p, int q) 在 p 和 q 之间添加一条连接
int find(int p) p 所在的分量的标识符(0 到 N-1)
boolean connected(int p, int q) 如果 p 和 q 存在于同一个分量则返回 true
int count() 连通分量的数量

用一个以触点为索引的数组 id[] 作为基本数据结构来表示所有分量。初始有 N 个分量,每个触点都构成了一个只含有它自己的分量,因此将 id[i] 初始化为 i,其中 i 为 0 到 N-1。find() 判定它所在分量所需的信息保存在 id[i] 之中。connected() 方法只有一条语句 find(p)==find(q),它返回一个布尔值。

实现

1 quick-find 算法

代码
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
public class UF{
private int[] id;
private int count;
public UF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
public void union(int p, int q){
int pid = find(p);
int qid = find(q);
if(pid == qid){
return;
}
for(int i = 0; i < id.length; i++){
if(id[i] == pid){
id[i] = qid;
}
}
count--;
}
public int find(int p){
return id[p];
}
public boolean connected(int p, int q){
return id[p] == id[q];
}
public int count(){
return count;
}
}
分析

上述代码的 find 方法十分高效,因为仅仅需要一次数组读取操作就能够找到该节点的组号,但是问题随之而来,对于需要添加新路径的情况,就涉及到对于组号的修改,因为并不能确定哪些节点的组号需要被修改,因此就必须对整个数组进行遍历,找到需要修改的节点,逐一修改,每次添加新路径带来的复杂度就是线性关系了,如果要添加的新路径的数量是M,节点数量是N,那么最后的时间复杂度就是MN,显然是一个平方阶的复杂度,对于大规模的数据而言,平方阶的算法是存在问题的,这种情况下,每次添加新路径就是“牵一发而动全身”,想要解决这个问题,关键就是要提高union方法的效率,让它不再需要遍历整个数组。

2 quick-union 算法

代码

id[] 数组用父链接的形式表示了一片森林,从任何触点所对应的节点开始跟随链接,最终都将到达含有该节点的树的根节点。quick-union 中 union() 的实现只用了一条语句就将一个根节点变为另一个根节点的父节点,从而归并了两棵树。

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
public class QuickUnionUF{
private int[] id;
private int count;
public QuickUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
}
}
public void union(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot){
return;
}
id[pRoot] = qRoot;
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int count(){
return count;
}
}
分析

quick-union 算法看起来比 quick-find 算法更快,因为它不需要为每对输入遍历整个数组。但树这种数据结构容易出现极端情况,因为在建树的过程中,树的最终形态严重依赖于输入数据本身的性质,比如数据是否排序,是否随机分布等等。比如在输入数据是有序的情况下,构造的BST会退化成一个链表。如下图所示。

定义:一棵树的大小是它的节点的数量。树中一个节点的深度是它到根节点的路径上的链接(也就是边)数树的高度是它的所有节点中的最大深度。
命题:quick-union 算法中 find() 方法访问数组的次数为1加上给定触点所对应的节点的深度的两倍。union() 和 connected() 访问数组的次数为两次find() 操作(若union()中给定的两个触点分别存在于不同的树中则还需要加1)。

由命题G可知,对于整数对0 i,union()操作访问数组的次数为2i+2(触点0的深度为i,触点i的深度为0)。因此,处理N对整数所需的所有find()操作访问数组的总次数为 $2(1+2+…+N)\sim N^2$。

3 加权 quick-union 算法

只需简单修改quick-union算法就能保证像这样的最坏情况不会出现。与其在 union() 中随意将一棵树连接到另一棵树,现在记录每棵树的大小并总是将较小的树连接到大数上。此时需添加一个数组来记录树中节点数,将这种算法称为加权 quick-union 算法。该算法构造的树的高度也远远小于未加权版本构造的树的高度。

代码
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
public class WeightedUnionUF{
private int[] id;
private int count;
private int[] sz;
public WeightedUnionUF(int N){
id = new int[N];
count = N;
for(int i = 0; i < N; i++){
id[i] = i;
sz[i] = 1;
}
}
public 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];
}
count--;
}
public int find(int p){
while(p != id[p]){
p = id[p];
}
return p;
}
public boolean connected(int p, int q){
return find(p) == find(q) ;
}
public int count(){
return count;
}
}
分析

命题H:对于 N 个触点,加权 quick-union 算法够早的森林中的任意节点的深度最多为 lgN。
推论:对于加权 quick-union 算法和 N 个触点,在最坏情况下 find()、connected()union() 的成本增长数量级为 logN。

命题H和推论的意义在于加权 quick-union 算法是三种算法中唯一可以用于解决大型实际问题的算法。加权 quick-union 算法处理N个触点和M条连接时最多访问数组 cMlgN 次,c为常数,比 quick-find(和某些情况下的quick-union)需要访问数组至少MN次形成鲜明对比。

4 最优算法——基于quick-union 算法进行路径压缩

理想情况下,我们希望每个结点都直接链接到它的根节点,但又不想像quick-find那样通过修改大量链接实现,实际实现很简单——在检查节点时将它们直连到根节点。

1
2
3
4
5
6
7
8
9
public int find(int p){
while(p != id[p]){
//若当前节点非根节点
//则使当前节点指向父节点的父节点/或直接指向根节点find(index)
id[p] = id[id[p]];
p = id[p];
}
return p;
}

所得到的结果几乎是完全扁平化的树,即路径压缩的加权 quick-union 算法是最优的算法

参考:

并查集(Union-Find)算法介绍

前面两篇文章的相关代码地址:
代码地址

请我喝杯咖啡吧☕~