所以,基本上我正在实现一种算法来计算加权图中从一个源节点到每个其他节点的距离,并且如果一个节点在负循环中,它会检测并标记该节点。
我的问题涉及算法的总时间复杂度。假设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)吗?
我的问题涉及算法的总时间复杂度。假设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)吗?