普林斯顿算法中级笔记1(连接算法)

连接算法

---

本节共分为两个部分：功能实现与算法优化。 属于整个课程的引子。

功能实现：

提出以下模型，该模型具有如下功能：

• 现有N个对象，可以任意连接任意两个对象
• 有一个方法，可以得知任意两个对象是否连接
  图示如下：

image.png

对于连接做如下定义：

1. 自反：p 连接于自身
2. 对称：若p连接于q,则q连接于p
3. 传递：若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;
     }
}

下面对上面的代码进行算法复杂度分析

1. 计算每个方法的数组访问次数（并部署确切的访问次数，通常理解为循环次数）：

算法	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秒。可见算法上的优化比超级计算机有用多了。