Formations — 1 037 leçons en français

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 :

  1. Les constantes disparaissent. 3n + 500 est O(n) ; n²/2 est O(n²).
  2. Le terme dominant l'emporte. n² + n est 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.

Lire l'explication détaillée et faire le quiz →

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.