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

doi:10.3778/j.issn.1002-8331.2009.02.013

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (2): 48-50.DOI: 10.3778/j.issn.1002-8331.2009.02.013

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

农修德^1,2,徐章艳^1,3,阮慎¹,杨炳儒³

1.广西师范大学计算机系，广西桂林 541004
2.广西南宁师范高等专科学校数计系，广西崇左 532200
3.北京科技大学信息工程学院，北京 100083

收稿日期:2008-07-22 修回日期:2008-10-13 出版日期:2009-01-11 发布日期:2009-01-11
通讯作者: 农修德

Counting method—novel algorithm for computing partition

NONG Xiu-de^1,2,XU Zhang-yan^1,3,RUAN Shen¹,YANG Bing-ru³

1.Department of Computer，Guangxi Normal University，Guilin，Guangxi 541004，China
2.Department of Mathematics and Computer Science，Guangxi Nanning Normal College，Chongzuo，Guangxi 532200，China
3.College of Information Engineering，Science and Technology University of Beijing，Beijing 100083，China

Received:2008-07-22 Revised:2008-10-13 Online:2009-01-11 Published:2009-01-11
Contact: NONG Xiu-de

摘要/Abstract

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

关键词: 粗糙集, 等价类, 划分, 计数法

Abstract: At present，the algorithm for computing partition based on radix sorting has lower time complexity than the others，but it also has the following shortcomings：it will create a lot of idle storage when there is a big increment between two attribution value；for computing the partition，its time complexity is as high as O（|P‖U|） after sorting.For improving the efficiency of computing partition，a novel algorithm for computing partition is designed.It does not create a lot of idle storage by mapping the attribution values to sequential natural number.And it records the length of equivalence classes to compute the partition by defining a count array.Its time complexity is as only low as O（|U|）.The time complexity of the new algorithm is O（|C‖U|），the space complexity is O（|U|）.It offers a new method for computing the partition of the universe U.

Key words: rough set, equivalence class, partition, counting method

农修德^1,2,徐章艳^1,3,阮慎¹,杨炳儒³. 新的等价类划分算法—计数法[J]. 计算机工程与应用, 2009, 45(2): 48-50.

NONG Xiu-de^1,2,XU Zhang-yan^1,3,RUAN Shen¹,YANG Bing-ru³. Counting method—novel algorithm for computing partition[J]. Computer Engineering and Applications, 2009, 45(2): 48-50.

[1]	高天宇，王庆荣，杨磊. 粗糙集属性依赖度强化的应急数据挖掘模型[J]. 计算机工程与应用, 2021, 57(3): 87-93.
[2]	王庆荣，马辰坤. 面向案例消耗推理的应急物资预测[J]. 计算机工程与应用, 2021, 57(22): 281-287.
[3]	张可铧，成卫青. 基于空间动态划分的差分隐私聚类算法[J]. 计算机工程与应用, 2021, 57(2): 97-103.
[4]	刘玉锋，孙文鑫. 一般多粒度量化软粗糙集模型[J]. 计算机工程与应用, 2021, 57(12): 137-143.
[5]	刘桂枝. 维度变化的不完备混合型数据增量式属性约简[J]. 计算机工程与应用, 2021, 57(12): 161-169.
[6]	刘艺，张起贵. 划分层次限制的快速帧间预测算法[J]. 计算机工程与应用, 2021, 57(10): 200-203.
[7]	杜宏伟，乔美丽，宋刚，张云峰，包芳勋. 基于视觉感知的图像放大[J]. 计算机工程与应用, 2020, 56(9): 204-212.
[8]	王安，顾益军. 基于社区划分的节点重要性评估方法[J]. 计算机工程与应用, 2020, 56(8): 42-48.
[9]	王文慧，李鹏，胡韵迪. 基于目标预测的扩展目标量测集划分算法[J]. 计算机工程与应用, 2020, 56(8): 143-148.
[10]	康雁，李浩，梁文韬，宁浩宇，霍雯. 针对文本情感分类任务的textSE-ResNeXt集成模型[J]. 计算机工程与应用, 2020, 56(7): 205-209.
[11]	张博，贾华宇，马珺. RS-GA神经网络无人机受风情况估计[J]. 计算机工程与应用, 2020, 56(4): 209-213.
[12]	牟恩，张贤勇，姚岳松，邓切. 邻域近似条件熵的特定类属性约简及启发算法[J]. 计算机工程与应用, 2020, 56(24): 175-180.
[13]	张建华，李方方，杨岚. 融合PFS与RS的案例知识供需匹配研究[J]. 计算机工程与应用, 2020, 56(23): 139-145.
[14]	黄胜，李萌芳，张倩云. 基于背景帧的监控和会议视频帧间快速算法[J]. 计算机工程与应用, 2020, 56(22): 205-210.
[15]	骆公志，梅焘. 监督机制多粒度决策粗糙集模型及应用[J]. 计算机工程与应用, 2020, 56(18): 214-220.

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

Counting method—novel algorithm for computing partition

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics