我根据维基百科 (http://en.wikipedia.org/wiki/Dijkstra 's_algorithm) 上的伪代码编写了 Dijkstra 算法的实现，该算法使用带最小堆的优先级队列。该图用邻接矩阵表示(就像伪代码一样)。当我要测试它以查看运行时间时，我想我需要一些大图来测试，所以我随机生成了一些大小为 n 的图(尽管我用来生成图的方法可能很糟糕) .
现在，根据维基百科，此实现的复杂度为:O((|V|+|E|) log |V|)。
当我在 V = 1000 上运行算法时，例如一个有 1000 个节点的图(虽然我不知道有多少条边)，平均需要大约 800 毫秒。当我将 V = 2000 的图形大小加倍时，大约需要 1700 毫秒，而当我将其加倍 (V = 4000) 时，大约需要两倍的时间。
所以我的问题是(我知道我的计算机也在时间测量中发挥了一定作用)，运行时间不应该更快吗？这些测量是否合理？
最佳答案
这些测量是合理的；然而，运行时复杂度既是最坏情况又是渐进的。事实上，最有用的方法是评估实际达到最坏情况的实例的运行时间，以通过实验估计运行时复杂度。
关于algorithm - Dijkstra 算法的运行时间测量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25527403/