-
不相交集
2018-10-11 20:10:33不相交集用来解决等价问题,特点是编程实现很简单但是分析复杂。 关系:对于每一对元素,或者为true或者为false,称在集合S上定义关系R。...一个例子:不是等价关系,满足自反性和传递性,但是不满足对称性 用...不相交集用来解决等价问题,特点是编程实现很简单但是分析复杂。
关系:对于每一对元素
,
或者为true或者为false,称在集合S上定义关系R。若aRb是true,那么a和b有关系
等价关系:是满足以下3个性质的关系R:
1.自反性,对所有
,aRa
2.对称性,aRb当且仅当bRa
3.传递性,若aRb,bRc,那么aRc
一个例子:
不是等价关系,满足自反性和传递性,但是不满足对称性
用来解决等价问题的数据结构:
1.使用二维数组,缺点是浪费大量空间,比如若定义~是等价关系,那么a~b,b~c,c~d就足够判断abcd4个元素是相互等价的,但是二维布尔数组来表示这个问题很不明显
2.使用等价类,一个元素
的等价类是S的一个子集,包含所有和a有关系的元素,注意,每个元素只能出现在一个等价类中,否则按照传递性,两个等价类将合并。这样,为了验证a~b,只要验证a和b是否在一个等价类中。等价类的数据结构描述:初始输入是N个集合的类,每个集合中只有一个元素,集合之间不相交,允许使用两种运算:
Find:返回给定元素的集合的名字
Union:将a和b所在的两个等价类合并成一个新的等价类
称为不相交集的find/union运算,这是一个联机算法,执行过程中,集合通过union改变
方案:解决动态等价问题有两种方案,一种保证find常数时间,一种保证union常数时间,这两者不能同时做到。
代码如下:
#include <stdio.h> #define NumSets 128 typedef int DisjSet[NumSets + 1]; typedef int SetType; typedef int ElementType; void Initialize(DisjSet S); void SetUnion(DisjSet S, SetType Root1, SetType Root2); SetType Find(ElementType X, DisjSet S); /* 隐式的树,值为0表示自己是根,初始的时候,每个元素都是根 */ void Initialize(DisjSet S) { int i; for (i = NumSets; i > 0; i--) S[i] = 0; } /* 合并,将Root2的根设置为Root1 */ void SetUnion(DisjSet S, SetType Root1, SetType Root2) { S[Root2] = Root1; } /* 查找根,递归直到值为0,就找到了一个根,返回在数组中的位置 */ SetType Find(ElementType X, DisjSet S) { if (S[X] <= 0) return X; else return Find(S[X], S); }
两种灵巧求并的改进:
1.按大小求并
上面的代码中,union操作是无条件的,可以按大小求并,每次将小的合并到大的上,这样,深度最多是logN,因为每次合并都被放到至少是原来节点2倍的树中,一共可以合并logN次,也就是说find操作的时间是logN,M次find操作的时间是O(MlogN),最坏情况就是二项队列中的二项树。改进方法是,原来数组中值为0表示是根,改成节点个数的负值,初始时所有节点都是-1,后续union的时候,根所在节点的负值增加
2.按高度求并
和按大小求并类似,也保证深度最多O(logN),按高度求并代码如下
void SetUnion(DisjSet S, SetType Root1, SetType Root2) { /* 若Root2更深,那么将Root1合并到Root2上 */ if (S[Root2] < S[Root1]) S[Root1] = S[Root2]; else { /* 若高度相等,那么增加高度 */ if (S[Root1] == S[Root2]) S[Root1]--; S[Root2] = Root1; } }
路径压缩:对于连续M次操作,平均时间是O(M),但是最坏的O(MlogN)时间会发生,比如union之后形成了一个二项树。对union无法改进,因为无论按照何种方法执行union,都会造出来一个相同的最坏情形的树,也就是二项树,改进find如下:每次find(X)之后,从X到根的每个节点都让它的父节点变成根,只要对代码进行一点改进就可以实现,如下:
SetType Find(ElementType X, DisjSet S) { if (S[X] <= 0) return X; else return S[X] = Find(S[X], S); }
路径压缩和按照大小求并完成兼容,但是和按高度求并不兼容,因为会修改树的高度,但是可以使用秩,作为估计的高度
按秩求并和路径压缩的最坏情形:使用这两种方法,算法在最坏情形下几乎是线性的,精确时间是
,其中,
是Ackermann函数的逆,Ackermann函数如下定义:
由此定义
,在实际应用中,
。单变量反Ackermann函数写成
,是N的直到
的取对数的次数,
,
,
增长的比
还慢,不过不是常数,导致时间不是线性的
结论:使用路径压缩和按秩求并,任意顺序的
次Union/Find操作花费的时间是
分析:Union和Find操作可以以任何顺序出现,Union按秩进行,Find使用路径压缩
引理1:执行一系列Union指令时,一个秩为r的节点必然至少有
个后裔,包括自己
证明:数学归纳法
引理2:秩为r的节点的个数最多是
证明:秩为r的节点至少有
个子节点,一共N个节点,所以得到这个个数
引理3:在Union/Find算法的任一时刻,从树叶到根的路径上的节点的秩单调增加
证明:显然
记账法则:对于从代表i的定点到根的路径上的所有顶点v,在两个账户之一存入一个分币:
法则1.若v是根,或者v的父亲是根,或者v的父亲和v在不同的秩组中,那么将一个美分存入公共储金
法则2.否则,将一个canada分币存入该顶点中
引理4:对任意的find(v),无论存入总储金还是存入顶点,所存分币总数恰好等于从v到根的路径上的节点数
证明:显然
引理5:经过整个算法,在法则1下美分存入的总的数量是
证明:对于任意find,有根和根的儿子,有2个,由于一个路径上节点的秩单调递增,一共G(N)个秩组,因此一共还可以放G(N)个,M次find总的数量就是
引理6:秩组g > 0中顶点的个数
至多为
证明:由引理2,至多存在
个秩为r的节点,对秩组g中的秩求和,得到
引理7:存入秩组g的所有顶点的canada分币的最大的个数至多是
证明:秩组g中有
个节点,应用引理6得到结果
引理8:在法则2下存入分币最多是
个canada分币
证明:显然
综上,法则1和法则2总的分币数是
定理:M次Union和Find的运行时间是
证明:F是
和
递归定义的函数,
,将F和G定义插入到引理8中,得到结论
-
你必须知道的495个C语言问题
2015-10-16 14:14:282.17 C语言中有和Pascal的with等价的语句吗? 2.18 既然数组名可以用作数组的基地址,为什么对结构不能这样? 2.19 程序运行正确,但退出时却“coredump”(核心转储)了,怎么回事? 联合 2.20 结构和联合有什么... -
基于粗糙集的决策表知识约简研究
2009-07-26 14:57:21由等价类而不是单个元素参与差别矩阵的构造,得到一种简化的代数约简差别矩阵。从差别矩阵的角度讨论了代数约简和条件信息熵约简的核属性计算问题,指出代数约简核属性是信息熵约简核属性的子集。证明了分布协调集... -
数据库系统基础:初级篇(第5版)(讲述数据库系统原理的经典教材)--详细书签版
2013-04-05 13:45:32第7章 使用ER到关系的映射和EER到关系的映射进行关系数据库设计 147 7.1 使用ER到关系的映射进行关系数据库设计 147 7.1.1 ER到关系的映射算法 147 7.1.2 ER模型构造映射的讨论和总结 151 7.2 EER... -
你必须知道的495个C语言问题(高清版)
2010-03-31 16:24:092.17 C语言中有和Pascal的with等价的语句吗? 29 2.18 既然数组名可以用作数组的基地址,为什么对结构不能这样? 29 2.19 程序运行正确,但退出时却“core dump ”(核心转储)了,怎么回事? 29 联合 30 2.20... -
《你必须知道的495个C语言问题》
2010-03-20 16:41:182.17 C语言中有和Pascal的with等价的语句吗? 29 2.18 既然数组名可以用作数组的基地址,为什么对结构不能这样? 29 2.19 程序运行正确,但退出时却“core dump ”(核心转储)了,怎么回事? 29 联合 30 2.20... -
数据库系统基础:高级篇(第5版)(讲述数据库系统原理的经典教材)--详细书签版
2013-04-05 14:33:11CruiseYoung提供的带有详细书签的电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 数据库系统基础:高级篇(第5版)(讲述数据库系统原理的经典教材) 基本信息 原书名: Fundamentals of Database ... -
EL表达式的详细使用
2011-04-01 11:12:51它是一种简单的语言,基于可用的命名空间(PageContext 属性)、嵌套属性和对集合、操作符(算术型、关系型和逻辑型)的访问符、映射到 Java 类中静态方法的可扩展函数以及一组隐式对象。 EL 提供了在 JSP 脚本编制... -
工程硕士学位论文 基于Android+HTML5的移动Web项目高效开发探究
2017-02-28 21:22:19Sqlite 一款轻型的数据库,是遵守ACID的关系型数据库管理系统,它包含在一个相对小的C库中 W3C 万维网联盟,创建于1994年,是Web技术领域最具权威和影响力的国际中立性技术标准机构。主要的工作是发展 Web 规范,... -
LINGO软件的学习
2009-08-08 22:36:50不同集类型的关系见下图。 §3 模型的数据部分和初始部分 在处理模型的数据时,需要为集指派一些成员并且在LINGO求解模型之前为集的某些属性指定值。为此,LINGO为用户提供了两个可选部分:... -
数组、指针、引用等学习小结
2008-10-30 11:15:00总是搞不清楚指针、引用、数组、数组指针、指针数组等等一堆东西之间的关系和用法,学习C++ Primer之后,稍作总结,希望对需要的人有帮助,以下的文字基本上都是来自C++ Primer3的书中1、数组参数:int* 、int[] 、 ...总是搞不清楚指针、引用、数组、数组指针、指针数组等等一堆东西之间的关系和用法,学习C++ Primer之后,稍作总结,希望对需要的人有帮助,以下的文字基本上都是来自C++ Primer3的书中<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />
1、数组参数:
int* 、int[] 、 int[ 10 ]作为函数的参数是等价的
在被调函数内对参数数组的改变将被应用到数组实参上而不是本地拷贝上。
数组长度不是参数类型的一部分函数不知道传递给它的数组的实际长度编译器也不知道当编译器对实参类型进行参数类型检查时并不检查数组的长度2、传递数组长度的方法
①是提供一个含有数组长度的额外参数
void putValues( int[], int size );
②是将参数声明为数组的引用
void putValues( int (&arr)[10] );
③是使用抽象容器类型
void putValues( vector<int> vec )
另:
参数也可以是多维数组这样的参数必须指明第一维以外的所有维的长度例如:
void putValues( int matrix[][1a], int rowSize );多维数组的参数类型检查只检验多维数组实参中除了第一维之外的所有维的长度与参数的是否相同
int *matrix[ 10 ];将matrix 声明成一个含有10 个指向int 的指针的数组
int (*matrix)[10];把matrix 声明成一个二维数组每行由10 个列元素构成matrix
int (&arr)[10];将参数声明为数组的引用当参数是一个数组类型的引用时数组长度成为参数和实参类型的一部分编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配3、指针和引用作为参数的优缺点,以及何决定使用:
两种参数都允许函数修改实参指向的对象,两种类型的参数都允许有效地向函数传递大型类对象
指针可能指向一个对象或没有任何对象所以函数在确定指针实际指向一个有效的对象之前不能安全地解引用一个指针;对于引用参数函数不需要保证它指向一个对象引用必须指向一个对象甚至在我们不希望这样时也是如此。
如果一个参数可能在函数中指向不同的对象或者这个参数可能不指向任何对象则必须使用指针参数;引用参数的一个重要用法是它允许我们在有效地实现重载操作符的同时还能保证用法的直观性 -
你必须知道的495个C语言问题(PDF)
2009-09-15 10:25:471.13 以下的初始化有什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向p[i] 赋值的时候, 我的程序崩溃了。. . . . 5 1.14 我总算弄清除函数指针的声明方法了, 但怎样才能初始化呢? . . 5... -
软件测试规范
2018-04-23 09:16:121.等价类划分 .......................................................................................................................................... 7 2.因果图 ........................................ -
在 JavaScript 中用匿名函数(箭头函数)写出递归的方法
2020-12-29 11:39:46我们设想有以下特征的 <code>Y</code> 函数: <pre><code> javascript //定义时就工厂化,生产出阶乘函数 let factory = self => n => n < 2 ? 1 : n * self(n - 1) //暂时不管 Y... -
软件工程知识点
2012-12-02 21:34:25主要有以下几个方面的设计任务:制定规范、系统构架设计、软件结构设计、公共数据结构设计、安全性设计、故障处理设计、可维护性设计、编写文档、设计评审。 2.系统构架设计 (1)集中式结构 集中式系统由一台... -
C语言FAQ 常见问题列表
2010-10-28 16:41:29o 2.13 以下的初始化有什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向 p[i] 赋值的时候, 我的程序崩溃了。 o 2.14 我总算弄清除函数指针的声明方法了, 但怎样才能初始化呢? * 3.... -
iOS ARC 完全指南
2020-09-21 09:30:22修饰,以下两者是等价的 NSString firstnAme self textField text strong NSString *firstName self textField text 第7页/共49页 OS5ARC完全指南 GuanGyi Inc http://www.gungyi.com 属性可以是 写法如下 @property... -
国家集训队2019论文集.zip
2020-04-04 12:41:12该定理的证明可参见参考文献2],由于和本文主题关系不大,这 里略厶。 设p(x)=∑=0Cnx,P(M)=0即∑:0Cm-M=0,两边乘M得∑=0CnM+!=0 即∑0c;M件+=0。所以{c,C1…cn}即为数列{l,M,M2,M3……}的一个阶数为n的线性 递推... -
数据库系统概论(第四版)学习指导与习题解答-王珊.
2011-10-24 18:21:32著名的有美国 IBM 公司的 DBZ 关系数据库管理系统和 IMS 层次数据库管理系统、美国 Oracle 公司的 orade 关系数据库管理系统、 s 油 ase 公司的 s 油 ase 关系数据库管理系统、美国微软公司的 SQL Serve ,关系... -
数据库系统概论第四版答案
2011-10-24 18:22:19著名的有美国 IBM 公 司的 DBZ 关系数据库管理系统和 IMS 层次数据库管理系统、美国 Oracle 公司的 orade 关系数据库管理系统、 s 油 ase 公司的 s 油 ase 关系数据库管理系统、美国微软公司的 SQL Serve ,关系... -
sql数据库相关加密知识
2010-03-01 00:03:41一般而言,一个行之有效的数据库加密技术主要有以下6个方面的功能和特性。 (1)身份认证: 用户除提供用户名、口令外,还必须按照系统安全要求提供其它相关安全凭证。如使用终端密钥。 (2) 通信加密与完整性保护... -
C语言程序设计标准教程
2009-05-22 18:29:14各种无符号类型量所占的内存空间字节数与相应的有符号类型量相同。但由于省去了符号位,故不能表示负数。 下表列出了Turbo C中各类整型量所分配的内存字节数及数的表示范围。 类型说明符 数的范围 分配字节数 int -... -
网管教程 从入门到精通软件篇.txt
2010-04-25 22:43:49等价的设备名称是: DeviceHardDisk0Partition1 范例 下例将物理设备名映射为使用 ARC 设备名称的驱动器号: map arc 注意 如果不使用 arc 参数,则 map 命令显示设备名称。 map 命令还显示文件... -
10分钟看懂 Java NIO 底层原理
2020-10-29 16:42:17write,read把数据从内核缓冲区复制到进程缓冲区,write把数据从进程缓冲区复制到内核缓冲区,它们不等价于数据在内核缓冲区和磁盘之间的交换。 <p><img alt="" src=... -
事务处理原理 第2版
2012-12-30 10:49:38本书介绍事务处理,旨在满足广大读者的需要,包括以下读者。 ·有兴趣构建事务处理应用程序的应用程序编程人员。 ·管理用于事务处理的数据库系统的数据库管理员。 ·设计要部署在事务处理系统上的应用...
-
opencv深度图可视化
-
工人模型(FBX格式)
-
新版全民解析vip视频网站html源码
-
python创建指定版本虚拟环境
-
MySQL 数据库权限管理(用户高级管理和精确访问控制)
-
C/C++反汇编解密
-
不懂Spring的9种设计模式,面试会吃亏的
-
AD711SQ系列数据手册.pdf
-
ESP8266+OLED屏实现天气预报+温度显示+NTP时间同步6屏带中文显示V9.2
-
【Python-随到随学】FLask第二周
-
谷歌C++编程规范.docx
-
Java中Comparator比较器的应用
-
Docker从入门到精通
-
源于现实的数字孪生技术在智慧交通领域有怎样的应用.docx
-
不止是“焊门员”,Redmi K40又一次颠覆“性价比”
-
linux查看mysql版本
-
计算器 - Java语言编写.rar
-
MySQL 高可用(DRBD + heartbeat)
-
建立学生信息管理系统.doc
-
牛牛量化策略交易