Counting method—novel algorithm for computing partition

doi:10.3778/j.issn.1002-8331.2009.02.013

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (2): 48-50.DOI: 10.3778/j.issn.1002-8331.2009.02.013

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

通讯作者: 农修德

Abstract

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

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

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

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

[1]	GAO Tianyu, WANG Qingrong, YANG Lei. Data Mining Model Based on Attribute Dependability Enhancement of Rough Set [J]. Computer Engineering and Applications, 2021, 57(3): 87-93.
[2]	WANG Qingrong, MA Chenkun. Forecast of Emergency Supplies for Case Consumption Reasoning [J]. Computer Engineering and Applications, 2021, 57(22): 281-287.
[3]	ZHANG Kehua, CHENG Weiqing. Differential Privacy Clustering Algorithm Based on Spatial Dynamic Partition [J]. Computer Engineering and Applications, 2021, 57(2): 97-103.
[4]	LIU Suolan, GU Jiahui, WANG Hongyuan, ZHANG Yunpeng. Human Behavior Recognition Based on Associative Partition and ST-GCN [J]. Computer Engineering and Applications, 2021, 57(13): 168-175.
[5]	LIU Yufeng, SUN Wenxin. Generalized Multi-granulation Quantization Soft Rough Set Model [J]. Computer Engineering and Applications, 2021, 57(12): 137-143.
[6]	LIU Guizhi. Incremental Attribute Reduction of Incomplete Hybrid Data Based on Dimension Change [J]. Computer Engineering and Applications, 2021, 57(12): 161-169.
[7]	LIU Yi, ZHANG Qigui. Fast Inter-Frame Prediction Algorithm with Partition Level Limitation [J]. Computer Engineering and Applications, 2021, 57(10): 200-203.
[8]	WANG Wenhui, LI Peng, HU Yundi. Measurement Set Partitioning Algorithm for Extended Target Based on Target Prediction [J]. Computer Engineering and Applications, 2020, 56(8): 143-148.
[9]	LI Chao, DONG Xinhua, CHEN Jianxia. Asynchronous Iterative Updates Method Based on Subgraph in Spark [J]. Computer Engineering and Applications, 2020, 56(7): 67-73.
[10]	ZHANG Bo, JIA Huayu, MA Jun. Estimation of Air Condition for Unmanned Aerial Vehicle Based on RS-GA Neural Network [J]. Computer Engineering and Applications, 2020, 56(4): 209-213.
[11]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[12]	ZHANG Jianhua, LI Fangfang, YANG Lan. Research on Matching Supply and Demand of Case Knowledge Based on PFS and RS [J]. Computer Engineering and Applications, 2020, 56(23): 139-145.
[13]	HUANG Sheng, LI Mengfang, ZHANG Qianyun. Fast Inter Algorithm for Surveillance and Conference Video Based on Background Frame [J]. Computer Engineering and Applications, 2020, 56(22): 205-210.
[14]	LUO Gongzhi, MEI Tao. Multi-granulation Decision-Theoretic Rough Set Method Based on Supervisory Mechanism and Its Application [J]. Computer Engineering and Applications, 2020, 56(18): 214-220.
[15]	XIE Xuming, DUAN Longzhen, QIU Taorong, YANG Youfeng. Improved Quantum Search Algorithm and Its Application on Computation of Core [J]. Computer Engineering and Applications, 2020, 56(14): 57-61.

Counting method—novel algorithm for computing partition

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics