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

作     者：徐章艳 杨炳儒 蔡卫东 崔巍 谷冬元 XU Zhang-yan;YANG Bing-ru;CAI Wei-dong;CUI Wei;GU Dong-yuan

作者机构：广西师范大学计算机系广西桂林541004 北京科技大学信息工程学院北京100083 北京科技大学管理学院北京100083 

出 版 物：《系统工程与电子技术》 (Systems Engineering and Electronics)

年 卷 期：2006年第28卷第12期

页      面：1902-1905,1931页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家科技成果重点推广计划(2003EC000001)资助课题 

主　　题：粗糙集 正区域 简化差别矩阵 核 复杂度 

摘      要：现有利用差别矩阵设计的基于正区域的求核算法,其时间复杂度为O(|C‖U|2)。为降低求核算法的时间复杂度,给出了简化差别矩阵的定义和基于简化差别矩阵核的定义,并证明了该核与基于正区域的核是等价的。由于求简化差别矩阵的关键是求划分U/C,故利用基数排序的思想设计了一个快速求划分U/C的算法,其时间复杂度为O(|C‖U|)。在此基础上,利用简化差别矩阵设计了一个基于正区域的快速求核算法,其时间复杂度降为max{O(|C‖U|),O(|C‖U/C‖Up′os)}。实例说明了新算法的有效性。