個人的備忘録
辺の数を\(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}\) |
コメント