アルゴリズム

ダイクストラアルゴリズムの時間計算量の計算を理解する



Understanding Time Complexity Calculation



解決：

ダイクストラの最短経路アルゴリズムはO（ElogV）ここで：

  • Vは頂点の数です
  • Eはエッジの総数です

あなたの分析は正しいですが、あなたのシンボルは異なる意味を持っています！あなたはアルゴリズムがO（VElogV）ここで：



  • Vは頂点の数です
  • Eは、単一ノードに接続されているエッジの最大数です。

名前を変更しましょうEからN.ある分析によるとO（ElogV）と別の人は言うO（VNlogV）。どちらも正しく、実際にはE = O（VN）。違いはElogVはより厳密な見積もりです。


nを頂点の数、mをエッジの数とします。



ダイクストラのアルゴリズムでは、O（n）があります。 削除分 sおよびO（m） 減少キー s、それぞれのコストがO（logn）の場合、バイナリヒープを使用した合計実行時間はO（log（n）（m + n））になります。の費用を償却することは完全に可能です 減少キー フィボナッチヒープを使用してO（1）まで下げると、合計実行時間はO（nlogn + m）になりますが、FHの定数係数のペナルティはかなり大きく、ランダムグラフでは、 減少キー sは、それぞれの上限よりもはるかに低くなります（O（n * log（m / n）の範囲内で、m = O（n）のスパースグラフではるかに優れています）。したがって、次の事実に常に注意してください。合計実行時間は、データ構造と入力クラスの両方に依存します。


念のため、理解したとおり、より詳細な説明を追加します。

  • O（最小ヒープを使用する各頂点に対して：各エッジに対して線形に：頂点をプッシュして、エッジが指す最小ヒープに）。
  • V =頂点の数
  • O（V *（最小ヒープから頂点をポップ+エッジで未訪問の頂点を見つける*それらを最小ヒープにプッシュします））
  • E =各頂点のエッジの数
  • O（V *（最小ヒープから頂点をポップ+と*未訪問の頂点を最小ヒープにプッシュします））。 「訪問」する前に、ここで同じノードを複数回プッシュできることに注意してください。
  • O（V *（log（ヒープサイズ）+ E * log（ヒープサイズ））））
  • O（V *（（E + 1）* log（ヒープサイズ））））
  • O（V *（E * log（ヒープサイズ））））
  • 各頂点は他のすべての頂点を参照できるため、E = V
  • O（V *（V * log（ヒープサイズ））））
  • O（V ^ 2 * log（ヒープサイズ））
  • ヒープサイズはV ^ 2は、距離を更新するたびにプッシュし、頂点ごとに最大Vの比較を行うことができるためです。例えば。最後の頂点の場合、最初の頂点には距離があります10、2番目は9、3番目は8などなので、毎回プッシュして更新します
  • O（V ^ 2 * log（V ^ 2））
  • O（V ^ 2 * 2 * log（V））
  • O（V ^ 2 * log（V））
  • V ^ 2はエッジの総数でもあるので、E = V ^ 2（正式な命名のように）、O（E * log（V））