time-complexity - 图算法的时间复杂度取决于什么？

Question

我在教科书中偶然发现了这个问题：

“一般来说，Prim、Kruskal 和 Dijkstra 算法的时间复杂度取决于什么？”

一个。图中的顶点数。
湾。图中的边数。
C。两者都是关于图中顶点和边的数量。

解释你的选择。

因此，根据 Wikipedia Prim、Kruskal 和 Dijkstra 的算法，最坏情况的时间复杂度分别O(ElogV)为O(ElogV)和O(E+VlogV)。所以我猜答案是c？但为什么？

Answer 1

答案是 (c)，因为 V 和 E 都有助于各自算法的渐近复杂度。现在，在进一步的分析中，有人可能会争辩说 V 在 Kruskal 和 Prim 上的影响要小得多（因为它是对数因子）。但在所有三种情况下，E 似乎几乎具有相同的权重。

另外，请注意 |E| <= |V|^2 总是（对于简单的图表）

Answer 2

我不了解 Prim 和 Kruskal 的情况，并且可能对 Dijkstra 的情况有误，但我认为在这种情况下答案是 b，因为：

Dijkstra 将访问已知最短路径上的节点，直到找到目的地。

这意味着如果两条边指向同一个节点，则算法将只考虑一条，因为一条具有更高的权重或它们相等，从而使一条边没有意义。

因此，通过添加边来增加遍历图所花费的时间的唯一方法是添加节点（在现有节点上添加边可以改变算法的遍历时间，但它与边的数量不成正比，仅与它们的权重成正比）。

因此，我的直觉是只有节点的数量与运行时间有直接关系。Dijkstra 的 Alogrithm 维基百科页面似乎证实了这一点：

Dijkstra 算法的最简单实现将集合 Q 的顶点存储在普通链表或数组中，从 Q 中提取最小值只是对 Q 中的所有顶点进行线性搜索。在这种情况下，运行时间为 O(E + V^ 2) 或O(V^2)。

这当然只是一种直觉，cs.stackex可能会有更大的用处。

Answer 3

在最坏的情况下，图将是一个完整的图，即 v(v-1)/2 边，即 e>>v 和 e ~ v^2

Prim 和 Dijkstra 算法的时间复杂度是：
1. 使用邻接列表和优先级队列：
O((v+e) log v) 在最坏的情况下：e>>v 所以 O(e log v)
2. 使用矩阵和优先级队列:
O(v^2 + e log v) in WC e ~ v^2
所以 O(v^2 + e log v) ~ O(e + e log v) ~ O(e log v)。
3. 当图变得更密集时（最坏的情况是完整图），我们使用斐波那契堆和邻接表：O(e + v log v)

kruskal 的时间复杂度是 O(e log e) 在最坏的情况下 e ~ v^2 所以 log (v^2) = 2 log v

所以我们可以有把握地说，在最坏的情况下，O(e log e) 可以是 O(2e log v)，即 O(e log v)。

Answer 4

正如你所说，O(ElogV)、O(ElogV) 和 O(E+VlogV) 的时间复杂度意味着每个都依赖于 E 和 V。这是因为每个算法都涉及考虑边缘及其各自的权重在图表中。由于 Prim 和 Kruskal 的 MST 必须连接并包含所有顶点，而 Dijkstra 的最短路径必须通过其他中间顶点从一个顶点到另一个顶点，因此每个算法中也必须考虑顶点。

例如，使用 Dijkstra 算法，您实际上是在寻找成本低且连接顶点的边，这些边最终将提供从起始顶点到结束顶点的路径。要找到最短路径，不能只寻找连​​接起点和终点的路径，也不能只寻找最小的加权边，两者都需要考虑。由于您正在考虑边和顶点，因此在整个算法中进行这些考虑所需的时间将取决于边数和顶点数。

此外，通过三种算法的不同实现，可能存在不同的时间复杂度，分析每种算法需要同时考虑 E 和 V。

例如，Prim 的算法是 O(V^2)，但可以通过使用基于最小堆的优先级队列进行改进，以实现您发现的复杂性：O(ElogV)。O(ElogV) 可能看起来是更快的算法，但并非总是如此。E 可以与 V^2 一样大，因此在具有接近 V^2 边的密集图中，O(ElogV) 变为 O(V^2)。如果 V 非常小，则 O(V^2) 和 O(ElogV) 之间没有太大区别。E 和 V 还会根据图形的存储方式影响运行时间。例如，对于密集图（E 接近 V^2），邻接表变得非常低效，因为检查图中是否存在边从接近 O(1) 到 O(V)。