Dernière mise à jour : 2026-06-23

Croissance en notation grand O

La notation grand O classe la façon dont les besoins en ressources d'un algorithme évoluent avec la taille de l'entrée. Plutôt que de mesurer des secondes sur une machine particulière, elle capture la forme de cette croissance : le travail double-t-il quand n double, ou quadruple-t-il ? Les six classes de complexité ci-dessous sont celles que l'on rencontre le plus souvent dans les manuels et les entretiens techniques.

Les six classes courantes

O(log n) — Logarithmique. Chaque étape élimine une fraction constante du travail restant. La recherche dichotomique dans un tableau trié d'un milliard d'éléments ne demande que 30 comparaisons, car elle divise l'espace de recherche par deux à chaque étape. Les recherches dans les arbres binaires équilibrés et de nombreuses récurrences de type « diviser pour régner » entrent dans cette classe.

O(n) — Linéaire. Le travail croît en proportion directe de la taille de l'entrée. Un parcours unique d'un tableau pour en trouver le maximum, le comptage de caractères dans une chaîne ou la lecture de chaque élément d'une liste sont tous linéaires. Les algorithmes linéaires sont généralement considérés comme efficaces.

O(n log n) — Linéarithmique. La classe la plus courante pour le tri. Le tri fusion, le tri par tas et Timsort (utilisé en Python et en Java) atteignent tous O(n log n), qui est aussi la borne inférieure théorique du tri par comparaison. Pour $n = 10^6$, cela représente environ vingt millions d'opérations — rapide en pratique.

O(n²) — Quadratique. Deux boucles imbriquées sur l'entrée. Le tri à bulles, le tri par insertion et la multiplication naïve de matrices ont tous un pire des cas en O(n²). Pour $n = 10^4$, cela représente cent millions d'opérations ; pour $n = 10^6$, mille milliards — impraticable pour des données volumineuses.

O(2ⁿ) — Exponentiel. Le travail double à chaque élément supplémentaire. L'algorithme de Fibonacci récursif naïf recalcule les sous-problèmes de façon exponentielle ; l'énumération par force brute de tous les sous-ensembles d'un ensemble croît également en $2^n$. Pour n = 40, le comptage dépasse mille milliards.

O(n!) — Factoriel. La classe à croissance la plus rapide dans l'analyse algorithmique courante. Les solutions par force brute aux problèmes de permutation — l'énumération de toutes les tournées possibles dans le problème du voyageur de commerce — effectuent une opération par permutation, et il existe $n!$ permutations au total. Pour n = 20, le comptage dépasse deux milliards de milliards d'opérations.

Exemple numérique pour n = 20

$\log_2 20 \approx 4{,}32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86{,}4$

$20^2 = 400 \quad\quad 2^{20} = 1\,048\,576 \quad\quad 20! \approx 2{,}43 \times 10^{18}$

Le rapport entre O(n log n) et O(n!) pour n = 20 est d'environ $10^{16}$ — la différence entre un tri rapide et une attente supérieure à l'âge de l'univers.

Repères pratiques

Les constantes et les effets de cache comptent pour les petites entrées ; la complexité domine pour les grandes. Un seuil de l'ordre de n = 10 000 est celui à partir duquel O(n²) commence à poser problème sur du matériel moderne (pour des opérations simples). Au-delà de n = 10^6, un algorithme O(n log n) ou mieux est généralement nécessaire. Les algorithmes exponentiels et factoriels requièrent des approximations, de la programmation dynamique ou des stratégies d'élagage pour tout problème réel.

Convertisseur de base numérique est utile pour travailler avec les représentations binaires de l'espace d'entrée.