11

プリムのアルゴリズムのウィキペディアのエントリを見ていましたが、隣接行列を使用した時間の複雑さが O(V^2) であり、ヒープと隣接リストを使用した時間の複雑さが O(E lg(V)) であることに気付きました。ここで、E はV はグラフの頂点の数です。

Prim のアルゴリズムはより密なグラフで使用されるため、E は V^2 に近づくことができますが、近づくと、ヒープの時間計算量は O(V^2 lg(V)) になり、O(V^2) よりも大きくなります。明らかに、ヒープは単に配列を検索するよりもパフォーマンスを向上させますが、時間の複雑さはそうではありません。

改善によってアルゴリズムの速度が実際にどのように低下​​するのでしょうか?

4

3 に答える 3

12

ヒープを使用すると配列を検索できなくなりますが、アルゴリズムの「更新」部分の速度が低下します。配列の更新はO（1）であり、ヒープの更新はO（log（N））です。

本質的には、アルゴリズムのある部分の速度を別の部分の速度と交換します。

何があっても、N回検索する必要があります。ただし、密グラフでは、多くの更新（〜V ^ 2）が必要になりますが、疎グラフでは更新しません。

私の頭の上の別の例は、配列内の要素を検索することです。一度だけ実行する場合は線形検索が最適ですが、クエリを大量に実行する場合は、毎回並べ替えてバイナリ検索を使用することをお勧めします。

于 2009-04-04T02:15:15.733 に答える
3

アルゴリズムの紹介から (カルメン)

時間= Θ(V)・T(EXTRACT-MIN) + Θ(E)・T(DECREASE-KEY)

                   T(EXTRACT-MIN) T(DECREASE-KEY) 合計

1. 配列 O(V) O(1) O(V^2)
2. バイナリヒープ O(lgV) O(lgV) O(E lgV)
3. フィボナッチヒープ O(lgV) O(1) O(E + VlgV)

異なるデータ構造を使用すると、時間の複雑さが異なります。

于 2010-12-08T06:48:58.287 に答える
0

ある程度読み方を間違っていると思います。密度の高いグラフの場合、この記事では、時間計算量が O(E + V log V) のフィボナッチ ヒープを使用することについて説明しています。これは、大幅に優れています。

于 2009-04-04T02:40:25.923 に答える