MST: Prims Algorithmuskomplexität, warum nicht

8

Laut CLRS sind die Algorithmen des Prim wie folgt implementiert:

MST-PRIM(G,w,r)

  • für jedes tunuV[G]
    • Schlüssel[u]]
    • π[u]]NULL
  • Schlüssel[r]]0
  • Q.V.[G]]
  • während Q. tun // ... Ö(V.)
    • u EXTRACT-MIN(u) // ...O(lgV)
      • für jedes vadj[u] mache // ... O(E)
        • wenn vQ und w(u,v)>key[v]
          • dann π[v]u
            • // TASTE VERRINGERN ... O ( lg V )keyw(u,v)DECREASE-KEYO(lgV)

Das Buch sagt, dass die Gesamtkomplexität . Was ich jedoch verstanden habe, ist, dass die innere Schleife mit der Operation O ( E lg V ) kostet und die äußere Schleife sowohl die als auch die innere Schleife einschließt, so dass die Gesamtkomplexität O ( V ( lg V + E lg V) sein sollte ) ) = O (O(VlgV+ElgV)O(ElgV)forDECREASE-KEYO(ElgV)whileEXTRACT-MINfor .O(V(lgV+ElgV))=O(VlgV+EVlgV)O(EVlgV)

Warum wird die Komplexitätsanalyse nicht als solche durchgeführt? und was ist falsch an meiner Formulierung?

Ramgorur
quelle

Antworten:

9

Die Komplexität wird wie folgt abgeleitet. Die Initialisierungsphase kostet O(V) . Die while Schleife ausgeführt |V|mal. Die for innerhalb der verschachtelten Schleife while Schleife wird ausgeführt , degree(u) mal. Schließlich impliziert das Handshake-Lemma, dass es Θ(E) implizite DECREASE-KEYs gibt. Daher ist die Komplexität: Θ(V)TEXTRACTMIN+Θ(E)TDECREASEKEY .

Die tatsächliche Komplexität hängt von der tatsächlich im Algorithmus verwendeten Datenstruktur ab. Unter Verwendung eines Arrays ist TEXTRACTMIN=O(V),TDECREASEKEY=O(1) , die Komplexität ist O(V2) in der schlimmsten Fall.

Unter Verwendung eines binären Haufen, TEXTRACTMIN=O(logV),TDECREASEKEY=O(logV) , Komplexität O(ElogV) im schlimmsten Fall. Hier ist der Grund: Da der Graph verbunden ist, dann |E||V|1 undE ist höchstensV2 (schlimmster Fall für einen dichten Graphen). Wahrscheinlich haben Sie diesen Punkt verpasst.

Unter Verwendung eines Fibonacci-Haufens wird TEXTRACTMIN=O(logV) amortisiert, TDECREASEKEY=O(1) amortisiert, Komplexität ist O(E+VlogV) im schlimmsten Fall.

Massimo Cafaro
quelle
1

Ihre Idee scheint richtig zu sein. Nehmen wir die Komplexität als . Beachten Sie dann, dass wir in der inneren for-Schleife tatsächlich alle Eckpunkte und nicht die Kanten durchlaufen. Ändern wir also ein wenig zu V ( lg v + V lg v ) , was V lg v + V 2 lg v bedeutet . Für die Worst-Case-Analyse (dichte Graphen) ist V 2 ungefähr gleich der Anzahl der Kanten E , was V lg v + E ergibt V(lgv+Elgv)V(lgv+Vlgv)Vlgv+V2lgvV2EVlgv+Elgv=(V+E)lgvVEElgv

user3473400
quelle
Was ist? v? Ein Tippfehler fürV.?
David Richerby
Actually, I don't understand this at all. What does it mean to say "Let's take the complexity as [expression 1]" and then "modify a little to [expression 2]"? You can't just assume the running time is one thing and then change it to something else.
David Richerby