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

Utiliser avec ma classe

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. Un second écran, Voyageur de commerce, place des villes sur une carte et compare la force brute, qui examine les (n − 1)!/2 circuits et demande vite un temps déraisonnable, avec l’heuristique rapide du plus proche voisin.

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 log₂n, n, n·log₂n et n² ; les mesures montrent le tri à bulles vers n²/2 comparaisons et le tri rapide vers 1,4·n·log₂n. Certains problèmes sont bien pires. L’écran du voyageur de commerce essaie tous les circuits, soit (n − 1)!/2 : chaque ville de plus multiplie le travail, et 16 villes demanderaient des heures. Une heuristique comme le plus proche voisin répond en n(n − 1)/2 étapes, vite mais pas toujours avec le circuit le plus court.

Mode d’emploi

Faites glisser sur le graphique pour changer n et activez Échelle log pour l’axe des étapes quand les courbes sont très éloignées ; cliquez sur Course pour voir les tris. Cliquez ensuite sur Voyageur : touchez la carte pour ajouter des villes, cliquez sur Force brute et Plus proche voisin, puis comparez les circuits et les étapes. Changez Nombre de villes et Vitesse de l’ordinateur pour voir le temps exploser.

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, n, n², 2ⁿ et n!
  • Échelle log pour l’axe des étapes
  • Vitesse de la course 5–200 étapes/s
  • Écran Graphique de complexité, Voyageur de commerce
  • Nombre de villes (voyageur de commerce) 4–16
  • Graine aléatoire des villes 1–999
  • Vitesse de l’ordinateur 10⁶ étapes par seconde, 10⁹ étapes par seconde, 10¹² étapes par seconde

Questions à explorer

  1. Quand n double de 50 à 100, par combien n² est-il multiplié, et environ par combien n·log₂n l’est-il ?
  2. Pourquoi la courbe log₂n reste-t-elle presque plate alors que la courbe n² monte fortement ?
  3. 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 ?