为什么图算法的时间复杂度用|E|而不是使用 |V|^2？
Why do the time complexity of graph algorithms use |E| instead of using |V|^2?
Dijkstra算法和Bellman Ford算法的时间复杂度不应该分别是O(|V|^2)和O(|V|^3)吗？我一直在阅读他们的伪代码 here and here。
Bellman Ford 算法和 Dijkstra 算法看起来很相似，除了 Bellman Ford 算法执行与 Dijkstra 算法相同的过程 |V| 次（其中 |V| 是节点数）。那么，为什么我访问的每篇关于该主题的文章都说 Dijkstra 算法的运行时间复杂度为 O(|v|^2) 而 Bellman Ford 算法的运行时间复杂度为 O(|V||E|)？我哪里错了（如果我真的错了）？
更新：
你不觉得：
|E| = (|V|^2 - |V|)/ 2 如果每个节点都连接到其他节点？因此，让我们假设每个节点都与其他每个节点相连。现在我们得到 Bellman Ford 算法的 O(|V|^3)。我说得对吗？
所以我们有 O(|V||E|) = O(|V|(|V|^2 - |V|)/2) = O(|V|^3)。那正确吗？如果不是，我哪里错了？
Shouldn't the time complexity of Dijkstra's algorithm and Bellman Ford
algorithm be O(|V|^2) and O(|V|^3) respectively?
是(1)，但这不会是一个严格的界限。同样，您可以说它是 O(|V|^5)，它也是正确的（回想一下大 O 是渐近上界，而不是紧上界）。
很多图不是稠密的，而是稀疏的，连接到每个顶点的边数是次线性的。所以，如果我们使用 |E|还有符号，我们可以获得更好更紧密（和更多信息）的界限。
类似地，考虑一种遍历大小为 nxm 的矩阵的算法。说算法是 O(n*m) 比说它是 O(max{n,m}^2) 更能提供信息，不是吗？
关于 Dijkstra 算法的实现，实际复杂度在很大程度上取决于最小堆实现中的修改值，而有些实现可以在对数时间内完成（总共 O(|E|+|V|log|V|) 时间，一些实现不会打扰，只是寻求在 O(|V|^2).
中运行的更简单的解决方案
(1) 这里假设简单图
Dijkstra算法和Bellman Ford算法的时间复杂度不应该分别是O(|V|^2)和O(|V|^3)吗？我一直在阅读他们的伪代码 here and here。
Bellman Ford 算法和 Dijkstra 算法看起来很相似，除了 Bellman Ford 算法执行与 Dijkstra 算法相同的过程 |V| 次（其中 |V| 是节点数）。那么，为什么我访问的每篇关于该主题的文章都说 Dijkstra 算法的运行时间复杂度为 O(|v|^2) 而 Bellman Ford 算法的运行时间复杂度为 O(|V||E|)？我哪里错了（如果我真的错了）？
更新：
你不觉得：
|E| = (|V|^2 - |V|)/ 2 如果每个节点都连接到其他节点？因此，让我们假设每个节点都与其他每个节点相连。现在我们得到 Bellman Ford 算法的 O(|V|^3)。我说得对吗？
所以我们有 O(|V||E|) = O(|V|(|V|^2 - |V|)/2) = O(|V|^3)。那正确吗？如果不是，我哪里错了？
Shouldn't the time complexity of Dijkstra's algorithm and Bellman Ford algorithm be O(|V|^2) and O(|V|^3) respectively?
是(1)，但这不会是一个严格的界限。同样，您可以说它是 O(|V|^5)，它也是正确的（回想一下大 O 是渐近上界，而不是紧上界）。
很多图不是稠密的，而是稀疏的，连接到每个顶点的边数是次线性的。所以，如果我们使用 |E|还有符号，我们可以获得更好更紧密（和更多信息）的界限。
类似地，考虑一种遍历大小为 nxm 的矩阵的算法。说算法是 O(n*m) 比说它是 O(max{n,m}^2) 更能提供信息，不是吗？
关于 Dijkstra 算法的实现，实际复杂度在很大程度上取决于最小堆实现中的修改值，而有些实现可以在对数时间内完成（总共 O(|E|+|V|log|V|) 时间，一些实现不会打扰，只是寻求在 O(|V|^2).
(1) 这里假设简单图