Abstract: To cut down the time and space complexity and improve the efficiency of the attribute reduction algorithm based on Skowron's discernibility matrix, the definitions of a simplified discernibility matrix and corresponding attribute reduction were provided. It is proved that attribute reduction based on the simplified discernibility matrix is equivalent to that based on the old one. By the foundation of a simplified decision table, a function which can measure the frequency of a condition attribute in the simplified discernibility matrix was defined. An algorithm for the above function was designed. Its time and space complexity are O (|U/C|). Then an efficient algorithm of attribute reduction based on Skowron's discernibility matrix was designed with the new function. Its time complexity is cut down to O(|C||U|) + O(|C|²|U/C|), and space complexity to O(|U|). Finally, an example was used to illustrate the effectiveness of the new algorithm.