Complessità temporale dell'algoritmo di Prim
-
23-08-2019 - |
Domanda
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?
Soluzione
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.
Altri suggerimenti
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.
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.