计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2009年
5期
1201-1203,1206
,共4页
粗糙集%等价类%正区域%可分辨矩阵%核
粗糙集%等價類%正區域%可分辨矩陣%覈
조조집%등개류%정구역%가분변구진%핵
目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.
目前求覈算法存在以下不足:求得的覈與基于正區域的覈不一緻,算法的時間和空間複雜度不理想.針對上述問題,提齣一種簡化的可分辨矩陣的定義和求覈方法,併證明瞭由該方法穫得的覈與基于正區域的覈是等價的.為瞭提高算法效率,採用分佈計數的基數排序思想設計等價類U/C劃分算法,其時間複雜度為O(|C||U|).在此基礎上,給齣快速求覈算法,其時間和空間複雜度分彆降為max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最後,實例說明瞭算法的有效性.
목전구핵산법존재이하불족:구득적핵여기우정구역적핵불일치,산법적시간화공간복잡도불이상.침대상술문제,제출일충간화적가분변구진적정의화구핵방법,병증명료유해방법획득적핵여기우정구역적핵시등개적.위료제고산법효솔,채용분포계수적기수배서사상설계등개류U/C화분산법,기시간복잡도위O(|C||U|).재차기출상,급출쾌속구핵산법,기시간화공간복잡도분별강위max{O(|C||U/C|2),O(|C||U|)}화O(|C||U/C|2).최후,실례설명료산법적유효성.
