Temps algorithme de complexité Prim

Question

Je regardais entrée de Wikipedia pour l'algorithme de Prim et j'ai remarqué que son temps complexité avec une matrice d'adjacence est O (V ^ 2) et sa complexité temporelle avec une liste de segments de mémoire et de la contiguïté est O (E lg (V)) où E est le nombre d'arêtes et V est le nombre de sommets du graphe.

Depuis l'algorithme de Prim est utilisé dans des graphiques plus denses, E peut approcher V ^ 2, mais quand il le fait, la complexité de temps avec un tas devient O (V ^ 2 lg (V)) qui est supérieure à O (V ^ 2 ). De toute évidence, un tas améliorera les performances sur la simple recherche du tableau, mais la complexité du temps dit autrement.

Comment avec une amélioration de l'algorithme lent en fait vers le bas?

Answer 1

Même si le tas vous évite de chercher à travers le réseau, il ralentit la partie « mise à jour » de l'algorithme: les mises à jour du tableau sont O (1), tandis que les mises à jour tas sont O (log (N))

En substance, vous négociez la vitesse dans une partie de l'algorithme pour la vitesse dans un autre.

Peu importe, vous aurez à la recherche N fois. Cependant, dans les graphiques denses, vous aurez besoin de mettre à jour un lot (~ V ^ 2), et sous forme de graphiques rares, vous n'avez pas.

Un autre exemple du haut de ma tête est à la recherche d'éléments dans un tableau. Si vous faites seulement une fois, la recherche linéaire est le meilleur -. Mais si vous faites beaucoup de requêtes, il est préférable de trier et utiliser la recherche binaire à chaque fois

Answer 2

De l'introduction aux algorithmes (Carmen)

Temps = Θ (V) · T (EXTRACT-MIN) + Θ (E) · T (DIMINUTION-KEY)

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

En utilisant différentes structures de données source de complications de temps différentes.

Answer 3

Je pense que vous lisez mal dans une certaine mesure. Pour les graphiques denses, l'article parle de l'utilisation des tas de Fibonacci avec la complexité du temps O (E + V log V), ce qui est nettement mieux.