Come algoritmo di tempo la complessità di Prim è ElogV utilizza priorità Q?

Question

pseudo codice che ho usato:

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;

Secondo la mia comprensione:

• Linea 1: esegue volte V-1
.
• Linea 2: Somma di Grado di tutti i vertici tempi ... ..che è volte 2E

Per ogni linea 2: Linea 3 e la linea 4 richiede tempo log E perché stiamo aggiungendo / cancellando tutti i bordi da / per l'PQ uno per uno.

Così totale time = V-1+2E.logE = E.log E

Ma il libro dice che è E.logV, potrebbe spiegarci perché?

Answer 1

O (log (V)) e O (log (E)) sono gli stessi.

• E è al massimo V ² .
• log (V ² ) = 2 * log (V)
• che è un O (log (V))

Answer 2

  

per tutti i bordi e (s, t) incidente s

Quanti bordi un s nodo può avere al massimo?
V-1 al massimo. Quindi, le operazioni di PQ hanno O (logV) Tempo di complessità.