使用斐波那契堆时 Dijkstra 算法的时间复杂度是多少？

适用条件

• 实现使用斐波那契堆数据结构作为优先队列。
• $|V|$ 代表顶点的数量。
• $|E|$ 代表边的数量。

理解与推导

1. 识别用于优先队列的数据结构（斐波那契堆）。
2. 回忆在斐波那契堆中提取最小元素和减少键值的成本。
3. 将这些成本与顶点数和边数结合起来以推导总复杂度。
4. 陈述最终的大 O 表示法。

例子

视频明确指出：“当使用斐波那契堆时，Dijkstra 算法的时间复杂度是 O(|E| + |V|log|V|)。”公式写在屏幕上。

容易误解的地方

• 假设这种复杂度适用于所有实现；使用二叉堆会产生 $O((|E| + |V|)\log|V|)$。
• 在公式中混淆 $|V|$ 和 $|E|$；对数项适用于顶点的数量。

观看对应讲解

继续追问

• Dijkstra 算法的伪代码是什么？
• 优先队列的选择如何影响 Dijkstra 算法的性能？
• 为什么斐波那契堆对此算法比二叉堆更高效？