Perché la complessità temporale dell'algoritmo di Prim non è $ | v || e | lg | v | $ ma $ | e | lg | v | $?

Question

Nei clrs, la complessità del tempo dell'algoritmo di Prim è $ o (| v | lg | v |+| e | lg | v |) = o (| e | lg | v |) $.

Ma, per la mia comprensione, l'algoritmo di Prim itera $ | e | $ tempi per l'operazione di riduzione che prende $ O (lg | v |) $ tempi e porta a $ o (| e | lg | v |) $.

Quindi, itera $ | v | $ tempi allora, penso che $ o (| e || v | lg | v |) $ sia giusto perché la complessità del tempo intero è come sotto.

1. Inizializzazione della chiave e del predecessore + Creazione di un heap binario = $ o (| v |) $
2. Operazione Extract-Min = $ O (| V | LG | V |) $
3. L'operazione di riduzione della chiave è iterata per $ | v | $ tempi = $ o (| e || v | lg | v |) $

Di conseguenza, $ o (| v |+| v | lg | v |+| e || v | lg | v |) = o (| e || v | lg | v |) $.
Perché è $ o (| e | lg | v |) $?

---

Da 2 risposte, prima mentre loop itera $ | v | $ tempi e $ diminuisce $ operazioni iterate $ | e | $ tempi e complessità del tempo di quell'operazione è $ o (lg | v |) $ perché il mucchio di min deve essere ricostruito.

Da questo, ho ottenuto un $ o (| v || e | lg | v |) $ perché per loop è nel ciclo. Ciò che le tue risposte dicono è che non conosco $ Diming-Key $ Operation itera $ | E | $ tempi, ma lo so.