Geek Answers Handbook

Stuck with a note O

I compare two algorithms: Prim and Kruskal's.

I understand the basic concept of time complexity and when both work better (sparse / dense graphs)

I found this on the Internet, but I try to convert it to English.

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

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

It's a little long shot, but can anyone explain what is going on here?

+5
source share
6 answers

Prim is O (N ^ 2), where N is the number of vertices.

Kruskal - O (E log E), where E is the number of edges. "E log E" comes from a good edge sorting algorithm. You can then process it in linear time E.

In the dense graph E ~ N ^ 2. So Kruskal would be O (N ^ 2 log N ^ 2), which is just O (N ^ 2 log N).

+5

, . O (N2) (2 = ) , N N - .

, E = c * N2. c , -, , , N, N . : log(ab) = log a + log b log(a^n) = n * log a. , log c < log N ( ) .

, , , . , Prim Kruskal, , , , , ...

+3

Kruskal (E) , . Prim (N), evaluting to O(N^2).

, , N ^ 2 ( ), O(E*log(E)) O(N^2*log(N)).

- , "" O. , log (N ^ 2) , log (N), 2 (log(N^2) => 2*log(N), O O(log(N))).

E N, O(N*log(N)).

+2

-O, ( ). , .

N - E - .

O (N ^ 2) Edges

O (N) Edges.

, O, c

+1

, O (N ^ 2), - O (N). O (E\lg E) E, Prim O (N ^ 2).

, , Kruskal , Prim .

+1

-: n - .

Prim - O (n ^ 2), .

Kruskal - 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)

The sparse graph has only n edges, so we have n log n that is less than O (n ^ 2).

0
source

More articles:


All Articles