一种构造Hasse图的高效算法  

An Efficient Algorithm to Construct Hasse Diagram

作　　者：王善坤[1] 

机构地区：[1]大连理工大学城市学院网络信息中心,辽宁大连116600

出　　处：《大连民族学院学报》2012年第1期43-45,共3页Journal of Dalian Nationalities University

摘　　要：目前在国内外的文献上,关于Hasse图的构造方法都是基于纯粹的数学矩阵变换方法,而非计算机算法,其缺点是不论最好还是最坏情况,其时间复杂度都是0(n3),进而无法为特殊情况作出优化。为此给出一种构造Hasse图的通用高效算法。该方法从计算机算法的角度对矩阵中单个元素进行计算,当矩阵中所需计算的元素较少时,算法的时间复杂度会相应的降低,在最好的情况下,时间复杂度将接近0(n2),而在最坏的情况下,时间复杂度仍保持在0(n3)。In domestic and foreign literature, the way to construct Hasse Diagram is researched only based on pure mathematic conversion of Matrix not computer algorithm. However, no mat- ter in which case, the best or the worst, the time complexity of the algorithms is always con- stant, which is 0 （n3）, so some special case is difficult to be optimized. In this paper we pro- vide a general high efficient way to construct Hasse Diagram from the computer perspective, which some elements in matrix is processed in computer. When the elements to be worked on in matrix become less, the time complexity of calculation will decrease, which in the best case, the time complexity almost is equal to 0 （ n2 ）, while in the worst case, the time complexity still re- mains around 0 （ n3 ）

关 键 词：Hasse图 偏序集 偏序关系 算法 覆盖关系 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]