5

隣接行列を使用するプリムのアルゴリズムが時間計算量をもたらす理由を誰かが私に説明できますか？O(V2)

4

3 に答える 3

6

（ずさんな見た目のASCII数学について事前に申し訳ありませんが、LaTEXを使用して回答を植字することはできないと思います）

複雑なプリムのアルゴリズムを実装する従来の方法は、隣接行列に加えて配列を用意することです。これを、ノードまでの頂点の最小距離を持つO(V^2)配列と呼びましょう。distance

このように、次のターゲットを見つけるためにチェックするだけdistanceです。これをV回実行し、のVメンバーが存在するdistanceため、複雑さはO(V^2)です。

distanceの元の値はすぐに古くなるため、これだけでは十分ではありません。この配列を更新するには、各ステップの最後で隣接行列を反復処理し、distance適切に更新するだけです。これは、各ステップにがかかることを意味するだけなので、時間計算量には影響しませんO(V+V) = O(2V) = O(V)。したがって、私たちのアルゴリズムはO(V^2)です。

を使用せずdistanceに、すべてのEエッジを毎回繰り返す必要があります。これには、最悪の場合V ^ 2エッジが含まれます。つまり、時間計算量はになりますO(V^3)。

証拠：

distance配列がないとMSTを時間内に計算できないことを証明するためにO(V^2)、サイズのツリーを使用した各反復で、追加される可能性のある頂点があることを考慮してnくださいV-n。

どれを選択するかを計算するには、これらのそれぞれをチェックしてツリーからの最小距離を見つけ、それを互いに比較してそこで最小値を見つける必要があります。

最悪のシナリオでは、各ノードにツリー内の各ノードへの接続が含まれているため、n *（Vn）個のエッジと複雑さが.になりO(n(V-n))ます。

nが1からVになると、合計はこれらの各ステップの合計になるため、最終的な時間計算量は次のようになります。

(sum O(n(V-n)) as n = 1 to V) =  O(1/6(V-1) V (V+1)) = O(V^3)

QED

于 2012-10-30T05:17:29.143 に答える
6

注：この回答は、 jozefgの回答を借用したものであり、理解する前に少し考えなければならなかったため、より完全に説明しようとしています。

バックグラウンド

グラフの隣接行列表現は、V x V行列（Vは頂点の数）を構成します。セル（a、b）の値は、頂点aとbをリンクするエッジの重み、またはエッジがない場合はゼロです。

Adjacency Matrix

   A B C D E
--------------
A  0 1 0 3 2
B  1 0 0 0 2
C  0 0 0 4 3
D  3 0 4 0 1
E  2 2 3 1 0

プリムのアルゴリズムは、グラフと開始ノードを取得し、グラフ上で最小スパニングツリーを見つけるアルゴリズムです。つまり、エッジのサブセットを見つけて、結果がすべてのノードと結合されたエッジを含むツリーになるようにします。重みは最小化されます。それは次のように要約されるかもしれません：

  1. ツリーに開始ノードを配置します。
  2. すべてのノードがツリーに含まれるまで繰り返します。
    1. ツリー内のノードをツリー内にないノードに結合するすべてのエッジを検索します。
    2. それらのエッジのうち、最小の重みを持つものを選択してください。
    3. そのエッジと接続されたノードをツリーに追加します。

分析

これで、次のようにアルゴリズムの分析を開始できます。

  1. ループを繰り返すたびに、ツリーに1つのノードを追加します。Vノードがあるため、このループにはO（V）回の反復があります。
  2. ループの各反復内で、ツリー内のエッジを見つけてテストする必要があります。E個のエッジがある場合、単純な検索の実装ではO（E）を使用して、最小の重みでエッジを検索します。
  3. したがって、組み合わせて、複雑さはO（VE）であると予想する必要があります。これは、最悪の場合はO（V ^ 3）になる可能性があります。

ただし、jozefgは、O（V ^ 2）の複雑さを実現する方法を示す良い答えを出しました。

Distance to Tree

            | A  B  C  D  E
            |----------------
Iteration 0 | 0  1* #  3  2
          1 | 0  0  #  3  2*
          2 | 0  0  4  1* 0
          3 | 0  0  3* 0  0
          4 | 0  0  0  0  0

NB. # = infinity (not connected to tree)
    * = minimum weight edge in this iteration

ここで、距離ベクトルは、各ノードをツリーに結合する最小の重み付きエッジを表し、次のように使用されます。

  1. 複雑度O（V）の開始ノードAへのエッジの重みで初期化します。
  2. 次に追加するノードを見つけるには、距離の最小要素を見つける（そしてリストから削除する）だけです。これはO（V）です。
  3. 新しいノードを追加した後、ツリーを残りのノードに接続するO（V）の新しいエッジがあります。これらのそれぞれについて、新しいエッジの重みが既存の距離よりも小さいかどうかを判断します。その場合は、距離ベクトルを更新します。繰り返しますが、O（V）。

これらの3つのステップを使用すると、検索時間がO（E）からO（V）に短縮され、追加のO（V）ステップが追加されて、各反復で距離ベクトルが更新されます。各反復はO（V）であるため、全体的な複雑さはO（V ^ 2）です。

于 2012-10-30T05:49:10.333 に答える
0

まず第一に、それは明らかに少なくともO（V ^ 2）です。これは、隣接行列の大きさだからです。

http://en.wikipedia.org/wiki/Prim%27s_algorithmを見ると、「Vnew=Vになるまで繰り返す」ステップをV回実行する必要があります。

そのステップ内で、V内の任意の頂点とV外の任意の頂点の間の最短リンクを計算する必要があります。各頂点に対して無限大（頂点がV内にある場合）または最短の長さのいずれかを保持して、サイズVの配列を維持します。 V内の任意の頂点とその頂点の間のリンク、およびその長さ（したがって、最初は、これは開始頂点と他のすべての頂点の間のリンクの長さから得られます）。Vに追加する次の頂点を見つけるには、コストVでこの配列を検索します。新しい頂点ができたら、その頂点から他のすべての頂点へのすべてのリンクを調べ、Vからその頂点。含まれている場合は、アレイを更新します。これもVの費用がかかります。

したがって、Vステップ（追加するV頂点）があり、それぞれにコストVがかかり、O（V ^ 2）が得られます。

于 2012-10-30T05:27:45.063 に答える