Complessità temporale dell'algoritmo di Prim

Question

Stavo guardando il Voce di Wikipedia per l'algoritmo di Prim e ho notato che la sua complessità temporale con una matrice di adiacenza è O(V^2) e la sua complessità temporale con un heap e un elenco di adiacenze è O(E lg(V)) dove E è il numero di archi e V è il numero di vertici nel grafico.

Poiché l'algoritmo di Prim viene utilizzato in grafici più densi, E può avvicinarsi a V^2, ma quando lo fa, la complessità temporale con un heap diventa O(V^2 lg(V)) che è maggiore di O(V^2).Ovviamente, un heap migliorerà le prestazioni rispetto alla semplice ricerca nell'array, ma la complessità temporale dice il contrario.

In che modo l'algoritmo rallenta effettivamente con un miglioramento?

Answer 1

Anche se l'heap ti evita di cercare nell'array, rallenta la parte di "aggiornamento" dell'algoritmo:gli aggiornamenti dell'array sono O(1), mentre gli aggiornamenti dell'heap sono O(log(N)).

In sostanza, scambi la velocità in una parte dell’algoritmo con la velocità in un’altra.

Non importa cosa, dovrai cercare N volte.Tuttavia, nei grafici densi sarà necessario aggiornare molto (~V^2), mentre nei grafici sparsi no.

Un altro esempio che mi viene in mente è la ricerca di elementi in un array.Se lo fai solo una volta, la ricerca lineare è la migliore, ma se fai molte query, è meglio ordinarle e utilizzare la ricerca binaria ogni volta.

Answer 2

Dalla Introduzione agli algoritmi (Carmen)

Tempo = Θ (V) · T (ESTRATTO-MIN) + Θ (E) · T (DIMINUZIONE-KEY)

                   T(EXTRACT-MIN)   T(DECREASE-KEY)   Total

1. array            O(V)             O(1)              O(V^2)
2. binary heap      O(lgV)           O(lgV)            O(E lgV)
3. Fibonacci heap   O(lgV)           O(1)              O(E + VlgV)

Utilizzando diverse strutture dati provoca diverse complessità di tempo.

Answer 3

Credo che lo si legge male in una certa misura. Per i grafici densi, i articolo parla utilizzando Fibonacci cumuli con il tempo la complessità O (E + V log V), che è significativamente migliore.