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

摘要：

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

关键词：粗糙集、等价类、划分、计数法

所属期刊栏目：45

分类号：TP311(计算技术、计算机技术)

资助基金：广西教育科研立项项目200707LX037,200606LX026

在线出版日期：2009-03-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：48-50,54