algorithm - 二叉堆稠密图上的 Dijkstra 线性运行时间

Question

首先:Dijkstras最短路径算法一般运行时间为

其中 m 是边数，n 是顶点数

其次:预期的减少键操作次数如下

第三:dijkstra 的预期运行时间是二叉堆，允许所有操作在 log(n) 时间内

但是，如果我们认为图是稠密的，那么为什么稠密图的运行时间是线性的

有人可以在这里帮助进行 O 表示法和对数计算吗？

Answer 1

首先不难证明如果 m 是 n log(n) log(log(n)) 的大 omega 那么 log( n) 是 log(m) 的大欧米茄。因此，您可以证明 m 是 n log(m) log(log(m)) 的大 omega。

由此您可以证明 n 是 m/(log(m) log(log(m))) 的大 omega。

将其代回第三点中的表达式，我们得到预期运行时间为:

O(m + n log(m/n) log(n))

                   m                                                 m
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------)
             log(m) log(log(m))                              log(m) log(log(m))

从这里您可以将所有产品日志扩展为日志总和。你会得到很多条款。然后这只是一个证明每个人都是 O(m) 或 o(m) 的问题。这很简单，但很乏味。