私は教科書でこの質問に出くわしました：
「一般に、プリム、クラスカル、ダイクストラのアルゴリズムの時間計算量は何に依存していますか?」
a. グラフ内の頂点の数。
b. グラフ内のエッジの数。
c. 両方とも、グラフ内の頂点とエッジの数について。あなたの選択を説明してください。
したがって、ウィキペディアのプリム、クラスカル、およびダイクストラのアルゴリズムによると、最悪の場合の時間の複雑さはO(ElogV)、それぞれO(ElogV)およびO(E+VlogV)です。答えはcだと思いますか？しかし、なぜ？
Prim と Kruskal についてはわかりませんし、Dijkstra については間違っているかもしれませんが、その場合、答えは b になると思います。
ダイクストラは、目的地が見つかるまで、既知の最短経路でノードを訪問します。
これは、2 つのエッジが同じノードを指している場合、1 つのエッジの重みが大きいか等しいため、アルゴリズムでは 1 つだけが考慮されることを意味し、1 つのエッジは従う必要がありません。
したがって、エッジを追加してグラフの走査に費やされる時間を増やす唯一の方法は、ノードを追加することです (既存のノードにエッジを追加すると、アルゴリズムの走査時間が変化する可能性がありますが、エッジの量には比例せず、重みのみに比例します)。
したがって、私の直感では、ノードの量のみが実行時間と直接関係しているということです。ダイクストラのアルゴリズム ウィキペディアのページはこれを確認しているようです:
ダイクストラ アルゴリズムの最も単純な実装は、セット Q の頂点を通常の連結リストまたは配列に格納し、Q から最小値を抽出することは、Q 内のすべての頂点を介した単純な線形検索です。この場合、実行時間は O(E + V^ 2) またはO(V^2)。
もちろん、これは単なる直感であり、cs.stackexの方がより役立つ可能性があります。
V と E の両方がそれぞれのアルゴリズムの漸近的な複雑さに寄与するため、答えは (c) です。ここで、さらに分析すると、V は Kruskal および Prim のものよりもはるかに少ないと主張できます (ログ ファクターであるため)。しかし、E は 3 つのケースすべてでほぼ同じ重みを持っているようです。
また、|E| に注意してください。<= |V|^2 常に (単純なグラフの場合)