删除算法复杂度中的非常量
Dropping non-constants in Algorithm Complexity
所以，基本上我正在实施一种算法来计算加权图中从一个源节点到每个其他节点的距离，如果一个节点处于负循环中，它会检测并标记该节点。
我的问题是关于我的算法的总时间复杂度。假设 V 是节点数，E 是边数。
算法首先要求 E 行输入指定图的边，并将其插入相应的邻接表中。这样的操作就是O(E)
我应用 Bellman-Ford 算法 V-1 次来了解距离，然后我再次应用算法 V-1 次来检测负循环中的节点。这是 2 * O(VE) = O(VE).
我打印了一个大小为 V 的距离向量，以显示距离 and/or 节点是否处于负循环中。 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非常大（理论上你通过计算极限来研究complexity当V 和 E 接近无穷大）。为什么你可以写 n^2 + n = O(n^2) 几乎相同，在你的情况下 VE + V + E 是 O(VE).
请注意，Bellman-Ford 的最坏情况复杂度实际上是 O(VE)，这证实了您的推理是正确的。
所以，基本上我正在实施一种算法来计算加权图中从一个源节点到每个其他节点的距离，如果一个节点处于负循环中，它会检测并标记该节点。
我的问题是关于我的算法的总时间复杂度。假设 V 是节点数，E 是边数。
算法首先要求 E 行输入指定图的边，并将其插入相应的邻接表中。这样的操作就是O(E)
我应用 Bellman-Ford 算法 V-1 次来了解距离，然后我再次应用算法 V-1 次来检测负循环中的节点。这是 2 * O(VE) = O(VE).
我打印了一个大小为 V 的距离向量，以显示距离 and/or 节点是否处于负循环中。 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非常大（理论上你通过计算极限来研究complexity当V 和 E 接近无穷大）。为什么你可以写 n^2 + n = O(n^2) 几乎相同，在你的情况下 VE + V + E 是 O(VE).
请注意，Bellman-Ford 的最坏情况复杂度实际上是 O(VE)，这证实了您的推理是正确的。