MST: complexité de l'algorithme de Prim, pourquoi pas

Selon CLRS, les algorithmes de Prim sont implémentés comme ci-dessous -

$\mathtt{\text{MST-PRIM}}(G,w,r)$

• pour chaque $u \in V[G]$ faire
  
  • $\mathtt{\text{key}}[u] \leftarrow \infty$
  • $\pi[u] \leftarrow \mathtt{\text{NIL}}$
• $\mathtt{\text{key}}[r] \leftarrow 0$
• $Q \leftarrow V[G]$
• tandis que $Q \ne \emptyset$ faire // ... $O(V)$
  • $u$ $\leftarrow$ $\mathtt{\text{EXTRACT-MIN}}(u)$ // ... $O(\lg V)$
    
    • pour chaque $v \in \mathtt{\text{adj}}[u]$ faire // ... $O(E)$
      
      • si $v \in Q$ et $w(u,v) \gt \mathtt{\text{key}}[v]$
        • puis $\pi[v] \leftarrow u$
          • $\mathtt{\text{key}} \leftarrow w(u,v)$ // $\mathtt{\text{DECREASE-KEY}}$ ... $O(\lg V)$

Le livre dit que la complexité totale est $O(V \lg V + E \lg V) \approx O(E \lg V)$. Cependant, ce que j'ai compris, c'est que la forboucle intérieure avec l' DECREASE-KEYopération coûtera$O(E \lg V)$, et la whileboucle extérieure renferme à la fois la boucle EXTRACT-MINintérieure et la forboucle intérieure , de sorte que la complexité totale doit être$O(V (\lg V + E \lg V)) = O(V \lg V + EV \lg V) \approx O(EV \lg V)$.

Pourquoi l'analyse de complexité n'est pas effectuée en tant que telle? et Quel est le problème avec ma formulation?

La complexité est dérivée comme suit. La phase d'initialisation coûte$O(V)$. le$while$ la boucle est exécutée $\left| V \right|$fois. le$for$ boucle imbriquée dans le $while$ la boucle est exécutée $degree(u)$fois. Enfin, le lemme de prise de contact implique qu'il existe$\Theta(E)$DECREASE-KEY implicites. Par conséquent, la complexité est:$\Theta(V)* T_{EXTRACT-MIN} + \Theta(E) * T_{DECREASE-KEY}$.

La complexité réelle dépend de la structure de données réellement utilisée dans l'algorithme. En utilisant un tableau,$T_{EXTRACT-MIN} = O(V), T_{DECREASE-KEY} = O(1)$, la complexité est $O(V^2)$ au pire des cas.

En utilisant un tas binaire, $T_{EXTRACT-MIN} = O(\log V), T_{DECREASE-KEY} = O(\log V)$, la complexité est $O(E \log V)$au pire des cas. Voici pourquoi: puisque le graphe est connecté, alors$\left| E \right| \ge \left| V \right| - 1$, et $E$ est tout au plus $V^2$(pire cas, pour un graphique dense). Vous avez probablement manqué ce point.

À l'aide d'un tas de Fibonacci, $T_{EXTRACT-MIN} = O(\log V)$ amorti, $T_{DECREASE-KEY} = O(1)$ amorti, la complexité est $O(E + V \log V)$ au pire des cas.

Votre idée semble correcte. Prenons la complexité comme $V(\lg v + E\lg v)$. Ensuite, notez que dans la boucle for interne, nous traversons en fait tous les sommets, et non les bords, alors modifions un peu pour $V(\lg v + V\lg v)$, ce qui signifie $V\lg v + V^2\lg v$. Mais pour l'analyse du pire des cas (graphiques denses),$V^2$ est à peu près égal au nombre d'arêtes, $E$, donnant $V\lg v + E\lg v = (V+E)\lg v$ mais depuis $V \ll E$, Par conséquent $E\lg v$.