Prims Algorithmus Zeit Komplexität

Question

Ich schaute auf die Wikipedia entry für Prim-Algorithmus und ich bemerkte, dass seine Zeit Komplexität mit einer Adjazenz-Matrix ist O (V^2) und seine Zeit Komplexität mit einer Heap und Adjazenzliste ist O (E lg (V)) wobei E die Anzahl der Kanten und V die Anzahl der Eckpunkte im Graphen ist.

Da Prims Algorithmus in dichteren Graphen verwendet wird, kann E sich V^2 annähern, aber wenn dies der Fall ist, wird die Zeitkomplexität mit einem Haufen zu O (V^2 lg (V)), was größer ist als O (V ^) 2). Offensichtlich verbessert ein Heap die Leistung, anstatt nur das Array zu durchsuchen, aber die Komplexität der Zeit sagt etwas anderes.

Wie verlangsamt sich der Algorithmus tatsächlich mit einer Verbesserung?

Answer 1

Obwohl der Heapspeicher das Durchsuchen des Arrays verhindert, wird der "Update" -Teil des Algorithmus verlangsamt: Array-Aktualisierungen sind O (1), während Heap-Aktualisierungen O (log (N)) sind.

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

Egal was, Sie müssen N-mal suchen. In dichten Diagrammen müssen Sie jedoch viel aktualisieren (~ V^2), und in dünnen Diagrammen nicht.

Ein weiteres Beispiel aus der Spitze meines Kopfes ist die Suche nach Elementen in einem Array. Wenn Sie es nur einmal machen, ist die lineare Suche die beste - aber wenn Sie viele Abfragen durchführen, ist es besser, sie zu sortieren und die binäre Suche jedes Mal zu verwenden.

Answer 2

Ich denke, Sie haben es bis zu einem gewissen Grad falsch gelesen. Für dichte Graphen spricht der Artikel über die Verwendung von Fibonacci-Heaps mit der Zeitkomplexität O (E + V log V), was signifikant besser ist.

Answer 3

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) 

Die Verwendung unterschiedlicher Datenstrukturen verursacht unterschiedliche Zeitkomplexitäten.