计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (7): 164-166.DOI: 10.3778/j.issn.1002-8331.2009.07.049

• 数据库、信号与信息处理 • 上一篇    下一篇

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

葛 浩1,3,杨传健2,李龙澍3   

  1. 1.滁州学院 电子信息工程系,安徽 滁州 239012
    2.滁州学院 计算机系,安徽 滁州 239012
    3.安徽大学 计算机学院,合肥 230039
  • 收稿日期:2008-01-21 修回日期:2008-04-14 出版日期:2009-03-01 发布日期:2009-03-01
  • 通讯作者: 葛 浩

Quick computing core algorithm based on binary discernibility matrix

GE Hao1,3,YANG Chuan-jian2,LI Long-shu3   

  1. 1.Department of Electronic and Information Engineering,Chuzhou University,Chuzhou,Anhui 239012,China
    2.Department of Computer Science,Chuzhou University,Chuzhou,Anhui 239012,China
    3.School of Computer Science,Anhui University,Hefei 230039,China
  • Received:2008-01-21 Revised:2008-04-14 Online:2009-03-01 Published:2009-03-01
  • Contact: GE Hao

摘要: 目前,求核算法存在以下不足:求得的核与正区域的核不一致,求核算法的时间复杂度和空间复杂度不理想。针对上述问题,给出一种二进制可分辨矩阵的定义及其求核性质,并证明了由该性质获得的核与正区域的核是等价的,然后设计求核算法,该算法的时间复杂度为max{O(|C||U/C|2),O(|C||U|)},空间复杂度为O(|C||U/C|2)。最后实例说明该方法的可行性和有效性。

Abstract: At present,the algorithms of the 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 are not good.Aiming at these problems,a binary discernibility matrix and correspondence property of computing core are provided.It is proved that the core acquired from the property is equivalent to the core based on positive region.Then,the computing core algorithm is designed,its time complexity is max{O(|C||U/C|2),O(|C||U|)},and its space complexity is O(|C||U/C|2).Finally,an example is given to explain the feasibility and availability of this method.