Dijkstra Fibonacci堆解决方案上的Big O [英] The Big O on the Dijkstra Fibonacci-heap solution

问题描述

来自维基百科: O(| E | + | V | log | V |)

来自 Big O作弊列表: O((| V | + | E |)log | V |)

我认为 E + V log V 和(E + V)log V 有区别吗?

因为，如果维基百科的是正确的，则不应仅将其显示为 O(| V | log | V |)(删除 | E | )因为我不明白的原因?)?

Because, if Wikipedia's one is correct, shouldn't it be shown as O(|V| log |V|) only then (Removing |E|) for a reason I do not understand?)?

Dijkstra的斐波那契堆的大O是什么?

What is the Big O of Dijkstra with Fibonacci-Heap?

推荐答案

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

The complexity of Dijkstra's shortest path algorithm is:

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

其中 Q 是根据其当前距离估算值的最小优先级队列排序顶点.

where Q is the min-priority queue ordering vertices by their current distance estimate.

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

For both a Fibonacci heap and a binary heap, the complexity of the extract-min operation on this queue is O(log |V|). This explains the common |V| log |V| part in the sum. For a queue implemented with an unsorted array, the extract-min operation would have a complexity of O(|V|) (the whole queue has to be traversed) and this part of the sum would be O(|V|^2).

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

In the remaining part of the sum (the one with the edge factor |E|), the O(1) v.s. O(log |V|) difference comes precisely from using respectively a Fibonacci heap as opposed to a binary heap. The decrease key operation which may happen for every edge has exactly this complexity. So the remaining part of the sum eventually has complexity O(|E|) for a Fibonacci heap and O(|E| log |V|) for a binary heap. For a queue implemented with an unsorted array, the decrease-key operation would have a constant-time complexity (the queue directly stores the keys indexed by the vertices) and this part of the sum would thus be O(|E|), which is also O(|V|^2).

总结:

• 斐波那契堆: O(| E | + | V | log | V |)
• 二进制堆: O((| E | + | V |)log | V |)
• 未排序的数组: O(| V | ^ 2)

因为，通常情况下， | E |= O(| V | ^ 2)，如果不对要处理的图的类型作进一步的假设，就无法进一步简化它们.

Since, in the general case |E| = O(|V|^2), these can't be simplified further without making further assumptions on the kind of graphs dealt with.

这篇关于Dijkstra Fibonacci堆解决方案上的Big O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！