[Analisi della complessità] Dubbio sull'algoritmo di Prim

[Pablitos23]

E' il seguente e serve a calcolare il minimo albero di copertura dato un grafo G non diretto, pesato e connesso.

Prim ( G: grafo non diretto, pesato e connesso )

   P: vettore dei padri inizializzato a 0
   P[s] <- s
   H <- min_heap   /*dei costi inizializzati a infinito eccetto s a 0 */
   
   while H.size > 0 do
      u <- H.get_min()

      for ogni adiacente v di u do

         if v in H AND p{u,v} < H.costo(v) then
            P[v] <- u
            H.decreade(v,p{u,v})   /* aggiorna il costo di v e l'heap */

return P

Complessità:

Iterazioni del while -> O(n)
Ad ogni iterazione del while estraggo il min dall'heap -> O(logn)

Fin qui abbiamo O(nlogn)

tempo necessario per scorrere la lista delle adiacenze del nodo estratto, assegnazione al vettore dei padri e aggiornamento dell'heap -> O(mlogn)

TOT = O((n+m)logn)

Fin qui ci sono. La dispensa dove sto studiando dice che l'algoritmo di Prim potrebbe usare per mantenere i costi dei nodi no un minHeap ma un semplice array, dove l'estrazione del nodo col costo minimo impiegherebbe O(n) e il controllo di un adiacente O(1). Quindi questa implementazione ha una complessità pari a $O(n^2)$.

E' dunque conveniente, rispetto a quella che usa un minHeap, solo quando il grafo è molto denso.

Non capisco il perchè di quest'ultima affermazione. Non è sempre più conveniente l'implementazione con il minHeap?

Buona giornata

[apatriarca]

Sono un po' di fretta e non ho tempo di guardare bene il codice e l'analisi della complessità relativa. Guardando quello che hai scritto immagino però che la frase si riferisca al termine \(m\) nella tua complessità totale (che immagino rappresenti il numero di archi del grafo). Se tutti i nodi fossero collegati tra di loro avresti \(n^2\) archi. Nel caso di grafi molto densi hai quindi che \( m \in O(n^2)\) e quindi la tua complessità diventa \( O(n^2\,\log\,n)\) che è peggiore della complessità ottenuta usando semplicemente un array.

[Pablitos23]

Quindi se tutti i nodi fossero collegati tra di loro avrei al massimo $(n(n-1))/2$ e quindi asintoticamente $O(n^2)$.

Ho capito grazie mille.