Algorithms 普林斯顿算法课程笔记(一)

Algorithms 普林斯顿算法课程笔记(一)本节将从动态连接性算法(并查集问题的模型)入手,引入算法分析和设计的整体思路和优化方法,为整个课程的引子部分。主要内容包括QuickFind和Quickunion算法,以及这些算法的改进。动态连接性对于连接做如下定义:自反:p连接于自身 对称:若p连接于q,则q连接于p 传递:若p连接q,q连接r那么p连接r我们的算法需要满足上述关于连接的定义。另外,引出了另一个概念…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

本节将从动态连接性算法(并查集问题的模型)入手,引入算法分析和设计的整体思路和优化方法,为整个课程的引子部分。

主要内容包括 Quick Find和Quick union算法,以及这些算法的改进。

动态连接性

对于连接做如下定义:

  1. 自反:p 连接于自身
  2. 对称:若p连接于q,则q连接于p
  3. 传递:若p连接q,q连接r那么p连接r

我们的算法需要满足上述关于连接的定义。另外,引出了另一个概念:

连通分量:最大的可连通对象集合,有两个特点:1)连通分量内部任意两个对象都是相连通的;2)连通分量内部的对象不与外部对象相连通。

功能实现:

我们需要设计一个类,该模型具有如下功能:

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

Algorithms 普林斯顿算法课程笔记(一)

image.png

先来看解决这类问题的第一种方法:Quick Find.

Quick Find

快速查找是基于贪心策略的一种算法,贪心策略是指在问题求解的时候,只找出当前最优解。

基于此,设计一种数据结构来存储实验对象。

  • 长度为N的整型数组

  • 如果p和q有相同的id,则表示他们有连接

Algorithms 普林斯顿算法课程笔记(一)

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的项

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

  1. 计算每个方法的数组访问次数(并部署确切的访问次数,通常理解为循环次数):
算法 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]是树根

Algorithms 普林斯顿算法课程笔记(一)

Algorithms 普林斯顿算法课程笔记(一)

因此,合并和查找操作就变为:

  • 查找:检查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账号...

(0)


相关推荐

  • 万能激活成功教程器修改器_闪照激活成功教程软件

    万能激活成功教程器修改器_闪照激活成功教程软件第一步:下载补丁文件如果是2017.2以上版本的,需要JetbrainsCrack-2.6.6及以上版本如果是2018.1及以上版本的,需要JetbrainsCrack-2.8及以上版本本人是windows64G系统,安装的2018.1.4专业版,试过JetbrainsCrack-2.6的,只能延长有效期一年;使用JetbrainsCrack-2.8的版本,有效期到2099年12月31…

    2022年10月28日
  • Elasticsearch集群规划及节点角色规划醉佳实践

    Elasticsearch集群规划及节点角色规划醉佳实践ES集群规划及节点角色规划最佳实践

  • npm下载和使用(超详细)

    npm下载和使用(超详细)NPM(NodePackageManager)简称为Node包管理工具安装(首先我们需要安装Node)Mac如果没有安装Node可以使用mac的包管理神器HomeBrew进行安装,首先下载HomeBrew,接下来在终端执行以下命令brewinstallnode也可以选择去官网下载pkg安装包,记得下载长期稳定版,即LTS版windows可以在官网中选择windows相对应的版本,同样下载稳定版本,一步点击安装即可使用当下载好Node后我们就可以使用n..

    2022年10月28日
  • RX 和 TX_RX和OTC

    RX 和 TX_RX和OTC我们在ifconfig查看网卡配置时或者嵌入式开发的时候,经常会看到rx/tx缩写,其含义如下:RX==receive,接收,从开启到现在接收封包的情况,是下行流量。TX==Transmit,发

  • jmeter 查看结果树导出接口结果文件,常用字段

    jmeter 查看结果树导出接口结果文件,常用字段

  • Java调用第三方接口(http总结)

    Java调用第三方接口(http总结)业务需求:一般情况下都是后端提供接口,前端调用,解决需求,但是有的时候为了方便,复用别人的接口(网上的,公共的第三方接口(短信、天气等)),就出现了后端调用后端接口的情况。(类似JavaScript中的ajax一样获取数据,并对数据进行处理)对比一般情况:前端调用后端接口业务情况:后端调用后端接口几种方式总结:在Java项目中调用第三方接口的方式有:①通过JDK网络类Java….

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号