Accueil › Coding & algorithmique › La notation Big-O, sans mathématiques
La notation Big-O, sans mathématiques
Raisonner sur la complexitédebutant
La complexité répond à une seule question : quand l'entrée grossit, le travail grossit comment ?
// O(1) — indépendant de la taille
t[0]; map.get(cle); liste.size();
// O(n) — un parcours
for (int x : t) { somme += x; }
// O(n²) — deux boucles imbriquées sur la même collection
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) { … }
// O(log n) — on divise par deux à chaque étape
Arrays.binarySearch(t, cible);
// O(n log n) — le coût d'un tri par comparaison
Arrays.sort(t);
Les ordres de grandeur, sur un million d'éléments :
| Complexité | Étapes (ordre de grandeur) | Verdict |
|---|---|---|
| O(1) | 1 | instantané |
| O(log n) | 20 | instantané |
| O(n) | 1 000 000 | rapide |
| O(n log n) | 20 000 000 | acceptable |
| O(n²) | 1 000 000 000 000 | inutilisable |
Deux règles suffisent pour calculer :
- Les constantes disparaissent.
3n + 500est O(n) ;n²/2est O(n²). - Le terme dominant l'emporte.
n² + nest O(n²).
Et une troisième, moins connue mais très utile en entretien : on mesure aussi la complexité en espace — la mémoire supplémentaire utilisée. Beaucoup d'exercices se résolvent plus vite en échangeant de l'espace contre du temps.
Les termes à connaître
- Complexité en temps
Comment le nombre d'opérations croît quand la taille de l'entrée augmente. On ne compte pas les secondes, on compte les ordres de grandeur.
- O(n)
Linéaire : doubler l'entrée double le travail. Un parcours de tableau, une recherche dans une liste.
- O(log n)
Logarithmique : doubler l'entrée ajoute une étape. Recherche binaire, descente dans un arbre équilibré. Sur un million d'éléments, une vingtaine d'étapes suffisent.
- O(n²)
Quadratique : doubler l'entrée quadruple le travail. Deux boucles imbriquées sur la même collection. Acceptable sur 100 éléments, inutilisable sur 100 000.
- Complexité en espace
La mémoire supplémentaire utilisée, hors entrée. Une solution « en place » est en O(1) ; créer une Map de tous les éléments est en O(n).
- Pire cas, cas moyen
Big-O décrit par convention le pire cas. Une HashMap est en O(1) en moyenne mais en O(n) dans le pire cas — une nuance qu'on attend d'un candidat senior.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.