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
Utilisez-la avec votre classe : vos élèves l’ouvrent par un lien ou un QR code, sans créer de compte.
À suivre dans Algorithmique et résolution de problèmes
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.
Leçon : Évaluer un algorithme : nombre d’opérations en fonction de la taille des données, notation O, comparaison du tri à bulles et du tri rapide
Ce qu’elle montre
La complexité d’un algorithme décrit comment le nombre d’opérations augmente quand la taille des données n augmente, sans tenir compte des facteurs constants. Le graphique compare quatre croissances : log₂n monte à peine, n croît proportionnellement, n·log₂n un peu plus vite, et n² est multiplié par quatre chaque fois que n double. Les mesures confirment la théorie : sur un tableau aléatoire, le tri à bulles fait environ n²/2 comparaisons et le tri rapide environ 1,4·n·log₂n. Pour un petit n l’écart compte peu ; pour de grandes données, le choix de l’algorithme décide si un programme met des secondes ou des heures.
Mode d’emploi
Commencez avec Courbes théoriques affichées sur les quatre fonctions et faites glisser sur le graphique pour changer n, en lisant la valeur de chaque courbe. Quand les courbes sont trop éloignées pour être comparées, activez Échelle log pour l’axe des étapes. Cliquez ensuite sur Course pour que les deux algorithmes trient le même tableau au même rythme, puis recommencez avec Nouveau tableau et un n plus grand pour voir l’écart se creuser.
Paramètres modifiables
- Taille des données n 4–100
- Courbes théoriques affichées log₂n, n, n·log₂n, n², n et n², log₂n, n et n·log₂n
- Échelle log pour l’axe des étapes
- Vitesse de la course 5–200 étapes/s
Questions à explorer
- Quand n double de 50 à 100, par combien n² est-il multiplié, et environ par combien n·log₂n l’est-il ?
- Pourquoi la courbe log₂n reste-t-elle presque plate alors que la courbe n² monte fortement ?
- Pour n = 10, combien de comparaisons de plus le tri à bulles fait-il que le tri rapide, et cet écart compte-t-il en pratique ?
