algorithm - 复杂性 - Dijkstra 算法

Question

假设我已经使用 PriorityQueue 实现了 dijkstras，因此在未访问的节点中添加和删除需要 O(log n)。

PQ 最多包含 E 个节点，因此清空它我们得到 O(E)。当 PQ 不为空时，我们选择最好的节点并将其删除，如果未访问则访问并遍历其所有邻居(可能将它们添加到 PQ)。

我不明白的是:对于最坏的 E 项，遍历所有邻居(最坏的 V)怎么可能没有 O(E*V) 的时间复杂度。我看到了太多的解释，我们应该只看操作并观察它们将执行多少次并从中得出我们的结论。我不明白我们怎么能忽视我们正在循环 V 个邻居这一事实，n 个项目的空 for 循环仍然是 O(n)？

对我来说，最终的复杂度似乎是 O(V + E*V log E) 而不是 O(V + V log E)。我的意思是有很多差异，但重点是我遗漏了一些微不足道的东西 :P

Answer 1

您似乎混淆了术语的第一点。 E不是项目的数量，它是顶点之间的边数。 V是顶点的数量，这(取决于上下文)很可能是项目的数量。

接下来，“这个顶点是那个顶点的邻居”意味着它们之间有一条边。每条边贡献 2 个邻居关系。 (每个方向一个。)因此 2 E是可以存在的邻居关系的个数，total。

您的直觉是 V 中的每一个节点最多可以有 V-1邻居共V<sup>2</sup>-V邻居关系是正确的 - 但您可以从边的数量判断您与最坏情况的接近程度。

因此，我们最终完成了以下潜在工作:

for each of E edges:
    for each vertex on that edge:
        O(1) work to check whether it was processed yet
        (processing the vertex if needed accounted for separately)

for each of V vertices:
    O(log(V)) to add to the priority queue
    O(log(V)) to remove from the priority queue
    (processing its edges accounted for separately

第一个 block 是O(E) .第二 block 是 O(V log(V)) .总数是O(E + V log(V)) .

希望这个解释能澄清为什么会如此复杂。