Hey. J'ai une question débile pour vous !
Dans le tri par sélection à la page 2 du poly : http://info-llg.fr/commun-mp/pdf/03.tris.pdf
Ils disent que la complexité est quadratique mais c'est aussi vrai pour le meilleur des cas ? (liste déjà triée par ordre croissant)

Alors je vais laisser la réponse à ceux qui pourraient mieux s'y connaître, mais il me semble que la complexité d'un algorithme est toujours définie au pire cas donc bon, ça n'a pas tellement de sens

Oui puisqu'il faut dans tous les cas parcourir toute la liste et faire toutes les comparaisons pour aller chercher le minimum (qui est cyniquement le premier élément).

Tous les Algorithmes ont une complexité O(1) au meilleur des cas, lors du calcul d'une complexité d'un Algorithme ce n'est que le pire des cas qu'on "considère" (cf. Définition de la complexité et la notation O(machin) ). D'ailleurs tous les tris simples ont une complexité O(N²), il n'y a que le tri récursif (le plus optimal jusqu'à nouvel ordre) qui a une complexité O(n*log(n)).

"Tous les Algorithmes ont une complexité O(1) au meilleur des cas"

Ben non

iDratui à 12:07 :

Alors je vais laisser la réponse à ceux qui pourraient mieux s'y connaître, mais il me semble que la complexité d'un algorithme est toujours définie au pire cas donc bon, ça n'a pas tellement de sens

Pas du tout, la complexité en cas moyen (selon des distributions de probabilité qui peuvent être variées) est également très utilisée. Le pire cas est souvent très pessimiste par rapport à ce à quoi on peut s'attendre dans la plupart des cas.

L'auteur Même si la liste est déjà triée, tu dois la parcourir entièrement pour t'assurer que le premier élément est bien le plus petit. Donc c'est quadratique dans tous les cas.

En prépa on te demande rarement autre chose que la complexité dans le pire des cas.

Ouais blue, notamment pour le tri par insertion (quadratique à une constante multiplicative pres). Cependant, on distingue aussi le meilleurs cas par fois, pour le même tri, la complexité devient linéaire. Sinon, merci à tous ! J'ai eu ma réponse.

Merci pour la réponse d'ailleurs