En fait ici on doit avoir a = n2 au max :
le nombre d'arête c'est au maximum le nombre de couple de sommets, t'as n sommets, donc le nombre de sommets = a = n2 (tu fais le produit cartésien, il doit y en avoir moins mais on s'en fout ici, on fait du O(n2) )
Donc on a pas du tout besoin de la constante "a" ici, c'est même incorrect d'en faire une constante puisqu'il varie potentiellement avec la taille du graphe, et qu'on sait le compter dans le pire des cas, si je me trompe pas.
[^] # Re: Spanning tree
Posté par thoasm . En réponse au journal Informatique fondamentale : chemins dans un graphe. Évalué à 2.
le nombre d'arête c'est au maximum le nombre de couple de sommets, t'as n sommets, donc le nombre de sommets = a = n2 (tu fais le produit cartésien, il doit y en avoir moins mais on s'en fout ici, on fait du O(n2) )
Donc on a pas du tout besoin de la constante "a" ici, c'est même incorrect d'en faire une constante puisqu'il varie potentiellement avec la taille du graphe, et qu'on sait le compter dans le pire des cas, si je me trompe pas.
Donc du coup O(a+n2) = O( n2 + n2) = O(n2)