-
高效的信息表求核算法—兄弟判断法
- 农修德 徐章艳
-
2009, 29(08):
2230-2263.
-
摘要
(
)
PDF (542KB)
(
)
-
相关文章 |
计量指标
目前的求核算法大多基于决策表,基于信息表的很少。为此,先寻求理论依据,说明了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|)。算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题。通过实例验证了算法的有效性。