Dijkstraアルゴリズム（遅延）ランニングタイムの解析

cs.stackexchange https://cs.stackexchange.com/questions/126394

質問

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 |）$ 。

しかしながら、スパースグラフでは、例えば。 $ o（| | e |）= O（| V |）$ 、それでもはるかに良いことをすることができます。

あなたが直面している問題は、上限を乗じることが過大評価につながる可能性があることです。次の例をご覧ください：

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 |）$ 。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top