我正在阅读有关使用二进制堆的 Dijkstra 算法的最坏情况时间复杂度(该图表示为邻接表)。
根据维基百科(https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time)和各种stackoverflow问题,这是O((V + E) logV)E - 边数,V - 顶点数。但是我没有找到解释为什么它不能在O(V + E logV).
使用自平衡二叉搜索树或二叉堆,算法
Θ((E+V) logV)在最坏情况下需要时间
在 E >= V 的情况下,复杂性O(E logV)无论如何都会降低。否则,我们O(E)在与起始顶点相同的连通分量中有顶点(一旦到达它们,算法就会结束)。在每次迭代中,我们都会获得其中一个顶点,并花O(logV)时间将其从堆中删除。到连接顶点的距离的每次更新都需要O(logV),并且这些更新的数量受边数 E 的约束,因此我们总共进行O(E)此类更新。增加O(V)初始化距离的时间,我们得到最终的复杂度O(V + E logV)。
我哪里错了?