Prim-Algorithmus Zeitkomplexität

Question

Ich war auf der Suche auf der Seite Wikipedia-Eintrag für Prim-Algorithmus und ich bemerkte, dass seine Zeit Komplexität, die mit einer Adjazenzmatrix O (V ^ 2) und dessen Zeitkomplexität mit einem Haufen und Adjazenzliste O (E lg (V)), wobei E die Anzahl der Kanten, und V ist die Anzahl der Knoten in dem Graphen ist.

Da Prim-Algorithmus in dichteren Graphen verwendet wird, kann E V ^ 2, nähern sich aber, wenn es der Fall ist, die Zeitkomplexität mit einem Haufen wird O (V ^ 2 lg (V)), die größer ist als O (V ^ 2 ). Offensichtlich wird ein Haufen Verbesserung der Leistung einfach über den Array suchen, aber die Zeit Komplexität etwas anderes sagt.

Wie langsam der Algorithmus tatsächlich mit einer Verbesserung nach unten?

Answer 1

Auch wenn der Haufen Sie erspart durch die Anordnung der Suche, verlangsamt es die "update" Teil des Algorithmus: Array-Updates sind O (1), während Heap-Updates sind O (log (N))

Im Wesentlichen handeln Sie Geschwindigkeit in einem Teil des Algorithmus für die Geschwindigkeit in einem anderen.

Egal was passiert, werden Sie N-mal suchen. Doch in dichten Graphen, müssen Sie eine Menge (~ V ^ 2) und in lichten Graphen aktualisieren, können Sie dies nicht tun.

Ein weiteres Beispiel aus der Spitze von meinem Kopf ist für Elemente in einem Array zu suchen. Wenn Sie es nur einmal tun, lineare Suche ist die beste -. Aber wenn Sie viele Anfragen zu tun, dann ist es besser, sie zu sortieren und jedes Mal, binäre Suche verwenden

Answer 2

Von der Einführung in Algorithmen (Carmen)

Time = Θ (V) · T (EXTRACT-MIN) + Θ (E) · T (DECREASE-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)

unterschiedliche Datenstrukturen verursacht verschiedene Zeit Komplexität.

Answer 3

Ich glaube, Sie es bis zu einem gewissen Grad falsch gelesen. Für dichte Graphen, häuft die Artikel spricht über Fibonacci Verwendung mit Zeitkomplexität O (E + V log V), die deutlich besser ist.