%0 Journal Article %A 鲍忠贵 %A 杨鹏 %A 赵辉 %T 基于双十字链表存储的共享资源矩阵方法特性研究 %D 2016 %R 10.11772/j.issn.1001-9081.2016.03.653 %J 计算机应用 %P 653-656 %V 36 %N 3 %X 针对共享资源矩阵法在系统隐蔽通道检测过程中存在的算法时间复杂度高的问题,提出了一种基于双十字链表存储的改进算法。首先,针对共享资源矩阵方法中的核心操作——传递闭包操作,将传统的数组存储改进为双十字链表存储;其次,针对共享资源矩阵方法建立了概率模型;最后,在该概率模型下,分析了改进算法的时间复杂度和共享资源矩阵方法的特性。理论分析和实验仿真表明:当共享资源矩阵为稀疏矩阵时,采用基于双十字链表存储的改进算法能够使共享资源矩阵法的时间效率相比传统的数组存储提高67%;当共享资源矩阵的规模较大时,传递闭包操作会使得共享资源矩阵中的元素快速填充,从而导致基于双十字链表存储改进算法相比传统数组存储的时间效率优势下降,并在概率模型下通过理论推导验证了传递闭包操作的这一特性。 %U http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2016.03.653