8

隣接行列を使用しています。優先キューはデータ構造です。

私の計算によると、複雑さは次のV^3 log Vとおりです。

  • Whileループ：V
  • 隣接する頂点の確認：V
  • エントリがすでに存在する場合はキューをチェックし、同じものを更新します。V log v

しかし、私はどこでも複雑さはV^2

説明してください。

4

2 に答える 2

4

フィボナッチヒープを使用する場合、最小値の抽出は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（Eエッジしかないため）。そしてE <= V^2、これは少し良い境界です。

つまり、外側のループはV回、内側のループはE回になります。最小実行時間を抽出Vし、ヒープ実行E時間のエントリを更新します。

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

繰り返しになり E <= V^2ますが、この事実を使用して代用して取得できるためです

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

しかし、これは、まばらなグラフを検討する場合には、より緩い境界です（正しいとはいえ）。

于 2012-11-26T00:13:30.163 に答える
1

最小ヒープベースの優先キューを使用すると、時間計算量はO（ElogV）になります。

あなたが言ったように、外側のwhileループはO（V）です。これは、各頂点を一度MSTに追加する必要があるため、すべての頂点をループしているためです。

whileループで考慮される頂点ごとに、次の2つの手順を実行する必要があります。

  1. MSTに追加する次のエッジが選択されます。最小ヒープベースの優先度キューのプロパティによると、ルート要素は常に最小の要素になります。したがって、コストが最も低い次のエッジを選択すると、ルート要素のO（1）抽出になります。残りの値は、優先キューを維持する方法で抽出後にシフトする必要があります。キューは平衡二分木を表すため、このシフトは最悪の場合O（logV）で発生する可能性があります。

  2. 優先キューが更新されます。新しい頂点に付随するエッジは、キューでコストを更新する必要がある場合があります。これは、新しく追加された頂点とその隣接する頂点の間のエッジに関連するコストを考慮するためです（ただし、以前に追加された頂点をエッジを介して隣接している場合は、新しく導入されたエッジよりも低コストであるため、最小コストを探しているため、コストは更新されません）。最悪の場合、キューを表す平衡二分木の全長にわたって頂点をシフトする必要があるため、これもO（logV）になります。

ステップ1はwhileループで1回発生するため、V回発生し、合計でO（VlogV）になります。また、ステップ2は、すべてのエッジが現在の頂点に接続されているため、すべてを更新する必要がある最悪の場合、E回発生します。 、これはO（ElogV）合計であることを意味します。セットアップはO（E）です。これは、優先キューの各エッジコストを無限大に初期化する必要があるためです。

最小ヒープベースのプライバシーキューを使用した合計時間計算量=O（E + VlogV + ElogV）= O（ElogV）

複雑さがO（V ^ 2）であることを読んでいるときは、ヒープを使用しない実装を見ているかもしれません。この場合、外側のwhileループはまだO（V）です。ボトルネックは、MSTに追加する次の頂点（O（V））を選択するステップにあります。これは、すべての隣接ノードに関連付けられたコストをチェックして最低コストを見つける必要があるためです。これは、最悪の場合、すべてをチェックすることを意味します。他のノード。したがって、複雑さはO（V * V）= O（V ^ 2）です。

さらに、非常に密なグラフのO（ElogV）はO（V ^ 2）になります。これは、どのグラフでも最大でE = V^2の合計エッジが存在する可能性があるためです。

于 2018-11-30T23:31:57.313 に答える