algorithm - Dijkstra 斐波那契堆解决方案中的大 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 的大 O 与斐波那契堆是什么？

Answer 1

Dijkstra最短路径算法的复杂度为:

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

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

对于 Fibonacci 堆和二叉堆，此队列上的 extract-min 操作的复杂度为 O(log |V|)。这解释了常见的 |V|记录总和中的 |V| 部分。对于使用未排序数组实现的队列，extract-min 操作的复杂度为 O(|V|)(必须遍历整个队列)，这部分总和为 O(|V|^2)。

在总和的剩余部分(具有边缘因子 |E| 的部分)，O(1) v.s. O(log |V|) 区别恰恰来自分别使用 Fibonacci 堆而不是二进制堆。每条边都可能发生的减少键操作正是具有这种复杂性。因此，对于斐波那契堆，总和的剩余部分最终具有复杂度 O(|E|)，对于二叉堆，复杂度为 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)，如果不对所处理的图类型做出进一步假设，这些就无法进一步简化。