アルゴリズムの複雑さを要約できません

私はグラフアルゴリズムを実装しました。アルゴリズムの時間複雑度はO(V) + O(log V) + O(E) * O(log V)であることがわかりました。アルゴリズムの複雑さが最大になるのはO((V + E) log V)です。それは正しく見えません。アルゴリズムの複雑さはどういうものでしょうか？アルゴリズムの複雑さを要約できません

出典

2016-04-22 aradhak

あり、そして複雑さは'単純です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に近いグラフ）を持っている場合は

、あなたの複雑さは `E`は`少なくとも `O（V）であると仮定するとO(V^2 * log V)

出典

2016-04-23 05:04:12

アルゴリズムの複雑さを要約できません

答えて

関連する問題