一种基于数组的高效等价类划分算法  

An Efficient Equivalence Partitioning Algorithm Based on Array

作　　者：樊艳英[1] 张自敏[2] 陈冠萍[1] FAN Yan-ying, ZHANG Zi-min, CHEN Guan-ping （1.College of computer and Information Engineering, HeZhou University, Hezhou 542899, China; 2.Multimedia Technology Center, HeZhou University, Hezhou 542899, China）

机构地区：[1]贺州学院计算机与信息工程学院,广西贺州542899 [2]贺州学院多媒体技术中心,广西贺州542899

出　　处：《电脑知识与技术》2016年第1期74-76,共3页Computer Knowledge and Technology

基　　金：2013贺州学院教学改革项目“《asp.net程序设计》课程教学改革探讨”（编号：hzxyjg201316）

摘　　要：粗糙集理论是建立在等价类的基础上的,等价类划分算法的优劣会直接影响到属性约简和规则提取的效率.针对等价类基数排序算法中存在重复计算和空间开销较大的问题,提出了一种基于数组的等价类划分算法.算法的时间复杂度为O（｜U｜｜C｜）,空间复杂度为O｜U｜.最后通过具体案例验证了算法的执行过程。结果表明算法高效且正确可行。Rough set theory is based on Equivalence class, The good and bad of equivalence partitioning algorithm will directly affect the efficiency of the attribute reduction and rule extraction.Aiming at the problem of duplicate computing and large space overhead existed in the equivalence class of Radix Sort, propose an equivalence partitioning algorithm based on array.The time complexity of the algorithm is O （｜U｜｜C｜）, The space complexity is O｜U｜. Finally, verify the process of algorithm by specific examples. The results show that the algorithm is correct and feasible

关 键 词：粗糙集 属性约简 等价类划分 基数排序 规则提取 

分 类 号：TP18[自动化与计算机技术—控制科学与工程;自动化与计算机技术—控制理论与控制工程]