精华内容
下载资源
问答
  • 不相交集

    2018-10-11 20:10:33
    不相交集用来解决等价问题,特点是编程实现很简单但是分析复杂。 关系:对于每一对元素,或者为true或者为false,称在集合S上定义关系R。...一个例子:不是等价关系,满足自反性和传递性,但是不满足对称性 用...

    不相交集用来解决等价问题,特点是编程实现很简单但是分析复杂。

    关系:对于每一对元素(a,b),a,b\in SaRb或者为true或者为false,称在集合S上定义关系R。若aRb是true,那么a和b有关系

    等价关系:是满足以下3个性质的关系R:

    1.自反性,对所有a\in S,aRa

    2.对称性,aRb当且仅当bRa

    3.传递性,若aRb,bRc,那么aRc

    一个例子:\leqslant不是等价关系,满足自反性和传递性,但是不满足对称性

    用来解决等价问题的数据结构:

    1.使用二维数组,缺点是浪费大量空间,比如若定义~是等价关系,那么a~b,b~c,c~d就足够判断abcd4个元素是相互等价的,但是二维布尔数组来表示这个问题很不明显

    2.使用等价类,一个元素a\in S的等价类是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);
    }
    

    路径压缩和按照大小求并完成兼容,但是和按高度求并不兼容,因为会修改树的高度,但是可以使用秩,作为估计的高度

    按秩求并和路径压缩的最坏情形:使用这两种方法,算法在最坏情形下几乎是线性的,精确时间是\Theta (M\alpha (M,N)),M\geqslant N,其中,\alpha(M,N)是Ackermann函数的逆,Ackermann函数如下定义:

    A(1,j)=2^j,j\geqslant 1

    A(i,1)=A(i-1,2),i\geqslant 2

    A(i,j)=A(i-1,A(i,j-1)),i,j\geqslant 2

    由此定义\alpha (M,N)=min\left \{ i\geqslant 1|A(i,\left \lfloor M/N \right \rfloor)> logN \right \},在实际应用中,\alpha(M,N)\leqslant 4。单变量反Ackermann函数写成log^{*}N,是N的直到N\leqslant 1的取对数的次数,log^{*}65535= 4log^{*}2^{65536}= 5\alpha(M,N)增长的比log^{*}N还慢,不过不是常数,导致时间不是线性的

    结论:使用路径压缩和按秩求并,任意顺序的M=\Omega (N)次Union/Find操作花费的时间是O(Mlog^{*}N)

    分析:Union和Find操作可以以任何顺序出现,Union按秩进行,Find使用路径压缩

    引理1:执行一系列Union指令时,一个秩为r的节点必然至少有2^{r}个后裔,包括自己

    证明:数学归纳法

    引理2:秩为r的节点的个数最多是N/2^{r}

    证明:秩为r的节点至少有2^{r}个子节点,一共N个节点,所以得到这个个数

    引理3:在Union/Find算法的任一时刻,从树叶到根的路径上的节点的秩单调增加

    证明:显然

    记账法则:对于从代表i的定点到根的路径上的所有顶点v,在两个账户之一存入一个分币:

    法则1.若v是根,或者v的父亲是根,或者v的父亲和v在不同的秩组中,那么将一个美分存入公共储金

    法则2.否则,将一个canada分币存入该顶点中

    引理4:对任意的find(v),无论存入总储金还是存入顶点,所存分币总数恰好等于从v到根的路径上的节点数

    证明:显然

    引理5:经过整个算法,在法则1下美分存入的总的数量是M(G(N)+2)

    证明:对于任意find,有根和根的儿子,有2个,由于一个路径上节点的秩单调递增,一共G(N)个秩组,因此一共还可以放G(N)个,M次find总的数量就是M(G(N)+2)

    引理6:秩组g > 0中顶点的个数V(g)至多为N/2^{F(g-1)}

    证明:由引理2,至多存在N/2^{r}个秩为r的节点,对秩组g中的秩求和,得到

    V(g)\leqslant \sum_{r=F(g-1)+1}^{F(g)}\frac{N}{2^{r}}

              \leqslant \sum_{r=F(g-1)+1}^{\infty }\frac{N}{2^{r}}

              \leqslant N\sum_{r=F(g-1)+1}^{\infty }\frac{1}{2^{r}}

              \leqslant \frac{N}{2^{F(g-1)+1}}\sum_{s=0}^{\infty }\frac{1}{2^{s}}

              \leqslant \frac{2N}{2^{F(g-1)+1}}

              \leqslant \frac{N}{2^{F(g-1)}}

    引理7:存入秩组g的所有顶点的canada分币的最大的个数至多是NF(g)/2^{F(g-1)}

    证明:秩组g中有F(g)-F(g-1)个节点,应用引理6得到结果

    引理8:在法则2下存入分币最多是N\sum_{g=1}^{G(N)}F(g)/2^{F(g-1)}个canada分币

    证明:显然

    综上,法则1和法则2总的分币数是M(G(N)+2)+N\sum_{g=1}^{G(N)}F(g)/2^{F(g-1)}

    定理:M次Union和Find的运行时间是O(Mlog^{*}N)

    证明:F是F(0) = 0F(i)=2^{F(i-1)}递归定义的函数,G(N)=1+\left \lfloor log^{*}N \right \rfloor,将F和G定义插入到引理8中,得到结论

    展开全文
  • 2.17 C语言中和Pascalwith等价的语句吗? 2.18 既然数组名可以用作数组基地址,为什么对结构不能这样? 2.19 程序运行正确,但退出时却“coredump”(核心转储)了,怎么回事? 联合 2.20 结构和联合什么...
  • 等价类而不是单个元素参与差别矩阵构造,得到一种简化代数约简差别矩阵。从差别矩阵角度讨论了代数约简和条件信息熵约简核属性计算问题,指出代数约简核属性是信息熵约简核属性子集。证明了分布协调集...
  • 第7章 使用ER到关系的映射和EER到关系的映射进行关系数据库设计 147 7.1 使用ER到关系的映射进行关系数据库设计 147 7.1.1 ER到关系的映射算法 147 7.1.2 ER模型构造映射的讨论和总结 151 7.2 EER...
  • 2.17 C语言中和Pascalwith等价的语句吗? 29 2.18 既然数组名可以用作数组基地址,为什么对结构不能这样? 29 2.19 程序运行正确,但退出时却“core dump ”(核心转储)了,怎么回事? 29 联合 30 2.20...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    2.17 C语言中和Pascalwith等价的语句吗? 29 2.18 既然数组名可以用作数组基地址,为什么对结构不能这样? 29 2.19 程序运行正确,但退出时却“core dump ”(核心转储)了,怎么回事? 29 联合 30 2.20...
  • CruiseYoung提供详细书签电子书籍目录 http://blog.csdn.net/fksec/article/details/7888251 数据库系统基础:高级篇(第5版)(讲述数据库系统原理经典教材) 基本信息 原书名: Fundamentals of Database ...
  • EL表达式详细使用

    2011-04-01 11:12:51
    它是一种简单语言,基于可用命名空间(PageContext 属性)、嵌套属性和对集合、操作符(算术型、关系型和逻辑型)访问符、映射到 Java 类中静态方法可扩展函数以及一组隐式对象。 EL 提供了在 JSP 脚本编制...
  • Sqlite 一款轻型数据库,是遵守ACID的关系型数据库管理系统,它包含在一个相对小C库中 W3C 万维网联盟,创建于1994年,是Web技术领域最具权威和影响力国际中立性技术标准机构。主要工作是发展 Web 规范,...
  • LINGO软件学习

    2009-08-08 22:36:50
    不同集类型的关系见下图。 §3 模型数据部分和初始部分 在处理模型数据时,需要为集指派一些成员并且在LINGO求解模型之前为集某些属性指定值。为此,LINGO为用户提供了两个可选部分:...
  • 总是搞不清楚指针、引用、数组、数组指针、指针数组等等一堆东西之间的关系和用法,学习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];将参数声明为数组的引用当参数是一个数组类型的引用时数组长度成为参数和实参类型的一部分编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配

     

    、指针和引用作为参数的优缺点,以及何决定使用:
    两种参数都允许函数修改实参指向的对象,两种类型的参数都允许有效地向函数传递大型类对象
    指针可能指向一个对象或没有任何对象所以函数在确定指针实际指向一个有效的对象之前不能安全地解引用一个指针;对于引用参数函数不需要保证它指向一个对象引用必须指向一个对象甚至在我们不希望这样时也是如此。
    如果一个参数可能在函数中指向不同的对象或者这个参数可能不指向任何对象则必须使用指针参数;引用参数的一个重要用法是它允许我们在有效地实现重载操作符的同时还能保证用法的直观性

    展开全文
  • 你必须知道495个C语言问题(PDF)

    热门讨论 2009-09-15 10:25:47
    1.13 以下的初始化什么区别?char a[] = "string literal"; char *p = "string literal"; 当我向p[i] 赋值时候, 我程序崩溃了。. . . . 5 1.14 我总算弄清除函数指针声明方法了, 但怎样才能初始化呢? . . 5...
  • 软件测试规范

    2018-04-23 09:16:12
    1.等价类划分 .......................................................................................................................................... 7 2.因果图 ........................................
  • 我们设想有以下特征 <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)集中式结构 集中式系统由一台...
  • o 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...
  • 该定理证明可参见参考文献2],由于和本文主题关系不大,这 里略厶。 设p(x)=∑=0Cnx,P(M)=0即∑:0Cm-M=0,两边乘M得∑=0CnM+!=0 即∑0c;M件+=0。所以{c,C1…cn}即为数列{l,M,M2,M3……}一个阶数为n线性 递推...
  • 著名的有美国 IBM 公司的 DBZ 关系数据库管理系统和 IMS 层次数据库管理系统、美国 Oracle 公司的 orade 关系数据库管理系统、 s 油 ase 公司的 s 油 ase 关系数据库管理系统、美国微软公司的 SQL Serve ,关系...
  • 著名的有美国 IBM 公 司的 DBZ 关系数据库管理系统和 IMS 层次数据库管理系统、美国 Oracle 公司的 orade 关系数据库管理系统、 s 油 ase 公司的 s 油 ase 关系数据库管理系统、美国微软公司的 SQL Serve ,关系...
  • 一般而言,一个行之有效数据库加密技术主要有以下6个方面功能和特性。 (1)身份认证: 用户除提供用户名、口令外,还必须按照系统安全要求提供其它相关安全凭证。如使用终端密钥。 (2) 通信加密与完整性保护...
  • 各种无符号类型量所占的内存空间字节数与相应的有符号类型量相同。但由于省去了符号位,故不能表示负数。 下表列出了Turbo C中各类整型量所分配的内存字节数及数的表示范围。 类型说明符 数的范围 分配字节数 int -...
  •  等价的设备名称是:  DeviceHardDisk0Partition1  范例  下例将物理设备名映射为使用 ARC 设备名称驱动器号:  map arc  注意 如果不使用 arc 参数,则 map 命令显示设备名称。 map 命令还显示文件...
  • write,read把数据从内核缓冲区复制到进程缓冲区,write把数据从进程缓冲区复制到内核缓冲区,它们不等价于数据在内核缓冲区和磁盘之间交换。 <p><img alt="" src=...
  • 事务处理原理 第2版

    热门讨论 2012-12-30 10:49:38
     本书介绍事务处理,旨在满足广大读者需要,包括以下读者。  ·兴趣构建事务处理应用程序应用程序编程人员。  ·管理用于事务处理数据库系统数据库管理员。  ·设计要部署在事务处理系统上应用...

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

以下关系不是等价关系的有