1

我一直试图通过将它与 Dijkstra 算法一起使用来触发斐波那契堆的最坏情况复杂性，但显然没有运气。我有第二个使用香草二进制堆的 Dijkstra 实现，它似乎总是赢。我被告知要使用更大的数据集进行测试，如图所示（直接从我的程序复制粘贴）：

Running Dijkstra's algorithm with 3354 nodes and 8870 links...
Source node: ALL
Time using binary heap = 2167698339 ns (2167.70 ms)

相对...

Running Dijkstra's algorithm with 3354 nodes and 8870 links...
Source node: ALL
Time using Fibonacci heap = 11863138070 ns (11863.14 ms)

2 秒，约 12 秒。差别很大好吧。

现在，我有另一个图表，其中包含高达 264,000 个节点和 733,000 条边。我还没有机会测试它，但这足以让斐波那契堆的理论优势大放异彩吗？

我希望我不需要超过一百万个节点的东西。我的意思是这不是世界上最大的问题，但很高兴能看到一次行动的不同。

4

2 回答 2

1

首先，您的问题的标题不正确。输入的大小不会影响最坏情况的复杂性。您需要的是图的大小，其中斐波那契堆的渐近计算复杂度弥补了它的常数因子。还记得旧日的美好O(n)吗？这O(n)意味着对于足够大的数据集，您的算法将执行近似k*n运算，其中 k 是一个固定数字。这k是我所指的常数。现在，如果你有一个复杂的算法O(n)和另一个复杂的算法O(n*log(n))，这仍然不意味着第一个总是比第二个快。想象一下，第一个执行 k 1 *n 操作，第二个执行 k 2 n*log(n) 操作。现在如果 k 1= k 2 * 1000，只有当 n > 21000 时，第一个算法才会比第二个算法快，这是相当大的。重要的是，如果您有一个值，第一个算法将超过第二个算法。

根据给定数据结构的实现，常数可能会有所不同，因此您可能需要几倍大的数据集来弥补它。我已经看到了一些结果，其中斐波那契堆在大约 500 000 个边（和大约 5000 个节点）处比普通的旧二进制堆更快，但这些仅适用于该特定实现。在您的实现中，差异可能会更早或更晚显示，具体取决于您实现这两种结构的效率。可以肯定的是，如果您以正确的复杂性实现数据结构，则差异会在某些 n 中显示出来（但可能没有现有的计算机可以处理那么大的图）。

于 2013-04-18T08:43:04.547 回答
0

我认为你的斐波那契堆对于大图不一定更快。您需要增加的是 reductionKey 操作的数量。如果节点的平均度数增加（因此是高维图），您应该获得更多这样的操作。或者可以说图形是否变得更完整（高度互连）。

于 2013-04-18T11:08:33.750 回答