摘要
目前求核算法存在以下不足:求得的核与基于正区域的核不一致、算法的时间和空间复杂度不理想。针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的。为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(│C││U)。在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(│C││U/C│2,O(C││U)}和O(│C││U/C│2)。最后,实例说明了算法的有效性。
At present, the algorithms for computing core have the following shortcomings： the core acquired from these algorithms is not the core based on positive region. The time complexity and space complexity of these algorithms are not good. Aiming at these problems, firstly a definition of simple dicernibility matrix and the method of computing core are provided. It is proved that the core is equivalent to the core based on positive region. In order to improve the efficiency of the algorithm, an efficient algorithm for computing U/C is designed with the idea of radix sorting based on distributing counting. It＇ s time complexity is O（｜ C｜ ｜U｜）. On this condition, a quick computing core algorithm is put forward. Its time complexity and space complexity are cut down max{O（│C││U/C│^2,O（C││U）} and O（│C││U/C│^2） .Finally, an example is used to explained the efficiency of the algorithm.
出处
《计算机工程与设计》
CSCD
北大核心
2009年第5期1201-1203,1206,共4页
Computer Engineering and Design
基金
安徽省自然科学基金项目(O50420204)
安徽高校省级自然科学研究基金项目(KJ2008B117)。
关键词
粗糙集
等价类
正区域
可分辨矩阵
核
rough set
equivalence class
positive region
dicemibility matrix
core
