Explorateur de complexité Big-O

Observe comment les classes de complexité des algorithmes croissent lorsque la taille d'entrée N augmente.

Exemple résolu — Explorateur de complexité Big-O

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10 000

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Explorateur de complexité Big-O

Le grand O est une borne supérieure de croissance, et non une mesure du temps. Dire qu’un algorithme est O(N²) signifie qu’au-delà d’une certaine taille d’entrée, son travail reste inférieur à un multiple fixe de N² — cela ne dit rien sur les secondes, et absolument rien sur les petites entrées.

Ce que signifie chaque symbole

N: la taille de l’entrée — le nombre d’éléments fournis à l’algorithme. C’est le nombre réglé ci-dessus, allant de 2 à 1 000 000.
f(N): le travail réellement effectué pour cette taille, compté en opérations abstraites plutôt qu’en secondes.
c: un facteur multiplicatif constant que la notation a le droit de masquer. L’affirmation est f(N) ≤ c·g(N) ; c peut valoir 2 ou 2 000, et c’est précisément cette information que le grand O ignore.
n₀: la taille au-delà de laquelle la borne doit s’appliquer. En dessous de n₀, les classes peuvent se ranger dans n’importe quel ordre, c’est pourquoi les cinq nombres ci-dessus se regroupent pour les petites valeurs de N.

D’où vient la formule

Partons de l’affirmation à rendre précise : le travail f(N) finit par ne pas croître plus vite qu’une fonction de référence g(N).
“Ne pas croître plus vite” doit tolérer un facteur constant, car l’optimisation d’une boucle interne modifie la constante, pas la forme de la courbe. On autorise donc un multiplicateur : f(N) ≤ c·g(N).
Et “à terme” doit tolérer les petites entrées, où tout peut arriver. On n’impose l’inégalité qu’une fois N ≥ n₀. En résumé : f(N) = O(g(N)) signifie qu’il existe un c > 0 et un n₀ tels que f(N) ≤ c·g(N) pour tout N ≥ n₀.

Comment lire ce que vous voyez

Les cinq lignes représentent une même taille d’entrée évaluée dans cinq classes de croissance avec toutes les constantes fixées à 1 — ce sont donc des comptes d’opérations, pas des temps d’exécution. Avec la valeur par défaut N = 100, elles indiquent 1, 7, 100, 664 et 10,000. Le logarithme est en base 2 : log₂ 100 ≈ 6.64, c’est pourquoi O(log N) affiche 7 et O(N log N) affiche 664 au lieu de 700.

Suppose: Que chaque opération a le même coût que n’importe quelle autre, et que le décompte est exact plutôt que mesuré. C’est ce qui rend la comparaison nette, et tout autant ce qui la rend abstraite — les profils d’accès à la mémoire, le comportement du cache et le disque sont tous exclus de ce modèle, et sur un matériel réel, ce sont eux qui déterminent couramment quel algorithme l’emporte.
Ne tient plus quand: La borne ne garantit rien en dessous de n₀, et vous pouvez l’observer directement : réglez N = 2 et les cinq classes indiquent 1, 1, 2, 2 et 4 — quasiment indistinctement. L’ordre garanti par la notation n’émerge que lorsque N devient grand, ce qui explique pourquoi une méthode en O(N²) avec une petite constante peut surpasser une méthode en O(N log N) pour n’importe quelle entrée que vous manipulerez en pratique.

Quand la croissance dépasse toute optimisation 🖖

Le Big-O décrit comment le travail croît lorsque la taille d'entrée augmente. Une simple boucle croît à peu près avec N, les boucles imbriquées croissent souvent avec N², et la récursion ramifiée peut croître exponentiellement. La leçon importante est l'échelle : pour un petit N, de nombreuses approches se ressemblent, mais pour un N plus grand, la classe de croissance domine le temps d'exécution.

Le test du doublement 🖖

La façon la plus claire de ressentir une classe de croissance est de doubler l'entrée et d'observer ce qui arrive au travail. En O(log N), il bouge à peine — la recherche dichotomique trouve un élément parmi un million en environ 20 comparaisons. En O(N), le travail double, et en O(N²) il quadruple. Faites glisser N dans cet outil et voyez les écarts passer d'invisibles à écrasants.

Quand la classe la plus rapide perd 🖖

Une classe de croissance plus basse ne garantit pas un programme plus rapide. Les informaticiens appellent ces exceptions des algorithmes galactiques : des méthodes à meilleure notation Big-O dont le facteur constant caché est si énorme qu'elles ne dépassent les méthodes simples que sur des entrées plus grandes que tout ce que contient l'univers physique. Plusieurs algorithmes record de multiplication matricielle ne sont jamais utilisés pour cette raison précise — Big-O écarte discrètement les constantes qui décident de la vitesse réelle.

Problème entièrement résolu

Où le gouffre se creuse entre N log N et N ² 5 étapes
À N = 100, le panneau affiche 664 pour N log N et 10 000 pour N². Cela ne représente qu'un facteur de quinze — loin du gouffre que les classes de complexité sont censées représenter. Déterminez où ce gouffre s'ouvre réellement.
1. Commencez par les deux nombres. log₂ 100 vaut 6,6439, donc N log₂ N vaut 664 et N² vaut 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. Le ratio entre eux n'est pas une constante, et c'est tout l'intérêt des classes de complexité. Divisez et le N s'annule une fois, laissant N/log N — une quantité qui croît sans borne, simplement lentement.
3. À N = 100, il est de 15,1. C'est réel mais peu impressionnant : un gain d'un facteur quinze est le genre de chose qu'un meilleur facteur constant pourrait vous apporter, ce qui explique exactement pourquoi les tests de performance sur de petites entrées induisent en erreur.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Injectez maintenant un million. Le logarithme a à peine bougé — de 6,6 à 19,9, un facteur de trois — tandis que N a été multiplié par dix mille. Le ratio est désormais de 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. Et il ne s'inverse jamais. La dérivée de N/log N est positive pour tout N supérieur à e, il n'existe donc aucune taille d'entrée au-delà de laquelle l'algorithme quadratique rattrape son retard.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Réponse

L'outil affiche 664 contre 10 000 pour N = 100. Le nombre qui mérite d'être retenu est l'autre : à un million, ces deux mêmes courbes sont séparées de 50 172. Les classes de complexité ne traitent pas de paquets de cent éléments, et les comparer à cette échelle est le moyen classique de se convaincre d'opter pour le mauvais algorithme — un écart d'un facteur quinze ressemble à ce qu'un langage plus rapide pourrait combler. Déplacez le curseur vers le haut et observez le ratio augmenter. C'est également la raison pour laquelle le logarithme est si souvent négligé en pratique : il n'a augmenté que d'un facteur trois alors que l'entrée a été multipliée par dix mille.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Parcours

Compter le travail, pas les secondes

Mène à sorting-race

Références (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

Par l’équipe 42Math · Mis à jour 2026-06-10

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

N petit = 20 - Toutes les courbes à N=20
N=1000 - N=1000 : les courbes polynomiales divergent
Échelle log - L'échelle logarithmique révèle les différences de croissance
Constantes cachées - Avec c=50, 50N log N et N² se croisent près de N=439