Un algorithme est une recette précise et finie qui transforme une entrée en sortie : une liste de noms en liste triée, une carte en plus court chemin, un nombre en facteurs premiers. Avant même qu’un langage de programmation entre en jeu, on peut comparer des algorithmes sur une question : quelle quantité de travail font-ils quand l’entrée grandit ?
Compter des étapes, pas des secondes
Chronométrer un programme mesure à la fois le programme, le compilateur et la machine. Pour comparer des algorithmes, on compte plutôt leurs opérations de base — comparaisons, échanges, lectures du tableau — en fonction de la taille de l’entrée n. Ce décompte ne dépend pas du CPU, et il montre comment le coût croît. Pour les grandes entrées, c’est la croissance qui compte.
Voici deux façons de chercher une valeur dans une liste de 32 nombres. La recherche linéaire examine chaque élément tour à tour. La recherche dichotomique ne marche que sur une liste triée : elle regarde le milieu, écarte la moitié qui ne peut pas contenir la valeur, et recommence.
Initial array.
Linear search — Checks every element left to right until it meets the target. Best O(1), average O(n), worst O(n).
Initial array.
Binary search — Needs sorted input: each probe of the middle element halves the range lo..hi. Best O(1), average O(log n), worst O(log n). The generated array is sorted first.
Réglez la cible sur absent — le pire cas — et regardez le graphique cost vs n sous chaque démo. La recherche linéaire fait une comparaison par élément : 8, 16, 32 … 256. La recherche dichotomique divise l’intervalle par deux à chaque étape, et il lui faut 3, 4, 5 … 8 comparaisons. Doubler l’entrée ajoute une étape. Sur un million d’éléments, cela fait 20 comparaisons contre un million.
| n | recherche linéaire | recherche dichotomique |
|---|---|---|
| 8 | 8 | 3 |
| 32 | 32 | 5 |
| 256 | 256 | 8 |
| 1 000 000 | 1 000 000 | 20 |
La notation grand O
La notation grand O décrit la croissance d’un coût en ignorant les facteurs constants et les petites entrées. Formellement, un coût f(n) est en O(g(n)) s’il existe des constantes c et n₀ telles que f(n) ≤ c·g(n) pour tout n ≥ n₀. En pratique : on garde le terme qui croît le plus vite et on oublie son coefficient. Par exemple, 3n² + 5n + 20 est en O(n²).
Les classes les plus courantes, avec le temps qu’elles prendraient pour n = 1 000 000 à raison d’une nanoseconde par étape :
| Classe | Nom | Exemple | n = 10⁶ |
|---|---|---|---|
| O(1) | constante | lire a[i] | 1 ns |
| O(log n) | logarithmique | recherche dichotomique | 20 ns |
| O(n) | linéaire | recherche linéaire, somme d’un tableau | 1 ms |
| O(n log n) | quasi linéaire | tri fusion, tri par tas | 20 ms |
| O(n²) | quadratique | tri par insertion, comparer toutes les paires | 17 minutes |
| O(2ⁿ) | exponentielle | essayer tous les sous-ensembles | plus que l’âge de l’Univers |
Chaque ligne du tableau est un autre monde. Aucune machine plus rapide ne sauve un algorithme en O(n²) sur une entrée assez grande, et un meilleur algorithme gagne souvent plus que n’importe quelle mise à niveau matérielle.
Meilleur cas, pire cas, cas moyen
Un même algorithme peut faire des quantités de travail très différentes sur des entrées de même taille. Le tri par insertion prend chaque élément et le fait glisser vers la gauche jusqu’à sa place :
Initial array.
Insertion sort — Grows a sorted prefix; each new element sinks left until it meets a smaller one. Best O(n), average O(n²), worst O(n²).
Sur 16 éléments en ordre inverse, chaque nouvel élément doit remonter jusqu’au début : 120 comparaisons, soit n(n − 1)/2. Passez l’entrée en sorted : 15 comparaisons, une par élément. Sur une entrée random, on est entre les deux : 88 ici. Pour n = 256, l’écart devient 255 comparaisons pour une entrée triée, 15 874 pour une entrée aléatoire et 32 640 pour une entrée inversée.
« Le tri par insertion est en O(n²) » est donc une affirmation sur le pire cas (et ici aussi le cas moyen). Son meilleur cas est en O(n), ce qui le rend excellent sur des données déjà presque triées.
Les pires cas se cachent là où on ne les attend pas. Le tri rapide de ce visualiseur prend le dernier élément comme pivot. Sur une entrée aléatoire, il lui faut 2 325 comparaisons pour 256 éléments, mais sur une entrée déjà triée, chaque partition est aussi déséquilibrée que possible, et il lui en faut 32 640, aussi mal que le tri par insertion. Les vraies bibliothèques s’en protègent : elles choisissent leurs pivots plus soigneusement et changent d’algorithme quand une partition tourne mal. Le std::sort du C++, par exemple, est en général un introsort, un tri rapide qui se replie sur le tri par tas.
n log n contre n²
Le tri montre l’écart entre les deux classes les plus courantes. Sur 256 éléments aléatoires :
| Algorithme | Comparaisons | Croissance |
|---|---|---|
| tri par insertion | 15 874 | O(n²) |
| tri par sélection | 32 640 | O(n²), sur toute entrée |
| tri rapide | 2 325 | O(n log n) en moyenne |
| tri par tas | 3 323 | O(n log n) |
| tri fusion | 1 731 | O(n log n) |
Initial array.
Merge sort — Top-down: sort each half, then merge the two sorted runs through an auxiliary buffer. Best O(n log n), average O(n log n), worst O(n log n).
Le tri fusion coupe la liste en deux jusqu’à des éléments isolés, puis refusionne des moitiés triées. Il y a log₂ n niveaux de découpage, et chaque niveau fait environ n travail : le total est en O(n log n).
Aucun tri par comparaisons ne peut faire fondamentalement mieux. Il existe n! ordres possibles, et chaque comparaison n’a que deux issues : les distinguer demande au moins log₂(n!) ≈ n log₂ n comparaisons dans le pire cas. Pour 256 éléments, cela fait environ 1 684 — et les 1 731 du tri fusion en sont proches.
Là où la vraie machine tord les règles
Le grand O est un point de départ, pas toute l’histoire :
- Les constantes comptent pour les petits n. Un algorithme en O(n²) à petite constante bat un O(n log n) sur quelques dizaines d’éléments. C’est pourquoi les vrais tris — Timsort en Python et en Java, introsort en C++ — passent au tri par insertion sur les petits intervalles.
- L’ordre des accès mémoire compte. Deux algorithmes au même décompte peuvent différer énormément en temps parce que l’un parcourt la mémoire dans l’ordre et l’autre saute partout. Le chapitre sur les caches montre 75 % contre 0 % de succès pour un travail identique.
- Les branchements comptent. Une comparaison dont l’issue est aléatoire provoque une mauvaise prédiction environ une fois sur deux ; la même comparaison sur des données triées ne coûte presque rien.
- La mémoire est aussi un coût. Le tri fusion a besoin de O(n) mémoire supplémentaire pour fusionner. Le tri par tas et le tri par insertion trient sur place, avec O(1) de mémoire en plus.
À retenir
- On compare des algorithmes en comptant les étapes de base en fonction de la taille de l’entrée n, pas en les chronométrant.
- Le grand O garde le terme qui croît le plus vite : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
- Un même algorithme a un meilleur cas, un pire cas et un cas moyen : le tri par insertion est en O(n) sur une entrée triée et en O(n²) sur une entrée inversée.
- Le tri par comparaisons ne peut pas descendre sous environ n log₂ n comparaisons, et le tri fusion, le tri par tas et (en moyenne) le tri rapide atteignent cette borne.
- Les constantes, les caches et la prédiction de branchement départagent les algorithmes d’une même classe.