无法总结算法的复杂性

我实现了一个图算法，我发现该算法的时间复杂度为O(V) + O(log V) + O(E) * O(log V)。作为算法的复杂性，我可以提出最好的结果是O((V + E) log V)。它看起来不正确。算法的复杂性究竟是什么？无法总结算法的复杂性

2016-04-22 aradhak

假设'E'至少'O（V）'，那么复杂性简直是' O（E logV）'，因为这是增长最快的术语。对于大的“E”和“V”，O（E logV）>> O（V）>> O（logV）'。 – user3386109

所以你的算法是O(V) + O(E) * O(log V)（logV是一个小项）。

现在，如果您有一个稀疏图形（图的边数约为顶点数），则复杂度为O(V * log V)。

当你有一个稠密图（图这里边的数量接近V * (V - 1)/2），你的复杂性是O(V^2 * log V)

2016-04-23 05:04:12

回答