图需要多大才能触发斐波那契堆的最坏复杂度？
发布于2024-12-11 17:24 阅读(508) 评论(0) 点赞(5) 收藏(3)
我一直试图通过将斐波那契堆与 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))，这仍然不意味着第一个总是比第二个快。想象一下第一个执行 k 1 *n 个操作，第二个执行 k 2 n*log(n) 个操作。现在，如果 k 1 = k 2 * 1000，那么只有当 n > 21000 时，第一个算法才会比第二个算法更快，这是相当大的。重要的是，如果您有一个值，第一个算法将超过第二个算法。
根据给定数据结构的实现，常数可能会有所不同，因此您可能需要几倍大的数据集来弥补它。我已经看到一些结果，斐波那契堆在约 500 000 条边（和约 5000 个节点）时比普通的旧二进制堆更快，但这些仅适用于该特定实现。在您的实现中，差异可能会更早或更晚出现，具体取决于您实现这两种结构的效率。可以肯定的是，如果您以正确的复杂性实现了数据结构，差异将在某个 n 时显示出来（但可能发生的情况是没有现有的计算机可以处理这么大的图形）。
所属网站分类: 技术文章 > 问答
作者：黑洞官方问答小能手
链接：http://www.javaheidong.com/blog/article/694586/29df3c29e51d82624a55/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力