5

プリム法とクラスカル法の2つのアルゴリズムを比較しています。

時間計算量の基本的な概念と、2つが最適に機能する場合（スパース/密グラフ）を理解しています

これはインターネットで見つけましたが、英語に変換するのに苦労しています。

dense graph:  Prim = O(N2)
              Kruskal = O(N2*log(N))

sparse graph: Prim = O(N2)
              Kruskal = O(N log(N))

少し長めですが、ここで何が起こっているのか誰かが説明できますか？

4

6 に答える 6

5

PrimはO（N ^ 2）です。ここで、Nは頂点の数です。

クラスカルはO（E log E）です。ここで、Eはエッジの数です。「ElogE」は、エッジをソートする優れたアルゴリズムに由来します。その後、線形E時間で処理できます。

密グラフでは、E〜N^2。したがって、クラスカルはO（N ^ 2 log N ^ 2）になり、これは単純にO（N ^ 2 log N）になります。

于 2009-12-15T14:57:30.373 に答える
3

OK、ここに行きます。O（N2）（2 = 2乗）は、大きなNのアルゴリズムの速度がNの2乗として変化することを意味します。したがって、グラフのサイズが2倍になると、計算に4倍の時間がかかります。

クラスカル行は単純化されているだけであり、E = c * N2。cここではおそらく定数であり、Nが大きくなるにつれてNよりも大幅に小さくなると想定できます。次の対数の法則を知っておく必要があります：log(ab) = log a + log bおよびlog(a^n) = n * log a。これらの2つを、log c << log N（はるかに小さく、無視できる）という事実と組み合わせると、そこでの簡略化を理解できるはずです。

さて、元の表現とそれらがどこから派生したかについては、それらを取得したページを確認する必要があります。しかし、プリム法とクラスカル法を見ている場合は、その派生を理解できると思います。少なくとも、説明できない場合は、長期的には実際には役に立たないと思います。 ...

于 2009-12-15T14:56:00.187 に答える
2

クラスカルは、ノードの数ではなく、グラフのエッジの数（E）に敏感です。ただし、Primはノードの数（N）によってのみ影響を受け、に評価されO(N^2)ます。

これは、エッジの数がN ^ 2（接続されているすべてのノード）に近づく密グラフでは、の複雑さの係数O(E*log(E))はほぼに等しいことを意味しO(N^2*log(N))ます。

cは、「ほぼ」を説明する定数であり、O表記には関係ありません。また、log（N ^ 2）はlog（N）と同じ桁数であり、対数は2の累乗を大幅に上回ります（log(N^2) => 2*log(N)O表記ではO(log(N))）。

スパースグラフでは、EはNに近く、を与えますO(N*log(N))。

于 2009-12-15T14:57:13.727 に答える
1

2つのアルゴリズムでは、異なる入力（ノードとエッジ）に対してbig-Oが定義されています。したがって、それらを比較するために、一方を他方に変換しています。

Nはグラフ内のノードの数、Eはエッジの数です。

密グラフの場合、O（N ^ 2）エッジがあります

スパースグラフの場合、O（N）エッジがあります。

もちろん、定数はbig-Oには無関係であるため、cはドロップアウトします。

于 2009-12-15T14:56:05.270 に答える
1

密グラフでは、エッジの数はO（N ^ 2）であるのに対し、疎グラフでは、エッジの数はO（N）であると考えられます。したがって、彼らはO（E \ lg E）を取得し、プリムのO（N ^ 2）の実行時間と直接比較するために、このEの近似値で拡張しています。

基本的に、クラスカル法はスパースグラフに適し、プリム法は密グラフに適していることを示しています。

于 2009-12-15T14:56:07.660 に答える
0

まず、nは頂点の数です。

プリムはO（n ^ 2）で、その部分は十分に簡単です。

クラスカルはO（Elog（E））です。ここで、Eはエッジの数です。密グラフでは、N個が2つのエッジを選択します。これはおよそn ^ 2です（実際にはn（n-1）/ 2ですが、誰が数えているのでしょうか）。したがって、およそn ^ 2 log（n ^ 2）です。 ）これは2n ^ 2 log nであり、O（n ^ 2logn）はO（n ^ 2）よりも大きいです。

スパースグラフでは、エッジがn個しかないため、O（n ^ 2）よりも小さいnlognがあります。

于 2009-12-15T14:59:54.923 に答える