Prim de l'Algorithme de Complexité temporelle

J'ai été à la recherche à la L'entrée de Wikipedia pour l'algorithme de Prim et j'ai remarqué que son temps de la complexité grâce à une matrice de contiguïté est O(V^2) et de la complexité avec un segment et de la liste d'adjacence est O(lg E(V)) où E est le nombre d'arêtes et V est le nombre de sommets dans le graphe.

Depuis Prim de l'algorithme est utilisé dans plus dense graphiques, E approche V^2, mais quand il le fait, la complexité du temps avec un tas devient O(V^2 lg(V)) qui est supérieure à O(V^2). De toute évidence, un segment de mémoire pour améliorer les performances sur juste une recherche dans le tableau, mais la complexité du temps dit le contraire.

Comment fonctionne l'algorithme de ralentir avec une amélioration?

OriginalL'auteur kevmo314 | 2009-04-04

  1. 11

    Même si le segment de mémoire vous permet d'économiser de la recherche par le biais de la matrice, il ralentit la "mise à jour" de la partie de l'algorithme: tableau des mises à jour sont en O(1), alors que des tas de mises à jour sont en O(log(N)).

    En essence, vous le commerce de vitesse dans une partie de l'algorithme pour la vitesse de l'autre.

    N'importe quoi, vous aurez à chercher N fois.
    Cependant, dans les graphiques, vous aurez besoin de mise à jour de beaucoup (~V^2), et dans éparses graphiques, vous n'avez pas.

    Un autre exemple se trouve sur le dessus de ma tête est à la recherche d'éléments dans un tableau.
    Si vous êtes seulement à faire une fois, la recherche linéaire est le meilleur - mais si tu fais beaucoup de requêtes, il est préférable de les trier et utiliser les binaires de recherche à chaque fois.

    OriginalL'auteur v3.

  2. 3

    De l'Introduction aux Algorithmes (Carmen)

    Temps= Θ(V)·T(EXTRAIRE-MIN) + Θ(E)·T(DIMINUTION-CLÉ)

     T(EXTRAIRE-MIN) T(DIMINUTION-CLÉ) Total 

1. la matrice de O(V) O(1) O(V^2) 
2. tas binaire O(lgV) O(lgV) O(E lgV) 
3. Fibonacci tas O(lgV) O(1) O(E + VlgV)

    À l'aide de différentes structures de données sont les causes des différents temps de complexités.

    OriginalL'auteur

  3. 0

    Je pense que vous lisez mal à un certain degré.
    Pour les dense graphiques, l'article porte sur l'utilisation des tas de Fibonacci avec le temps, la complexité de O(E + V log V), ce qui est nettement mieux.

    Mais même si, E->V^2, la complexité du temps atteint O(V^2+Vlog(V)) qui est supérieure à O(V^2).
    -1 désolé. kevmo314 commentaire qui explique pourquoi.
    O(V^2+Vlog(V)) == O(V^2) Qui devrait être évident, après la prise d'un des algorithmes de parcours de...
    Mon point principal était qu'il kevmo314 lire l'article de mal à un certain degré. L'article dit que des tas de Fibonacci sont utilisés dans les graphiques suffisamment dense que E = w(v). L'article ne fait pas mention de l'aide de l'algorithme de Prim pour plus denses graphes, il mentionne les tas de Fibonacci. Suffisamment Dense que E=w(V) ne pas E=w(V^2).
    Je ne pense pas qu'il a fait; il a noté que la complexité pour les deux tas de méthodes ont été pire que l'approche de base, ce qui le surprit. Vous avez raison sur ce que le dit l'article sur les tas de Fibonacci, mais qui n'a presque rien à voir avec l'OP

    OriginalL'auteur RAL