Dijkstra Fibonacci-heap解上的大O

Question

来自Wikipedia：O(|E| + |V| log|V|)

来自Big O Cheat List：O((|V| + |E|) log |V|)

我认为E + V log V和(E+V) log V是有区别的，不是吗？

因为，如果维基百科的一个是正确的，那么它不应该只显示为O(|V| log |V|) (删除|E|)，原因我不明白吗？)

Dijkstra和Fibonacci-Heap的大O是什么？

Answer 1

Dijkstra的最短路径算法的复杂度是：

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

其中Q是根据顶点的当前距离估计对顶点进行排序的最小优先级队列。

对于斐波那契堆和二进制堆，此队列上的提取-最小操作的复杂度均为O(log |V|)。这解释了sum中的公共|V| log |V|部分。对于使用未排序数组实现的队列，提取最小操作的复杂度将为O(|V|) (必须遍历整个队列)，并且这部分和将为O(|V|^2)。

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

总结一下：

数组Fibonacci堆：O(|E| + |V| log |V|)

• binary堆：O((|E| + |V|) log |V|)

• unsorted

• ：O(|V|^2)

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

Answer 2

Dijkstra的是O(|E| + |V| log|V|)和O((|V| + |E|) log |V|)。

两者在某种程度上都是正确的。大O作弊列表显示了最常见的实现和最好的Wiki。

O(|E| + |V| log|V|)不在O(|V| log|V|) btw中。E在O(|V|^2)中，而不是O(|V| log|V|)中。