G（V、E）を、正のエッジの重みを持つ無向グラフとします。ダイクストラの単一ソース最短経路アルゴリズムは、時間計算量のあるバイナリヒープデータ構造を使用して実装できます。
1. O(|V|^2)
2. O(|E|+|V|log|V|)
3. O(|V|log|V|)
4. O((|E|+|V|)log|V|)
================================================== ======================
正解は-
- O（| E | + | V |）ログ| V |）
================================================== =======================
私のアプローチは次のとおりです-
O(V+V+VlogV+ElogV) = O(ElogV)
O(V) 初期化する。O(V) ヒープを構築します。VlogV Extract_Minを実行するにはElogV 減少キーを実行するにはさて、O（ElogV）を取得し、オプションを見ると、グラフがまばらであるため、正しいものはO（VlogV）であると言う人がいます| V | = | E |ですが、私が言ったように、正解はO（（| E | + | V |）log | V |）です。それで、私はどこが間違っているのですか？
さて、あなたは複雑さが実際にはO（E log V）であることは正しいです。
以来、Eが最大であることができる（V ^ 2 - V）/ 2、これは同じではありませんO（VログV） 。
すべての頂点にエッジがある場合、V <= 2Eであるため、その場合、O（E log V）= O（（E + V）log V）です。これは通常のケースであり、「正解」に対応します。
ただし、技術的には、O（E log V）はO（（E + V）log V）と同じではありません。これは、Vに切断された頂点が多数存在する可能性があるためです。ただし、その場合、ダイクストラのアルゴリズムは、単一のソースに接続されている頂点のみを検出するため、これらすべての頂点を検出することはありません。したがって、これら2つの複雑さの違いが重要な場合、あなたは正しいですが、「正解」は正しくありません。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加