嵌套循环和 Dijkstra 算法的大 O 表示法

Question

我有以下代码：

for each nodeG in Graph
   for each nodeS in subset
       path(nodeG, nodeS) // using dijkstra that in the best has O(V lg V + E);
   end
end

每次执行主循环时，都会从队列中提取一个顶点。假设图中有 V 个顶点，则队列可能包含 O(V) 个顶点。假定优先级队列的堆实现，每个弹出操作都需要 O(lg V) 时间。所以执行主循环本身所需的总时间是 O(V lg V)。此外，我们必须考虑在函数 expand 中花费的时间，它将函数 handle_edge 应用于每个出边。因为 expand 每个顶点只调用一次，所以 handle_edge 每个边只调用一次。它可能会调用 push(v')，但在整个执行过程中最多可以有 V 次这样的调用，因此该 case arm 的总成本最多为 O(V lg V)。然而，另一个 case arm 可能被调用 O(E) 次，并且每次调用 increase_priority 都需要 O(lg V) 时间来实现堆。因此，总运行时间为 O(V lg V + E lg V)，即 O(E lg V)，因为 V 是 O(E)，假设一个连通图。

（还有另一个更复杂的优先级队列实现，称为 Fibonacci 堆，它在 O(1) 时间内实现 increase_priority，因此 Dijkstra 算法的渐近复杂度变为 O(V lg V + E) ; 然而，大的常数因子使得斐波那契堆对于大多数用途来说是不切实际的。）

所以基本上现在对于每个两个，我们有 O(n^2)。但路径实际上是 Dijkstra 算法，其中 Big Oh 是 O(V lg V + E)。我怎样才能将它乘以总的 Big Oh？

Answer 1

我是这样理解你的问题的（如有错误请指正）：

您尝试为图中的每一对节点计算 Dijkstra。所以图中有 V(V-1)/2 对（V 是顶点数）。

然后，V(V-1)（即你计算 Dijkstra 的 O(V^2) 次，其复杂度为 O(V + ElogV)（我不知道你从哪里得到你的 O(VlogV + E) 来自，但它可能不正确)

总的来说，复杂度是O(V^2logV + EV^2)

嵌套循环和 Dijkstra 算法的大 O 表示法

Big O notation for nested loops and Dijkstra algorithm

complexity-theory

big-o

time-complexity