Complexité des algorithmes – O(log n), O(n), O(n log n), O(n²) et course de tris

InformatiqueAlgorithmique et résolution de problèmes15–16 ans

Un graphique trace le nombre d’étapes en fonction de la taille n des données pour les fonctions log₂n, n, n·log₂n et n², avec le nombre de comparaisons mesuré en direct pour le tri à bulles et le tri rapide. Les élèves font glisser le repère n sur le graphique pour lire les valeurs, puis cliquent sur Course pour voir les deux algorithmes trier le même tableau au même rythme : le tri rapide (n log n) termine avant le tri à bulles (n²), et l’écart grandit quand n augmente.