Dijkstra法のデータ構造による計算量の変化

質問

Dijkstra法を実行するプログラムを隣接行列と隣接リストを用いてそれぞれ実装しました。
そこでデータ構造の違いによる計算量の違いをオーダー表記を用いて表そうとしているのですが
どのように計算すればいいのか検討がつきません。
次の点に行くためにどのような処理が必要か、また点を訪れてからどのような処理が必要かを求めれば良いみたいです。
回答よろしくお願いします。

回答No.1

Tacosan · ベストアンサー

単純には, 各処理に対して
「1回あたりの所要時間」と「実行回数」の積
を積算するだけ.