在算法复杂性中删除非常量项

Question

所以，基本上我正在实现一种算法来计算加权图中从一个源节点到每个其他节点的距离，并且如果一个节点在负循环中，它会检测并标记该节点。

我的问题涉及算法的总时间复杂度。假设V是节点数，E是边数。

算法首先询问E行输入以指定图的边缘，并将其插入相应的邻接列表中。此类操作为O（E）。

我将Bellman-Ford算法应用V-1次以了解距离，然后再次应用算法V-1次以检测负循环中的节点。这是2 * O（VE）= O（VE）。

我打印一个大小为V的距离向量，以显示距离和/或节点是否处于负循环中。 O（V）。

所以我想我的总复杂度将是O（VE + V + E）。现在我的问题是：由于对于大的数字，VE几乎总是比V + E大（总是！），我可以在复杂度中省略V + E并使其简单地为O（VE）吗？

- Luís Pedro Borges

Answer 1

是的，O(VE + V + E)简化为O(VE)，其中V和E表示图中顶点和边的数量。对于高度连接的图，E = O(V^2)，因此在这种情况下VE + V + E = O(V^3) = O(VE)。对于稀疏图，E = O(V)（注意，这不一定是紧密的上界），因此VE + V + E = O(V^2) = O(VE)。在所有情况下，O(VE)是适当的复杂度上界。

- Matthew Nizol

Answer 2

是的，在处理渐近复杂度时，您总是假设V和E非常大（在理论上，通过计算当V和E趋近无穷大时的极限来研究复杂性）。就像您可以写成n^2 + n = O(n^2)一样，在您的情况下VE + V + E是O(VE)。

请注意，Bellman-Ford算法的最坏情况复杂度实际上是O(VE)，这证实了您的推理是正确的。

- Miljen Mikic