摘要： 利用顺序表存储数据集对象，并借助基数排序按关键字“分配”思想，求解U/C的时间复杂度为 、空间复杂度为O(U)。在求属性约简集时，为避免存储差别矩阵所需的大量空间，利用差别矩阵的直观性，给出一种计算差别对象个数公式，并以此为启发信息，设计2种动态约简算法，其时间/空间复杂度分别为 、max( )。理论分析与实验结果表明该算法是有效可行的。

关键词: 粗糙集, 属性重要性, 差别矩阵, 顺序表, 启发式

Abstract: Using order list to store data set objects and borrowing the idea of allocation by keys in radix sorting, its time and space complexity for U/C is and O(U) respectively. To avoid large space to store discernibility matrix and use the intuition of it, a expressions to compute the number of discernibility objects is presented when computing attribute reduction sets. Two algorithms are designed with time and space complexity only and max( ). Theoretical analysis and experimental results show that the algorithm is effective and feasible.

Key words: rough set, attribute importance, discernibility matrix, order table, heuristic

中图分类号: 

• TP311