ダイクストラ法の計算量をわかりやすく

個人的備忘録

辺の数を\(E\),頂点の数を\(V\)とする。 スタート地点とゴール地点は固定されている。

オリジナル

$$\mathcal{O} (V^2 + E) = \mathcal{O} (VV + E)$$

Vそれぞれの頂点について一回踏み入れ、探索する。
Vその時、V頂点の中から一番コストの少ない点を取得するため。
+
E辺を二回使うことはなく、それぞれの辺に一回ずつアクセスする

優先度付き待ち行列

$$\mathcal{O} ((V+E)\log{E}) = \mathcal{O} (V\log{E} + E\log{E})$$

Vそれぞれの頂点について一回踏み入れ、探索する。
\(\log{E}\)その時、V頂点の中から一番コストの少ない点を取得するため。
これには今キューに入っている数の対数で計算量かかる。
キューには最大E個挿入される可能性があるため、\(\log{E}\)
+
E辺を二回使うことはなく、それぞれの辺に一回ずつアクセスする
\(\log{E}\)キューに追加するとき、今キューに入っている数の対数で計算量がかかる。
キューには最大E個挿入される可能性があるため、\(\log{E}\)

コメント

タイトルとURLをコピーしました