普林斯顿算法中级笔记1(连接算法)
连接算法
本节共分为两个部分：功能实现与算法优化。 属于整个课程的引子。
功能实现：
提出以下模型，该模型具有如下功能：
- 现有N个对象，可以任意连接任意两个对象
- 有一个方法，可以得知任意两个对象是否连接
图示如下：
image.png
对于连接做如下定义：
- 自反：p 连接于自身
- 对称：若p连接于q,则q连接于p
- 传递：若p连接q，q连接r那么p连接r
我们假设被连接的对象均是数字，把他们作为一个数组的index，使用数组来存储被连接的对象集合，具有相同value的元素被认为是相互连接的
image.png
定义一个类描述上述模型 该类的名称成为QuickFindUF：
public class QuickFindUF
{
private int[] id;
//构造函数，为每一个数组元素赋值为自己的Index
public QuickFindUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
}
//通过两个元素的value是否相同来判断他们是否连接
public boolean connected(int p, int q)
{ return id[p] == id[q]; }
//如果希望p与q连接 则 需要将所有的value为p的元素的value设置为id[q]
public void union(int p, int q)
{
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
下面对上面的代码进行算法复杂度分析
- 计算每个方法的数组访问次数（并部署确切的访问次数，通常理解为循环次数）：
| 算法 | QuickFindUF | union | connected |
|---|---|---|---|
| QuickFind | N | N | 1 |
如果对一个包含N个元素的集合进行完全的联通，则N^2的数组访问，这是一个二次方算法复杂度的算法。
image.png
算法优化
对上面算法进行优化
新的数据结构：
树形结构
若q,p在同一颗树中，则认为是连接的，通过将p的根结点变q的根节点的子节点来进行连接操作。
仍旧使用数组承载这个数据结构，定义id[i]为i的父节点。
屏幕快照 2018-07-30 上午10.24.56.png
屏幕快照 2018-07-30 上午10.25.01.png
代码实现：
public class QuickUnionUF
{
private int[] id;
//构造函数，用来初始化
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
//获取根结点
private 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;
}
}
将这个算法成为quickunion
算法复杂度分析：
| 算法 | 初始化 | connect | union |
|---|---|---|---|
| quickfind | N | 1 | N |
| quickunion | N | N | N |
可以看出单纯，数据结构上的变动并没有优化这个算法。但是树形结构的好处在于具有很多可以优化的地方，下面进行进一步的优化
quickunion的算法消耗主要在于寻找根结点(root())，树形结构越高则数组访问次数越多，针对这点进行以下优化。
增加一个数组，在用来记录每个树的大小
在union时将size较小的树合并到size较大的树，这样整体上树的高度就会变小。
优化后代码：
public class QuickUnionUF
{
private int[] id;
private int[] len;
//构造函数，用来初始化
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++)
{
id[i]=i;
len[i]=1;
}
}
//获取根结点
private 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);
if (i == j) return;
if (len[i] < len[j]) { id[i] = j; len[j] += len[i]; }
else { len[j] = i; len[i] += len[j]; }
id[i] = j;
}
}
将优化后的算法称为weightedquickunion,由于二叉树的深度最多为lgN(N表示树的节点个数)，而这个算法的中的树分叉最少为2，所以root()的复杂度为lgN
优化有算法复杂度：
| 算法 | 初始化 | connect | union |
|---|---|---|---|
| quickfind | N | 1 | N |
| quickunion | N | N | N |
| weightedquickunion | N | lgN | lgN |
继续优化:路径压缩：将树的高度进一步扁平化。
将这个算法称为weightedquickunionwithpathcompress:WQUWPC
代码实现：
private int root(int i)
{
while (i != id[i])
{
//将i指向它父节点的父节点，若id[i]已经是根结点，则id[i]=i=id[id[i]]；
id[i] = id[id[i]];
i = id[i];
}
return i;
}
计算上面这个算法复杂度前先进行一个名词解释：
lg*N:迭代对数.它是目前增长最慢的函数之一。
假设我们要对N个对象进行M次连接操作，各种算法的算法消耗如下：
| 算法 | 消耗 |
|---|---|
| quickfind | MN |
| quickunion | MN |
| weightedquickunion | N+MlgN(我认为这个N是构造器初始化的算法复杂度) |
| WQUWPC | N+Mlg*N |
优化的意义
目前的计算机每秒钟可以执行10^9次操作
若我们对10^9 个对象进行 10^9 次连接操作，使用第一种算法那么需要30年。而使用最后一种只需要5秒。可见算法上的优化比超级计算机有用多了。
