Quick Algorithm for Computing Core Based on Information Entropy
Zhangyan Xu · Journal of Chinese Computer Systems · 2007
At present, the time complexity of the best algorithm for computing core based on information entropy is O(｜C｜2｜U｜log｜U｜). For cutting down the time complexity, the definition of simplified discernibility matrix based on information entropy and the corresponding definition of core are first provided. At the same time, it is proved that this core is the same as the core based on information entropy. Then a new algorithm based on radix sorting for computing U/C is designed, its time complexity is O(｜C｜｜U｜). On this condition, a new algorithm for computing core is designed, and its time complexity is cut down to max{O(｜C｜｜U/C｜2),O(｜C｜｜U｜)}. At the end, an example is used to illustrate the efficient of this new algorithm.