Bellman算法空间复杂度

Question

我一直在搜索Bellman算法的空间复杂度，但是在维基百科Bellman-Ford算法上，它说空间复杂度是O(V)。在此链接上，它表示O(V^2)。我的问题是:真正的空间复杂性是什么?为什么？

Answer 1

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

1. 如果我们假设给出了图，那么额外的空间复杂度就是O(V) (对于一个距离数组)。
2. 如果我们假设图也是计数的，则它可以是邻接矩阵的O(V^2)，邻接列表的O(V+E)。

从某种意义上说，它们都是“真实的”。这正是我们想要在一个特定的问题上计算出来的。

Answer 2

有两宗个案：-

1. 如果我们假设图是给定的，那么我们必须创建两个数组(对于一个距离数组和父母数组)，所以额外的空间复杂度是O(V)。
2. 如果我们也考虑存储图形，那么： 邻接矩阵的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或贝尔曼福特都有复杂图，空间复杂度为O(V^2)