Pourquoi la complexité temporelle de l'algorithme de Prim n'est pas $ | v || e | lg | v | $ mais $ | e | lg | v | $?

Question

Dans les CLR, la complexité temporelle de l'algorithme de Prim est $ o (| v | lg | v | + | e | lg | v |) = o (| e | lg | v |) $.

Mais, à ma compréhension, l'algorithme de Prim itère $ | e | $ Times pour une opération de clé de diminution qui prend $ o (lg | v |) $ fois et cela conduit à $ o (| e | lg | v | v |) $.

Donc, il itère $ | v | $ fois alors, je pense que $ o (| e || v | lg | v |) $ est juste car la complexité du temps entier est comme ci-dessous.

1. Initialisation de la clé et du prédécesseur + faisant un tas binaire = $ o (| v |) $
2. Opération extrait-min = $ o (| v | lg | v |) $
3. L'opération de clé de diminution est itérée pour $ | v | $ times = $ o (| e || v | lg | v |) $

Par conséquent, $ o (| v | + | v | lg | v | + | e || v | lg | v |) = o (| e || v | lg | v |) $.
Pourquoi est-ce $ o (| e | lg | v |) $?

---

À partir de 2 réponses, tout d'abord tandis que Loop itère $ | v | $ Times et $ diminrease-key $ opération itère $ | e | $ Times et la complexité du temps de cette opération est $ o (lg | v |) $ parce que Min tas doit être reconstruit.

À partir de cela, j'ai un $ o (| v || e | lg | v |) $ parce que pour la boucle est en boucle. Ce que vos réponses disent, c'est que je ne sais pas $ diminue-key $ opération itère $ | e | $ fois, mais je le sais.