有限集拓扑验证算法的优化

• 作者: 梁立 陈玉华
• 来源期刊: 云南师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 有限集 拓扑 可行集簇 算法
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 计算机科学及应用
• 页码范围: 34-37
• 页数: 4页
• 分类号: TP301.6
• 字数: 3195字
• 语种: 中文
• DOI: 10.7699/j.ynnu.ns-2016-021

摘要

有限集合拓扑构建的基本算法是验证一个可行集簇是否为拓扑.验证算法就是检验可行集簇里的两两子集的交运算和并运算是否都封闭.利用拓扑占可行集簇的比例非常小,即不是拓扑的概率非常大的现象,又根据局部性原理,可将验证算法优化以可以大幅度减少检查封闭的运算量.对阶为k的可行集簇,验证算法的时间复杂度从O(k2)几乎降至O(1).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈玉华	云南师范大学信息学院	14	92	5.0	9.0
2	梁立	云南师范大学信息学院	75	313	10.0	15.0