使用 Dinic 的 O((V^2)E) 算法优于 Edmond-Karp 算法 O(V(E^2))
Advantage of using Dinic's O((V^2)E) algorithm over Edmond-Karp algorithm O(V(E^2))
使用 Dinic 的 O((V^2)E) 算法与 Edmond-Karp 算法 O(V(E^2)) 相比有什么优势吗？
换句话说，如果从竞争性编程的角度来看，我想知道 O((V^2)E) 比 O(V(E^2)) 好多少。
假设 n 中的顶点总数。 "Usually"，连通图中的边数往往在n到n^2之间。
大部分输入图都不是很稀疏，所以在最大百分比的情况下边的数量会大于 n（可能是 O(n log n)，或者在最坏的情况下，O(n^ 2)).
所以，如果你考虑最坏的情况，O(V^2 * E) 是 O(n^4)，而 O(V*E^2) 是 O(n^5)。因此，您会看到使用 O(V^2*E) 时间算法优于 O(V*E^2) 的优势。
使用 Dinic 的 O((V^2)E) 算法与 Edmond-Karp 算法 O(V(E^2)) 相比有什么优势吗？ 换句话说，如果从竞争性编程的角度来看，我想知道 O((V^2)E) 比 O(V(E^2)) 好多少。
假设 n 中的顶点总数。 "Usually"，连通图中的边数往往在n到n^2之间。
大部分输入图都不是很稀疏，所以在最大百分比的情况下边的数量会大于 n（可能是 O(n log n)，或者在最坏的情况下，O(n^ 2)).
所以，如果你考虑最坏的情况，O(V^2 * E) 是 O(n^4)，而 O(V*E^2) 是 O(n^5)。因此，您会看到使用 O(V^2*E) 时间算法优于 O(V*E^2) 的优势。