《表1 各算法时间复杂度比较》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《PMC模型下网络故障的节点可诊断研究》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

1974年Hakimi等人[2]提出了PMC模型下的t-可诊断的充要条件，在此基础上，Dahbura等人[5]提出了O（N2.5）的t-可诊断算法；区别于t-可诊断，t/t-可诊断要求系统中所有故障节点能被孤立在一个容量不超过t的节点集中。相对于t-可诊断，它允许有正确节点被误诊为故障，但保证所有故障节点都能被诊断出。Chwa等人[18]提出了PMC模型下的t/t-可诊断的充要条件，Yang等人[19]在此基础上提出了O（N2.5）的可诊断算法。另外，在不同于PMC模型的MM模型下，Sengupta等人提出了t-可诊断的充要条件并给出了MM*下的O（N5）诊断算法，Yang等人[20]改进了该算法使之时间复杂度降至O（NΔδ3），其中Δ与δ分别代表节点最大度和最小度。各算法时间复杂度比较结果如表1所示。对比以上算法发现，算法STFDA时间复杂度仅有O（N log N），要远小于其他算法，因此算法的实现成本能够得以减小；另一方面，STFDA更简单实用，易于理解，实现起来要更加简单快捷。