Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 20 septembre 2026 · Notre méthode
- La complexité compte les opérations selon la taille n, pas les secondes sur une machine
- On garde l'ordre de grandeur : le terme dominant, sans ses constantes
- Deux boucles imbriquées sur les mêmes données donnent du n au carré
Le chronomètre est un mauvais juge
Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change. La COMPLEXITÉ répond autrement : elle compte le NOMBRE D'OPÉRATIONS effectuées en fonction de la taille des données, notée n. C'est une propriété de l'algorithme, pas de l'ordinateur qui l'exécute.
On ne cherche pas un nombre exact. On cherche l'ORDRE DE GRANDEUR : ce qui arrive au temps de calcul quand n double. C'est la seule information qui survit au changement de machine, et c'est celle qui décide si un programme tiendra sur des données réelles.
Les cinq familles qu'on rencontre
| La famille | La notation | Quand n double | Exemple typique |
|---|---|---|---|
| Constante | O(1) | Rien ne change | Lire le premier élément d'une liste |
| Logarithmique | O(log n) | Une opération de plus | La recherche dichotomique |
| Linéaire | O(n) | Le temps double | Le parcours complet d'une liste |
| Quadratique | O(n²) | Le temps quadruple | Le tri par sélection, deux boucles imbriquées |
| Exponentielle | O(2 puissance n) | Le temps est mis au carré | L'essai de toutes les combinaisons |
Compter, sur un cas concret
La méthode est mécanique : on repère les boucles, on regarde combien de tours chacune fait, et l'on multiplie les boucles imbriquées.Algorithme du tri par sélection. La boucle extérieure fait n moins 1 passes. À la passe numéro i, la boucle intérieure compare les n moins i éléments restants. Le total vaut n moins 1, plus n moins 2, plus… plus 1 : c'est la somme des premiers entiers, soit n fois n moins 1, divisé par deux. Développons : la moitié de n au carré, moins la moitié de n. Quand n vaut 1 000, le premier terme vaut 500 000 et le second 500 : le second est mille fois plus petit, et il le sera de plus en plus. On le laisse tomber, ainsi que le facteur un demi, et l'on écrit O(n²). Ce n'est pas de la négligence : on affirme exactement ce qui compte, à savoir que doubler n multiplie le travail par quatre.

Ce que cela permet de décider avant d'écrire
Un algorithme exponentiel sur trente données demande déjà un milliard d'opérations : il est inutilisable, et aucune machine plus rapide ne le sauvera, car ajouter une seule donnée double le travail. Savoir cela AVANT d'écrire évite de passer une semaine à optimiser ce qui ne peut pas l'être — et oriente vers un autre algorithme, ou vers une réponse approchée assumée.






- La complexité compte les opérations selon la taille n, pas les secondes sur une machine
- On garde l'ordre de grandeur : le terme dominant, sans ses constantes
- Deux boucles imbriquées sur les mêmes données donnent du n au carré
- Une complexité exponentielle est condamnée dès quelques dizaines de données
Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ?
n est multiplié par dix, donc n au carré par cent. Le temps suit le carré, pas la taille.
Que signifie O(log n) quand la taille des données double ?
Doubler n ajoute un seul niveau de division par deux : c'est ce qui rend la dichotomie si économique.




