arrays - プリムのアルゴリズムに配列と優先度キューをそれぞれいつ使用するか?

Question

これは過去の試験問題です。

(V, E) のどの条件の下で、(Extract-Min 操作と Decrease-Key 操作の両方の対数時間実装を使用して) ヒープではなく配列 (頂点によってインデックス付けされる) を使用して Prim のアルゴリズムの最小優先度キューを実装する必要がありますか? )?

(V, E) のどの条件の下で、順序付けられた配列を使用して Prim のアルゴリズムの最小優先度キューを実装する必要がありますか?

Answer 1

Prim は O(mlog(n)) 時間で実行され、バイナリ ヒープの実装と m はエッジの数、n は頂点の数です。ただし、グラフが非常に密集している場合、m は非常に大きく、Prim は O(n^2log(n)) で実行されます。多数(n)の頂点を持つグラフを作成し、すべての頂点を互いに接続して、これを納得させることができます。そう.... (n-1) + (n-2) + (n-3) ...... (n-n+1)。

これは次のように書き直すことができます。

n(n+1)/2 は O(n^2) であり、

優先度キュー配列の実装は O(n^2) 時間で実行されます。これはウィキペディアのページに記載されていますが、その証拠はありません。

したがって、m が非常に大きい場合は、隣接行列を使用することをお勧めします。

あなたは条件を求めましたが、m が非常に大きく、n と同じ次数である場合に答えます。

Answer 2

E が大きい場合、キューに多くのノードがあるため、優先度キューにヒープを使用することをお勧めします。配列 O(n)/O(n) から min を見つける/削除するには時間がかかりますが、ヒープは O(1)/log(n) しかかかりません。

E が小さい場合、キューにノードがほとんどないため、この場合、min を見つけて配列から削除するのに多くの操作は必要ありません。この場合、ヒープを使用する必要はなく、ヒープの構築に必要な操作のために配列よりも遅くなる可能性さえあります。