Dijkstraアルゴリズム(遅延)ランニングタイムの解析
-
29-09-2020 - |
質問
Dijkstraアルゴリズムの実行時間を把握しようとしています。私が読んだすべてのソースは、実行時間が遅延実装のためのO(e * log(e))であると言いました。
しかし私たちが数学をするとき、o(e *(j)(log(e)+ e * log(e)))。
Eは一定ではないので、誰かがO(e * log(e)。
間違ったものを分析するか、減らすことが可能ですか?
while (!minPQ.isEmpty()) { <=== O(E)
Node min = minPQ.poll(); <=== O(log(e)
for (Edge edge : graph.adj(min)) { <=== O(E)
if (min.getId() == target.getId()) {
// Source and Target = Same edge
if (edgeTo.size() == 0) edgeTo.put(target, edge);
return;
}
relax(edge, min, vehicle); <=== log(e) (because of add method on PQ)
}
}
. 解決
最初に、いくつかの境界を少し厳しくすることができ、 $ e $ sを $ vに置き換えることができます。 $ s。
冒頭のwhileループは $ o(| V |)$ 繰り返しを実行します(すべてのノードに一度だけアクセスします)、for (Edge edge : graph.adj(min))
ループは $ O(| | v |)$ 反復(ノードは、ほとんどの $ o(| v |)$}を持つことができます(| V |)$ 隣接エッジ)。
ログファクタと同じですが、その場合は $ o(\ log | v |)= O(\ log | e |)$ (グラフが接続されている場合)。
単純乗算を介してこれはあなたに $ o(| v | \ cdot(\ cdot | + | v | \ cdot \ log | v |)= o ^ 2 \ CDOT \ log | v |)$ 。
密なグラフでは、これはすでに望ましい複雑さです。密なグラフに $ O(| V | ^ 2)= O(| e |)$ 。
あなたが直面している問題は、上限を乗じることが過大評価につながる可能性があることです。次の例をご覧ください:
for (i = 1 to N) {
limit = N if i == 1 else 1
for (j = 1 to N) {
constant_work()
}
}
.
外部ループは明確に $ o(n)$ 回転し、内部ループは $ O(n)も実行されます。 )$ 回数(最悪の場合はそうであるため)。 複雑さが $ o(n ^ 2)$ 時刻であると言える。しかしこれは単なる上限です。
ほとんどの場合、内部関数が実際にはほとんどうまくいきません。
実際には、関数constant_work()
を実行した回数を数えると、取得されます。
$$ n + 1 + 1 +¥cdots + 1= 2n - 1= O(n)$$
$ n $ i == 1
の繰り返し、そうでなければ $ 1 $ 繰り返し。
そのため、コードは $ o(n)$ x 時刻で実行されます。
ノードの横にあるエッジを越えてループすると同じ効果が発生します.for (Edge edge : graph.adj(min))
。
はい、最悪の場合、 $ o(| V |)$ エッジ、しかしスパースグラフでは、ほとんどの場合は必要なほとんどが少なくなります。
別の角度から数えることができます。エッジ $(u、v)$ を固定した場合、そのエッジに触れてループの本文に移動しますか。
二度だけ! min == u
のとき、そしてmin == v
のときに1回。
したがって、ランタイム $ o(\ log | v |)$ だけで、ループの内部部分がのみを実行します。 (2 | e |)= O(| e |)$ 回数。つまり、全体が $ o(| e | \ log | v |)$ 。
他のヒント
あなたの分析は正しいですが、タイトなことはありません。
whileループとforループを別々に検討する代わりに、それらをまとめる方が良いです。FORループの内部本体は、合計 $ 2 | e | $ 時間の合計で、各(頂点、ペア)エッジに1回実行されます。したがって、すべてのリラックス操作の合計実行時間は $ O(| e | \ log | e | $ )
すべてのポーリング操作の合計実行時間も $ O(| | e | \ log | e |)$ 、それを推測します。合計実行時間は $ o(| e | \ log | e |)$ 。