计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
2期
48-50,54
,共4页
农修德%徐章艳%阮慎%杨炳儒
農脩德%徐章豔%阮慎%楊炳儒
농수덕%서장염%원신%양병유
粗糙集%等价类%划分%计数法
粗糙集%等價類%劃分%計數法
조조집%등개류%화분%계수법
目前,基于基数排序的等价类划分算法有较低的时间复杂度但存在以下不足:属性值跳跃性大时会产生大量空队列;排序后仍需O(|P||I|)的时间才实现划分,求出等价类,排序没能发挥应有作用.为此,设计了一种新算法,通过属性值映射避免大量空队列产生,通过增加一个记录等价类长度信息的计数数组,排序后仅需O(|U|)就可实现划分,求出等价类.整个算法时间复杂度为O(|C||U|),空间复杂度为O(|U|),为求等价类划分提供了一个新的解决办法.
目前,基于基數排序的等價類劃分算法有較低的時間複雜度但存在以下不足:屬性值跳躍性大時會產生大量空隊列;排序後仍需O(|P||I|)的時間纔實現劃分,求齣等價類,排序沒能髮揮應有作用.為此,設計瞭一種新算法,通過屬性值映射避免大量空隊列產生,通過增加一箇記錄等價類長度信息的計數數組,排序後僅需O(|U|)就可實現劃分,求齣等價類.整箇算法時間複雜度為O(|C||U|),空間複雜度為O(|U|),為求等價類劃分提供瞭一箇新的解決辦法.
목전,기우기수배서적등개류화분산법유교저적시간복잡도단존재이하불족:속성치도약성대시회산생대량공대렬;배서후잉수O(|P||I|)적시간재실현화분,구출등개류,배서몰능발휘응유작용.위차,설계료일충신산법,통과속성치영사피면대량공대렬산생,통과증가일개기록등개류장도신식적계수수조,배서후부수O(|U|)취가실현화분,구출등개류.정개산법시간복잡도위O(|C||U|),공간복잡도위O(|U|),위구등개류화분제공료일개신적해결판법.
