高效的信息表求核算法--兄弟判断法

基于信息表的求核算法存在如下不足:需要完整求出U/R后方可求核。为此,先寻求理论依据,说明U/R与U/(R-{a})的内在关系,得出了[x]R-{a}/{a}细分[x]R-{a}的结论,证明了U/(R-{a})≠U/R与"U/R元素有兄弟"的等价性。然后基于二叉树设计思想,用兄弟存储结构设计了一个新的信息表求核算法,仅需生成较小的二叉树就能求核,时间复杂度和空间复杂度分别为O(|C|2|U|)和O(|U|)。算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题。通过实例验证了算法的有效性。