大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
本节将从动态连接性算法(并查集问题的模型)入手,引入算法分析和设计的整体思路和优化方法,为整个课程的引子部分。
主要内容包括 Quick Find和Quick union算法,以及这些算法的改进。
动态连接性
对于连接做如下定义:
- 自反:p 连接于自身
- 对称:若p连接于q,则q连接于p
- 传递:若p连接q,q连接r那么p连接r
我们的算法需要满足上述关于连接的定义。另外,引出了另一个概念:
连通分量:最大的可连通对象集合,有两个特点:1)连通分量内部任意两个对象都是相连通的;2)连通分量内部的对象不与外部对象相连通。
功能实现:
我们需要设计一个类,该模型具有如下功能:
- 现有N个对象,可以任意连接任意两个对象
- 有一个方法,可以得知任意两个对象是否连接
图示如下:
image.png
先来看解决这类问题的第一种方法:Quick Find.
Quick Find
快速查找是基于贪心策略的一种算法,贪心策略是指在问题求解的时候,只找出当前最优解。
基于此,设计一种数据结构来存储实验对象。
-
长度为N的整型数组
-
如果p和q有相同的id,则表示他们有连接
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连接,我们不妨将所有和p的value相同的元素的value设置为id[q]
public void union(int p, int q)
{
int pid = id[p];
int qid = id[q];
if(pid==qid)
return;//如果p和q在相同的分量之中,则不需要采取任何行动
for (int i = 0; i < id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
上面的合并操作我们默认将所有与第一个id项相同的项设置为第二个id的项
下面对上面的代码进行算法复杂度分析
- 计算每个方法的数组访问次数(并部署确切的访问次数,通常理解为循环次数):
算法 | QuickFindUF | union | connected |
---|---|---|---|
QuickFind | N | N | 1 |
假设我们用这个算法最后得到一个完整的连通分量,那至少需要调用N-1次union(),每次Union中至少需要2+N+1次访问数组:两次访问pid和qid,for循环中有N次访问数组比较操作,以及至少一次的赋值操作。所以我们可以得知,对于最终只得到少数连通分量而言,这种方案一般是平方级别的:(N+3)*(N-1)~N^2.我们尽量避免使用平方级别的算法
Quick-union算法
快速合并是基于懒策略的一种算法,懒策略是指在问题求解时尽量避免计算,直到不得不进行计算。
我们依然用之前的数据结构,不过此时数组表示的是一组树或森林。
基于此,设计另外一种该数据结构来存储实验对象:
- 长度为N的整型数组
- id[i]是i的父亲,从而构造成树的结构
- 如果i=id[i],则表示id[i]是树根
因此,合并和查找操作就变为:
- 查找:检查p和q是否具有相同的根,如有则代表连通。
- 合并:在合并p和q对象时,将p的根的id(父亲)设成q的根。
查找操作虽然变得复杂了一些。
但合并操作变得十分简单,只需要改变数组中的一个值,就可以将两个大分量合并在一起。这也就是快速合并的来历。
代码实现:
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 |
这个算法中没有for循环,尽管有while循环。相对于快速查找,他是另一种慢。缺点在于树可能太高,意味着查找操作代价太大了,你可能需要回溯一颗瘦长的树。quickunion的算法消耗主要在于寻找根结点(root()),树形结构越高则数组访问次数越多。
Quick-union 优化:带权的快速合并
上面所描述的快速合并中,存在两个缺点是:一是查找时间消耗过大,二是树的深度容易过大
针对上述缺点,引入带权的快速合并
算法。在quick-union的基础上,我们通过执行一些操作避免产生很高的树。具体来说,我们需要:
-
增加一个数组来追踪每个树的大小(对象的个数)
-
在合并的时候,通过“将小树连接到大树的根”来达到平衡树高的效果
这样我们尽量保证所有节点不要离根节点太远。
优化后代码:
public class QuickUnionUF
{
private int[] id;
private int[] sz;
//构造函数,用来初始化
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++)
{
id[i]=i;
sz[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 (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
}
}
将优化后的算法称为weighted_quickunion,由于二叉树的深度最多为lgN(N表示树的节点个数),而这个算法的中的树分叉最少为2,所以root()的复杂度为lgN
优化有算法复杂度:
算法 | 初始化 | connect | union |
---|---|---|---|
quickfind | N | 1 | N |
quickunion | N | N | N |
weighted_quickunion | N | lgN | lgN |
继续优化??路径压缩!!
在检查节点的同时,将它们直接连接到根节点上,将树的路径进行压缩,从而保持树的扁平化。
代码实现:
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 |
weighted_quickunion | N+MlgN(我认为这个N是构造器初始化的算法复杂度) |
路径压缩的加权quick-union | N+Mlg*N |
足够接近线性,但无法达到线性!!(已经被证明在并查集问题中无法达到线性)
优化的意义
目前的计算机每秒钟可以执行10^9次操作
若我们对10^9 个对象进行 10^9 次连接操作,使用第一种算法那么需要30年。而使用最后一种只需要5秒。可见算法上的优化比超级计算机有用多了。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/189169.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...