基于可分辨矩阵的快速求核算法

摘要

目前求核算法存在以下不足:求得的核与基于正区域的核不一致,算法的时间和空间复杂度不理想.针对上述问题,提出一种简化的可分辨矩阵的定义和求核方法,并证明了由该方法获得的核与基于正区域的核是等价的.为了提高算法效率,采用分布计数的基数排序思想设计等价类U/C划分算法,其时间复杂度为O(|C||U|).在此基础上,给出快速求核算法,其时间和空间复杂度分别降为max{O(|C||U/C|2),O(|C||U|)}和O(|C||U/C|2).最后,实例说明了算法的有效性.