5

我最近使用两种数据结构对 Dijkstra 算法的运行时间进行了初步比较，基于 Java 的 PriorityQueue（如果我没记错的话，基于二进制堆）和 Fibonacci 堆。我使用 Java 的 currentTimeMillis() 进行计算。我最终得到的结果非常有趣。这是我的一个测试用例的输出：

Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds

诚然，我目前缺乏数据集，上面的图表是我最大的（我计划尽快制作更多）。但这有意义吗？我一直认为斐波那契堆比其他数据结构更快，因为与其他数据结构相比，它们摊销了运行时间。我不确定这 3 毫秒的差异是从哪里来的。（我在 Intel Core Ivy Bridge i7-3630M 处理器上运行它，如果有帮助的话。）

注意：我偶然发现了这个可能解释这个问题的线程，但我仍然不清楚为什么斐波那契堆版本需要更长的时间。根据该线程，这可能是因为我的图不够密集，因此减少键操作的数量不足以使斐波那契堆的性能真正发挥作用。这是唯一合理的结论，还是我还缺少其他东西？

4

2 回答 2

9

斐波那契堆比二进制堆（Java 的优先级队列中使用的数据结构）渐近更快，因为 Dijkstra 的算法在斐波那契堆中将花费 O(m + n log n) 时间，但在二进制堆中将花费 O(m log n) 时间。这意味着对于大而密集的图，在最坏的情况下，斐波那契堆会更快。

尽管斐波那契堆在渐近上比二叉堆快，但它们具有众所周知的大常数因子，并且斐波那契堆上的许多基本操作需要很长时间才能完成。从长远来看，它们会胜过二叉堆，但对于小图，常数项可能太大，以至于斐波那契堆实际上更慢。

其次，比较渐近运行时间（O(m + n log n) 与 O(m log n)）。如果您使用的图形是稀疏的（即 m = O(n)），那么这两个渐近运行时都是相同的（O(n log n)）。在这种情况下，斐波那契堆的理论优势不存在，二叉堆可能是更好的选择。

最后，请注意，在这种情况下，大 O 表示法指的是最坏情况下的行为，而不是平均情况下的行为。不久前有一篇论文表明，对于某种类型的随机图，Dijkstra 的期望算法远低于最坏情况下减少键和出列操作的数量。在这种情况下，即使在大型图上，二叉堆的性能也可能优于斐波那契堆，因为最坏情况下的行为可能永远不会被触发。

希望这可以帮助！

于 2013-04-04T16:16:01.440 回答
1

斐波那契堆具有更快的渐近线，但它们的常数因子不一定很大。在超过一百万左右的可笑输入时，它们可能会更快，但对于小输入，二进制堆可能会明显更快。

于 2013-04-04T16:11:00.253 回答