プライオリティキューを使用したプリムアルゴリズムの複雑さ？

Question

私は隣接行列を使用していますが、優先度キューはデータ構造体です。私の計算で

、複雑さがV^3 log Vです：

• Whileループ：V
• エントリがすでに存在している場合は、キューの確認、およびそれを更新：V log v
V
• は、隣接する頂点をチェック

しかし、私はどこでも複雑さが読み取られていますV^2

説明してください。

Answer 1

フィボナッチヒープを使用する場合、最小値を抽出するのはO(lg V)償却されたコストであり、そのエントリの更新はO(1)償却です。

我々は、この擬似コード

while priorityQueue not empty 
    u = priorityQueue.exractMin() 
    for each v in u.adjacencies 
     if priorityQueue.contains(v) and needsWeightReduction(u, v) 
      priorityQueue.updateKeyWeight(u, v) 

を使用する場合は、実装がpriorityQueue.contains(v)とneedsWeightReduction(u, v)の両方のために一定の時間を持っていると仮定します。

隣接関係を確認するために少し強く縛ることができる点に注意してください。外側ループはV回実行され、単一ノードの隣接関係をチェックするのは最悪の場合Vです。集約分析を使用すると、E以上の隣接関係をチェックすることはありません（theresのみEエッジなので）。そしてE <= V^2なので、これはやや良い境界です。

したがって、あなたは外側ループV回、内側ループE回を持っています。 minを抽出するとV回実行され、ヒープのエントリを更新するとE回実行されます。

V*lgV + E*1 
= O(V lgV + E) 

ここでも、E <= V^2ので、あなたは代わりと

O(V lgV + V^2) 
= O(V^2) 

を取得するには、この事実を使用することができます。しかし、これは（正しいが）まばらなグラフを検討する際にバインド緩いです。