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)
blank

相关推荐

  • devtools工具如何使用_devtool制作插件

    devtools工具如何使用_devtool制作插件7devtool快速参考目录7devtool快速参考7.1获得帮助7.2工作区层结构7.3向工作区层添加新配方7.4提取现有配方的来源7.5同步一个配方的提取源树7.6修改现有配方7.7编辑现有配方7.8更新配方7.9查看配方升级状态7.10升级配方7.11重置配方7.12建立你的配方7.13建立你的形象7.14在目标机器上部署你的软件7.15从目标机器上删除您的软件7.16在替代位置创建工作空间层7.17获取工作区中配方的状态

  • LVM 应用配置详解

    LVM 应用配置详解

  • tomcat配置教程idea_idea2019配置tomcat

    tomcat配置教程idea_idea2019配置tomcat1.打开idea,在项目运行列表下拉选择“editConfigurations”2.在打开的界面,点击“+”,再选择下面的TomcatServer下的local3.在打开的界面,第一行“Name”中填入tomcat的名称然后点击Configure…,在ApplicationServers界面,点击“+”,在TomcatServer配置界面选择要添加的tomcat…

    2022年10月30日
  • request.getRealPath 过期解决

    request.getRealPath 过期解决例子:StringfileUrl=request.getSession().getServletContext().getRealPath("/upload")+"/stafftemplate.xls"; request.getRealPath("")这个方法已经不推荐使用了,那代替它的是什么方法呢?下面就是替代它的方法:request.getSessio…

  • App测试面试题_软件测试算法面试题汇总

    App测试面试题_软件测试算法面试题汇总1.Web端测试和App端测试有何不同(常见)系统结构方面Web项目,b/s架构,基于浏览器的;Web测试只要更新了服务器端,客户端就会同步会更新;App项目,c/s结构的,必须要有客户端;App修改了服务端,则客户端用户所有核心版本都需要进行回归测试一遍;兼容方面Web项目:a.浏览器(火狐、谷歌、IE等)b.操作系统(Windows7、Windows10、Linux等)App项目:a.设备系统:iOS(ipad、iphone)、Android(三星、华为、联想等)、

  • ManagementObject_getsuperclass方法

    ManagementObject_getsuperclass方法原文:http://blog.csdn.net/hardstone1/article/details/5380775网上代码和MSDN帮助中都没有列出 ManagementObject[""]这里到底有哪些属性可以使用,参考了http://www.groupsrv.com/dotnet/about69957.html了之后发现了可以枚举出来所有属性,代码如函数getallprop()。…

发表回复

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

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