Comment la complexité temporelle de l'algorithme de Prim est ElogV en utilisant Q prioritaire?

Question

code de pseudo qui je:

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;

D'après ma compréhension:

• 1 ligne: exécute les temps de V-1
.
• Ligne 2: Somme des degrés de tous les temps des sommets ... ..that est temps de 2E

Pour chaque ligne 2: Ligne 3 et la ligne 4 Prenez le temps de log E parce que nous ajoutons / suppression de tous les bords vers / depuis l'PQ un par un.

= au total time V-1+2E.logE = E.log E

Mais le livre dit qu'il est E.logV, pourriez-vous expliquer pourquoi?

Answer 1

O (log (V)) et O (log (E)) sont les mêmes.

• E est au plus V ² .
• log (V ² ) = 2 * log (V)
• qui est un O (log (v))

Answer 2

  

pour tous les bords e (s, t) incident à s

Combien de bords un s de nœud peut avoir au plus
V-1 au plus. Ainsi, les opérations ont PQ O (logV) la complexité du temps.