無法總結算法的複雜性

我實現了一個圖算法，我發現該算法的時間複雜度爲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

回答