新的等价类划分算法-计数法

作     者：农修德 徐章艳 阮慎 杨炳儒 NONG Xiu-de;XU Zhang-yan;RUAN Shen;YANG Bing-ru

作者机构：广西师范大学计算机系广西桂林541004 广西南宁师范高等专科学校数计系广西崇左532200 北京科技大学信息工程学院北京100083 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2009年第45卷第2期

页      面：48-50,54页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：广西教育科研立项项目(No.200707LX037 No.200606LX026) 

主　　题：粗糙集 等价类 划分 计数法 

摘      要：目前,基于基数排序的等价类划分算法有较低的时间复杂度但存在以下不足:属性值跳跃性大时会产生大量空队列;排序后仍需O(|P‖U|)的时间才实现划分,求出等价类,排序没能发挥应有作用。为此,设计了一种新算法,通过属性值映射避免大量空队列产生,通过增加一个记录等价类长度信息的计数数组,排序后仅需O(|U)|就可实现划分,求出等价类。整个算法时间复杂度为O(|C‖U|),空间复杂度为O(|U)|,为求等价类划分提供了一个新的解决办法。