我一直试图通过将斐波那契堆与 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 条边。我还没有机会测试它，但这足以让斐波那契堆的理论优势大放异彩吗？
我希望我不需要超过一百万个节点的东西。我的意思是，这不是世界上最大的问题，但很高兴能看到一次行动上的差异。
最佳答案
首先你的问题标题不正确。输入的大小不会影响最坏情况的复杂性。您需要的是图表的大小，其中斐波那契堆的渐近计算复杂性弥补了其常数因子。还记得古老的O(n)吗？那么 O(n) 意味着对于足够大的数据集，您的算法将执行大约 k*n 操作，其中 k 是固定数字。这个k是我指的常量。现在，如果您有一个复杂度为 O(n) 的算法和另一个复杂度为 O(n*log(n)) 的算法，这仍然并不意味着第一个算法总是比第二个算法快。想象一下，第一个执行 k1*n 操作，第二个执行 k2n*log(n) 操作。现在，如果 k1 = k2 * 1000，则只有当 n > 21000(这是相当大)时，第一个算法才会比第二个算法更快。重要的是，如果你有一个值，第一个算法将超越第二个算法。
根据给定数据结构的实现，常量可能会有所不同，因此您可能需要几倍大的数据集来弥补。我已经看到一些结果，其中斐波那契堆在大约 500 000 个边(以及大约 5000 个节点)处比普通的旧二进制堆更快，但这些仅适用于特定的实现。在您的实现中，差异可能会更早或更晚显示，具体取决于您实现这两种结构的效率。可以肯定的是，如果您实现了具有正确复杂性的数据结构，则对于某些 n 会显示出差异(但可能会发生没有现有计算机可以处理那么大的图)。
关于java - 图表需要多大才能触发斐波那契堆的最坏情况复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16071225/