Un tri en O(n), je doute, un tri basé sur des comparaisons c'est minimum O(n*ln(n)) (ça se démontre).
La complexité tu la calcules en analysant l'algo. Par exemple, un tri par fusion:
* tu découpes ton tableau en 2
* tu tries chacune des deux moitiés
* tu fusionnes les deux
Fusionner les deux, ça prend O(n) comparaisons. Donc t(n) = 2 * t(n/2) + n . Ensuite tu as un simple problème de maths.
n lg(n) = n lg (n/2) + lg(2) n = 2 * ( n/2 lg (n/2)) + lg(2) n = 2* (n/2 lg (n /2)) + n
donc n lg(n) vérifie bien la relation de récurence, donc t(n) = n lg (n) (théorème d'unicité des suites récurentes avec conditions initiales (t(1) = 0))
J'espère que mes explications sont assez claires, mais le principe c'est ça. Bon, il manque un peu d'exactitude mathématiques, mais c'est pas le sujet.
[^] # Re: [HS ?] Ordre de complexité d'un alogrithme
Posté par Gaël Le Mignot . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 9.