Bellman-Ford 算法空间复杂度

Question

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

Answer 1

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

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

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

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