Kruskal ללא מיון

Kruskal ללא מיון

Eliran (guest) 28 Nov 2014 07:08

I wanted to know, do we consider Kruskal's algorithm, while given a sorted list of the edges, as linear? since it's O(E*alpha(V)).

Re: Kruskal ללא מיון

Shai V 28 Nov 2014 09:57

The nice thing (or not, depending on your perspective) about a theory course is that things are black or white. We do not get to decide. Something is either linear or it isn't.

Eliran (guest) 28 Nov 2014 14:54

So in Q8 in EX2, if I use an algorithms which applies Kruskal without the sorting part, which is indeed O(E*alpha(V)), I can't say I meet the question's requirements? (linear algorithm).

Shai V 29 Nov 2014 06:54

That is correct.