Provient du message de Actarus78
certes,certes,mais on peut trés bien conduire un voiture sans rien connaître en thermodynamique des moteurs.
mais ça paraitrait incroyable qu'un pilote de F1 ne sache pas comment marche un moteur à explosion.
Je bosse dans l'informatique de gestion pour l'industrie,mais j'imagine que dans le monde de l'informatique en temps réel où les choses se jouent au millième de seconde,comprendre et écrire des méthodes de tri est trés important....
je crois que tu n'as pas compris la notion de complexité...
ce qui est important ce n'est pas de gagner quelques microsecondes par élément, c'est comment se comporte le temps que tu met à trier en fonction du nombre d'éléments à trier.
tri linéaire : si tu met 1 seconde pour trier 1 élément, tu mettras 1000 secondes pour en trier 1000 (on peut montrer qu'il est impossible de trier en temps linéaire sauf cas très particuliers)
tri quadratique : si tu met 1 seconde pour trier 1 élément, tu en mettras 4 pour en trier 2, 100 pour en trier 10, 1.000.000 pour en trier 1.000.
il est inutile d'optimiser à fond un algorithme quadratique si on sait faire un algorithme linéaire, par exemple. (pour information, pour le tri, un algorithme optimal est en n.log(n).
Il existe différents algorithmes ayant une telle complexité, les plus connus sont tri-fusion (facile à comprendre) et heap sort (tris en tas, très peu intuitif mais très efficace pour de grosses listes). On peut aussi citer quicksort, qui est en moyenne plus rapide mais qui dans le pire cas se trouve quadratique.
|