En fait, la complexité s'obtient en considérant le pire cas pour un problème. C'est à dire que tu part toujours du pire cas pour l'algorithme que tu considères.
Exemple concret:
Je prend 'buble sort'. C'est un tri qui considère les élements d'une liste deux à deux et qui les tri.
Par exemple:
3, 4, 1, 8
On prend d'abord 3 et 4, 4 est plus grand que 3 donc on le met devant:
4, 3, 1, 8
On considère ensuite 3 et 1. Là, 3 est plus grand que 1, on laisse comme ça.
Puis, 1 et 8.
4, 3, 8, 1
Et ainsi de suite jusqu'à ce que l'on ne puisse plus rien changer.
4*, 3*, 8, 1
4, 3*, 8*, 1
4, 8, 3*, 1*
4*, 8*, 3, 1
8, 4*, 3*, 1
8, 4, 3*, 1*
Et enfin un dernier tour où rien ne change.
Ici, le pire cas est lorsque la liste est inversée par rapport à l'ordre initial. On évalue donc la complexité de cet algorithme à: O(n^2)
Car passer à travers la liste une fois et comparer les éléments deux à deux requière n (le nombre d'élements) et comme la liste est inversée, on doit le faire n fois. Donc n*n = n^2.
Et voila. :-)
Ah oui, je tiens à préciser que la meilleur complexité pour les algos de tri c'est en O(n*log(n)) (quicksort) et pas en O(n).
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Alan_T . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 10.