基于正区域的快速求核算法

基于正区域求核算法的最好时间复杂度为O(|C|2|U|log|U|),为降低该求核算法的时间复杂度,给出了基于正区域的简化决策表定义和相应核的定义.证明了该简化决策表的核与原决策表的核等价.由于求正区域的简化决策表首先要求划分U/C,而求划分U/C的最好算法的时间复杂度为O(|C||U|log|U|),因此以基数排序的思想设计了一个新的求划分U/C的算法,其时间复杂度为O(|C||U|).最后以快速缩小搜索空间为目的设计了一个新的求正区域POSC(D)的算法.在此基础上,利用核的性质设计了一个新的求核算法,其时间复杂度为max(O(|C||U|,O(|C|2|U/C|)).并用实例说明了算法的实用性.

An efficient algorithm for computing core based on positive region

At present,the time complexity of the best algorithm for computing core based on positive region is O(|C|2|U|log|U|).For reducing the computational complexity,simplified decision table for positive region and corresponding core were introduced at first.At the same time,it was proved that this core was equal to the core of the old decision table.Since it was first to compute the partition U/C before computing the simplified decision table for positive region.However the time complexity of the best algorithm for computing U/C was O(|C||U|log|U|).The idea of cardinal ordering was used to design a new algorithm for computing partition U/C with time complexity O(|C||U|).On the other hand,to reduce the space complexity,a new algorithm for computing the positive region POSC(D) was also proposed. Then based on the above definition and algorithms,a new algorithm for computing core was presented,whose time complexity was max(O(|C||U|,O(|C|2|U/C|)).Finally,an example was used for illustrating the proposed algorithms.