Complexité temporelle de l'Algorithme de Kruskal?

Je suis temps de calcul de la complexité de kruskal algorithme de type ce (voir l'algorithme dans l'Image ci-Jointe)

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

Le CLR de l'Algorithme:

Complexité temporelle de l'Algorithme de Kruskal?

Est-il correct ou je suis en train de faire quelque chose de mal, s'il vous plaît dites.

Merci de me dire la complexité de la ligne 4 et la ligne 5-9

OriginalL'auteur Sonali | 2013-12-06

  1. 10

    Kruskal est O(E log E), votre calcul est juste. On pourrait aussi dire que O(E log V) car E <= V * V, donc log(E) <= 2 log(V) (je ne sais pas pourquoi je me souviens que, à part que je pense qu'un prof de mettre cela sur un examen à un point...)

    Mais pourquoi est O(E log V) préférable que O(E log E)? Est-ce parce que généralement les graphiques complexités utiliser à la fois E et V dans la formule?
    Elog(V) peut être réduit ici à l'Elog(V^2) [ e = v^2 dans le pire des cas // graphe complet ] Donc Elog(V^2) <= 2Elog(V) c'est à dire Elog(V). Généralement dans les graphiques que nous utilisons à la fois e et v de cause nous ne pouvons pas remplacer e par v cause qui allait changer la complexité du temps, mais ici en raison de la présence de journal que nous le pouvons. PS: On ne peut pas écrire O(EE) S(VE) juste pour avoir ces deux variables.

    OriginalL'auteur Bandrami

  2. 4

    Depuis |V| > |E|+1, nous préférons une étroite limite supérieure avec V au lieu de E conditions.

        |E| <= |V|²   
.   log |E| < log |V|²   
.   log |E| < 2 log |V| 
.   running time of MST-KRUSKAL is: O(E log V)
    Le graphique est supposé être connecté, et donc ne devrait-il pas être |V| <= |E| + 1, depuis au minimum, vous disposez d'un arbre qui a la propriété |V| - 1 = |E| => |V| = |E| + 1. En ajoutant plus de bords, vous arrivez à un graphique avec des cycles, de sorte que |V| <= |E| + 1.
    Aussi, pour ceux qui ne peuvent pas immédiatement comprendre |E| <= |V|2, max nombre d'arêtes se produit dans un graphe où chaque sommet a un bord à tous les autres sommets. Un graphe complet a (|V| choisissez 2) les bords, qui est à moins de |V|2.

    OriginalL'auteur MOHIT KUMAR

  3. 1

    Désolé pour la réponse tardive.

    Exécution de Kruskal algorithme est O(E log E) et pas de O(E log V).

    Que, les bords doivent être triés d'abord et il faut O(E log E) d'où il domine le moteur d'exécution pour vérifier si la pointe en considération est sûr, à bord ou non, qui prendrait O( E log V). Et |E| > |V|((coin de cas si le graphe est déjà un arbre)), de sorte que son coffre-fort pour assumer le moteur d'exécution est O(E log E)

    Droit, mais E ne peut excéder V * V, ce qui signifie log(E) < 2 log(V).
    Oui, moi aussi, je trouve la même expression dans le PLC. Et je suis d'accord aussi que aussi , mais je me sens O(ElogE) serait un plus resserrement de la limite supérieure. Bottom line: O(ElogE) et O(ElogV) devrait fonctionner
    Aucune référence pour cette?
    Référence:people.cs.umass.edu/~limitation/cs611/conférence/7.pdf -- je n'ai pas vérifié complètement. Juste écrémé et a été convaincu. Donc, s'il vous plaît aller à travers avec une pincée de sel

    OriginalL'auteur letsBeePolite

  4. 0

    la ligne 5 à 9 de la complexité est de O(E).

    1. O(E)
    2. O(1)
    3. O(1)
    4. O(1)
    5. O(1)

    jusqu'à la ligne 5 vous avez calculé la complexité, à juste titre. Enfin, le facteur Dominant ici est de O(E lg E). Ainsi, la complexité est de O(E lg E)

    OriginalL'auteur Syed Ibna Zubayear