所以，基本上我正在实现一种算法来计算加权图中从一个源节点到每个其他节点的距离，如果一个节点处于负循环中，它会检测并标记该节点。
我的问题是关于我的算法的总时间复杂度。假设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)吗？
是的，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)，复杂度都有一个适当的上限。
是的，在处理渐近复杂性时，您总是假设V并且E非常大（理论上，您通过计算极限何时接近无穷大来研究复杂性）。在你的情况下，你可以写作的原因几乎相同。VEn^2 + n = O(n^2)VE + V + EO(VE)
请注意，Bellman-Ford的最坏情况复杂度实际上是O(VE)，这证实了您的推理是正确的。