知识卡片
二叉堆版Dijkstra复杂度
二叉最小堆中,V 次提取与至多 E 次降键各需 O(lg V),总时间 O((V+E)lg V);
若 E=Ω(V),可写 O(E lg V)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第22章 单源最短路径 · 查看原书依据
The total running time is therefore O((V + E) lg V), which is O(E lg V) in the typical case that |E| = Ω(V). This running time improves upon the straightforward O(V2)-time implementation if E = o(V2/lg V
参考来源
- 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[40000,45000))。
- 结论依据:原文统计一次入堆/提取每顶点与至多一次降键每边。
- 原始内容:The total running time is therefore O (( V + E ) lg V ), which is O ( E lg V ) in the typical case that | E | = Ω( V ). This running time improves upon the straightforward O ( V 2 )-time implementation if E = o ( V 2 /lg V