-3

Dijkstra 算法和 Bellman Ford 算法的时间复杂度不应该分别是O(|V|^2)和吗？O(|V|^3)我一直在从这里和这里阅读他们的伪代码。

Bellman Ford 算法和 Dijkstra 算法看起来非常相似，除了 Bellman Ford 算法在|V|时间上与 Dijkstra 算法执行相同的过程（其中|V|是节点数）。那么为什么我访问的关于这个主题的每一篇文章都说 Dijkstra算法运行在时间复杂度上，O(|v|^2)而 Bellman Ford 算法运行在O(|V||E|)时间复杂度上？我哪里做错了（如果我真的做错了）？

更新：你不觉得： |E| = (|V|^2 - |V|)/ 2如果每个节点都连接到其他节点？所以让我们假设每个节点都与其他节点相连。现在我们得到，O(|V|^3)对于贝尔曼福特算法。我对吗？

所以我们有O(|V||E|)= O(|V|(|V|^2 - |V|)/2) = O(|V|^3)。是对的吗？如果没有，我哪里做错了？

4

1 回答 1

2

Dijkstra算法和Bellman Ford算法的时间复杂度不应该分别是O(|V|^2)和O(|V|^3)吗？

是(1)，但这不会是一个严格的界限。同样，你可以说它是O(|V|^5)，它也是正确的（回想一下，大 O 是渐近上界，而不是紧上界）。
许多图不是密集的，而是稀疏的，并且连接到每个顶点的边数是次线性的。所以，如果我们使用 |E| 符号，我们可以得到一个更好的更紧密（和更多信息）的界限。

类似地，考虑一个遍历大小矩阵的算法nxm。说算法 isO(n*m)比说 it's更有用O(max{n,m}^2)，不是吗？

关于 Dijkstra 算法的实现，实际复杂性很大程度上取决于最小堆实现中的修改值，而有些实现可以在对数时间内完成（给出总O(|E|+|V|log|V|)时间，一些实现不打扰，只是去中运行的更简单的解决方案O(|V|^2)。

(1) 这里假设简单的图

于 2015-10-02T07:15:55.237 回答