gpt4 book ai didi

algorithm - Dijkstra 斐波那契堆解决方案中的大 O

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:38:32 27 4
gpt4 key购买 nike

来自 Wikipedia : O(|E| + |V| log|V|)

来自 Big O Cheat List : O((|V| + |E|) log |V|)

我认为 E + V log V(E+V) log V 是有区别的,不是吗?

因为,如果维基百科的是正确的,它不应该显示为 O(|V| log |V|) 只有这样(删除 |E|)出于我不明白的原因?)?

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

最佳答案

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

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

其中 Q 是根据当前距离估计对顶点排序的最小优先级队列。

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

在总和的剩余部分(具有边缘因子 |E| 的部分),O(1) v.s. O(log |V|) 区别恰恰来自分别使用 Fibonacci 堆而不是二进制堆。每条边都可能发生的减少键操作正是具有这种复杂性。因此,对于斐波那契堆,总和的剩余部分最终具有复杂度 O(|E|),对于二叉堆,复杂度为 O(|E| log |V|)。对于使用未排序数组实现的队列,减少键操作将具有常数时间复杂度(队列直接存储由顶点索引的键),因此这部分总和将为 O(|E| ),也就是 O(|V|^2)

总结:

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

因为,在一般情况下 |E| = O(|V|^2),如果不对所处理的图类型做出进一步假设,这些就无法进一步简化。

关于algorithm - Dijkstra 斐波那契堆解决方案中的大 O,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21065855/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com