Quick computing core algorithm based on discernibility matrix
LI Long-shu · Jisuanji gongcheng yu sheji · 2009
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 prob- lems, firstly a definition of simple dicernibility matrix and the method of computing core are provided. It is proved that the core is equiva- lent 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.