计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (6): 4-.

• 博士论坛 • 上一篇    下一篇

一个基于差别矩阵的快速求核算法

徐章艳,杨炳儒,宋威   

  1. 桂林市广西师范大学计算机系
  • 收稿日期:2005-11-01 修回日期:1900-01-01 出版日期:2006-02-21 发布日期:2006-02-21
  • 通讯作者: 徐章艳 xyzwlx xyzwlx

Quick Computing Core Algorithm Based on Discernibility Matrix

Xu Zhang-yan,,   

  1. 桂林市广西师范大学计算机系
  • Received:2005-11-01 Revised:1900-01-01 Online:2006-02-21 Published:2006-02-21
  • Contact: Xu Zhang-yan

摘要: 给出简化差别矩阵和相应核的定义,并证明该核与差别矩阵的核是等价的.在此基础上设计了一个新的求核算法,使得新算法的时间复杂度和空间复杂度分别被降为 max{O(|C||U/C||U/C|),O(|C||U|)}和max{O(|C||U/C||U/C|),O(|U|)} .

关键词: 粗糙集, 差别矩阵, 简化差别矩阵, 核, 复杂度

Abstract: In this paper, the definition of a simply discernibility matrix and correspondence core are provided. It is proved that this core is the core of the discernibility matrix. On the foundation, a new computing core algorithm is designed, and the time complexity and space complexity of the new algorithm are cut down max{O(|C||U/C||U/C|),O(|C||U|)} and max{O(|C||U/C||U/C|),O(|U|)}respectively.

Key words: Rough set, Dicernibility matrix, Simply discernibility matrix, Core, Complexity