中每个顶点的摊余更新成本是多少 Dijkstra 算法：回答： O(|E| / |V|) 我的挑战是：这个答案是否与实施有关？i、 e:纤维堆还是。。。下一步是关于dijkstra算法的哪种操作？我是说钥匙？删除最小部分？分析的哪一部分？例如，考虑这个伪代码只是为了讨论（或任何其他）：
Dijkstra
O(|E| / |V|)
uujelgoq1#
重复@paul，这个问题没有太多意义，因为dijkstra的算法不是一个包含许多可能调用序列的数据结构；它只是做自己的事然后退出。如果我们假设一个fibonacci堆，它的操作有分摊的时间界限，那么由堆在循环中为顶点u所做的分摊功是o（degree（u）），因为fibonacci堆有分摊的常数时间递减键操作。
1条答案
按热度按时间uujelgoq1#
重复@paul，这个问题没有太多意义，因为dijkstra的算法不是一个包含许多可能调用序列的数据结构；它只是做自己的事然后退出。
如果我们假设一个fibonacci堆，它的操作有分摊的时间界限，那么由堆在循环中为顶点u所做的分摊功是o（degree（u）），因为fibonacci堆有分摊的常数时间递减键操作。