Dijkstra Fibonacci堆解决方案的大O.

Dijkstra最短路径算法的复杂性是:

    O(|E| |decrease-key(Q)| + |V| |extract-min(Q)|)

其中Q介于最低优先级队列可以通过当前距离估计订货顶点.

对于Fibonacci堆和二进制堆,此队列上的extract-min操作的复杂性是O(log |V|).这解释|V| log |V|了总和中的共同部分.对于使用未排序数组实现的队列,extract-min操作将具有复杂性O(|V|)(必须遍历整个队列)并且这部分总和将是O(|V|^2).

在和的剩余部分(具有边缘因子| E |的部分)中,O(1)vs O(log |V|)差别恰好来自分别使用Fibonacci堆而不是二进制堆.每个边缘可能发生的减少键操作恰好具有这种复杂性.因此,总和的剩余部分最终具有O(|E|)Fibonacci堆和O(|E| log |V|)二进制堆的复杂性.对于具有未排序的阵列实现的队列,减少键操作将有一个恒定的时间复杂度(队列直接存储由顶点索引的键)和总和因此是这部分O(|E|),这也是O(|V|^2).

总结一下:

斐波纳契堆: O(|E| + |V| log |V|)

二进制堆: O((|E| + |V|) log |V|)

未排序的数组: O(|V|^2)

因为,在一般情况下|E| = O(|V|^2),如果不对所处理的图的种类做出进一步的假设,就不能进一步简化这些.