algorithm - Bellman-Ford 算法空间复杂度

Question

我一直在搜索贝尔曼福特算法的空间复杂度，但在维基百科贝尔曼福特算法上，它说空间复杂度是 O(V)。在这个链接上它说 O(V^2) 。我的问题是；什么是真正的空间复杂度，为什么？

Answer 1

这取决于我们定义它的方式。

1. 如果我们假设图是给定的，那么额外的空间复杂度是O(V)（对于距离数组）。

2. 如果我们假设图也很重要，它可以O(V^2)用于邻接矩阵和O(V+E)邻接列表。

从某种意义上说，它们都是“真实的”。这只是我们想要在特定问题中计算的内容。

Answer 2

有两种情况：-

1. 如果我们假设给定了图形，那么我们必须创建 2 个数组（用于距离数组和父数组），因此额外的空间复杂度为 O(V) 。

2. 如果我们也考虑存储图形，那么：

   a) O(V^2) 用于邻接矩阵

   b) O(V+E) 用于邻接表

   c) O(E) 如果我们只创建将只存储所有边的边列表

Answer 3

我们是否使用邻接表或使用邻接表都没有关系。
如果给定的图是完整的，则邻接矩阵

space complexity = input + extra
1  if we use adjacency matrix,  space = input + extra O(V^2)+O(V) ->Using min heap =O(V^2)
2 if we use adjacency list,  space = input + extraa 
In complite graph E = O(V^2)
O(V + E) + O(V) -> min heap = O(V^2)

因为如果我们谈论空间复杂度。
算法我们总是在最坏的情况下使用。
发生 .in Dijkstra 或 bellman ford 都有完整的图，空间复杂度为 = O(V^2)