Complessità temporale e spaziale
Lezione 7 di 9 del corso Algoritmo di Prim - Algoritmi sui grafi di Coddy.
Complessità temporale:
- La versione che esamina gli archi qui ha complessità O(V * E): V-1 iterazioni, ognuna delle quali esamina tutti gli E archi. Con un heap binario e liste di adiacenza, Prim ha complessità O((V + E) log V).
Complessità spaziale:
- O(V) per l'array
inTree(oltre agli archi di input).
Riepilogo:
- Prim fa crescere un albero, aggiungendo sempre l'arco meno costoso che lo collega a un vertice esterno, finché non sono inclusi tutti i vertici.
- Produce lo stesso peso totale minimo di Kruskal, usando una strategia diversa.
Provalo tu
Questa lezione non include una sfida di codice.
Mettiti alla provaQuesta lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.
Tutte le lezioni di Algoritmo di Prim - Algoritmi sui grafi
2L'algoritmo
Come funziona?PseudocodiceImplementazione (Parte 1)Implementazione (Parte 2)
Complessità temporale e spazialeEsercitati da solo: Compilatore C online