Wie Prim-Algorithmus Zeitkomplexität verwendet ElogV Priority Q?

Question

Pseudo-Code, die ich verwendet:

for all V vertices: visited[n]=0

pick any vertex r from graph and set visited[r]=1

For all edges e incident to r
PQ.insert()

while(PQ is not empty)//line 1
  f=PQ.min()//f(r,s) is such that visited[s]=0
  for all edges e(s,t) incident to s//line 2
     if(visited[t]==0)
        PQ.insert(e);//line 3
     else
        PQ.delete(e);//line 4
  visited[s]=1;
end while;

Nach meinem Verständnis:

• Zeile 1: führt V-1 mal
.
• Zeile 2: Summe der Grad aller Ecken mal ... ..das 2E mal
ist

Für jede Zeile 2: Linie 3 und Linie 4 nehmen log E Zeit, weil wir hinzufügen / löschen alle Kanten zum / vom PQ eins nach dem anderen.

So Gesamt time = V-1+2E.logE = E.log E

Aber das Buch sagt, es E.logV ist, könnten Sie erklären, warum das so ist?

Answer 1

O (log (V)) und O (log (E)) gleich sind.

• E ist höchstens V ² .
• log (V ² ) = 2 * log (V)
• , die ein O (log (V))

Answer 2

  

für alle Kanten e (s, t) Vorfall s

Wie viele Kanten ein Knoten s kann höchstens haben?
V-1 höchstens. So, PQ-Operationen haben O (LogV) Zeitkomplexität.