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

quick-union最坏情况

定义：一棵树的大小是它的节点的数量。树中一个节点的深度是它到根节点的路径上的链接（也就是边）数。树的高度是它的所有节点中的最大深度。
命题：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次形成鲜明对比。

各种union-find算法性能特点

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)算法介绍

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

请我喝杯咖啡吧☕~
分享到： 收藏夹 新浪微博 QQ空间 微信 腾讯QQ 复制网址 一键分享 更多