Dijkstra算法问题
题目
Dijkstra算法问题
求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则当图的顶点数为40时,计算时间为多少ms?
请写出具体分析,谢谢
答案
dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10)=10ms
那么k(40×40)=16[k×(10×10)]=160ms
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点