Big O pour les pressés : pourquoi votre boucle rame (et quand c'est grave)

La page se charge en 80 ms en local. En prod, sur la vraie base, elle met 9 secondes et fige l'onglet. Le code n'a pas changé. Les données, si : 60 lignes de test en local, 14 000 en production.

Le coupable était une boucle de dix lignes, parfaitement lisible, qui cherchait les doublons d'une liste. Elle n'avait aucun bug. Elle avait juste la mauvaise forme. Et comprendre cette forme, c'est tout ce que Big O raconte. Pas de maths, promis : juste de quoi lire son propre code et savoir lequel va exploser quand les données grossiront.

Big O ne mesure pas une vitesse, mais une forme

Première intuition à casser : O(...) ne te dit pas « ça prend 3 millisecondes ». Ça te dit comment le temps réagit quand tu doubles les données. C'est une forme de courbe, pas un chrono. Trois familles couvrent l'écrasante majorité du métier :

• O(1) : constant. La taille des données ne change rien. Lire tableau[5000] est aussi rapide que tableau[5].
• O(n) : linéaire. Deux fois plus de données, deux fois plus de temps. Une boucle qui parcourt tout.
• O(n²) : quadratique. Deux fois plus de données, quatre fois plus de temps. C'est la classe qui tue, et c'est celle de ma boucle.

Voilà pourquoi mon bug était invisible en local : à n = 60, O(n) fait 60 opérations et O(n²) en fait 3 600. La différence se mesure en microsecondes, personne ne la voit. À n = 14 000, O(n) fait 14 000 opérations, O(n²) en fait 196 millions. Là, ça se sent.

La boucle qui décroche

Le code incriminé, réduit à l'os : pour chaque élément, je reparcours toute la liste pour voir s'il existe en double.

// ✗ O(n²) : une boucle DANS une boucle
const doublons = [];
for (const a of liste) {
    for (const b of liste) {        // ← le re-parcours qui coûte
        if (a.id === b.id && a !== b) doublons.push(a);
    }
}

Le même piège se cache sous une forme plus discrète, et c'est celle qui m'a eu pendant des années : includes() dans une boucle. Ça a l'air d'une seule boucle, mais includes en cache une deuxième.

// ✗ O(n²) déguisé : chaque includes() reparcourt tout le tableau
const vus = [];
for (const item of liste) {
    if (vus.includes(item.id)) continue;   // includes = O(n), dans une boucle = O(n²)
    vus.push(item.id);
}

La correction tient en un mot : Set. Un Set (ou un objet, ou une Map) est une table de hachage : vérifier l'appartenance avec .has() est O(1), peu importe la taille. La double boucle s'effondre en une seule.

// ✓ O(n) : le Set répond en O(1), une seule passe suffit
const vus = new Set();
const doublons = [];
for (const item of liste) {
    if (vus.has(item.id)) doublons.push(item);   // O(1)
    vus.add(item.id);
}

Mes 9 secondes sont retombées à 40 millisecondes. Aucune optimisation maligne, aucun cache : juste la bonne forme de courbe.

Pourquoi le Set est magique : tableau contre liste chaînée

Pour comprendre d'où sort ce O(1), il faut ouvrir le capot des structures de données. Tout repose sur une question : où vivent les éléments en mémoire ? La mémoire, c'est une longue rangée de cases numérotées.

Un tableau range ses éléments dans des cases collées les unes aux autres. Comme il connaît l'adresse de départ, il calcule instantanément où est le 5000ᵉ : lecture en O(1). Le revers : insérer au début force à décaler tout le reste d'un cran, donc O(n). C'est exactement ce que fait unshift() en JavaScript, là où push() (ajouter à la fin) est gratuit.

Une liste chaînée fait l'inverse : ses éléments sont éparpillés n'importe où, et chacun garde l'adresse du suivant, comme une chasse au trésor. Insérer ne décale rien (O(1)), mais lire le 5000ᵉ force à suivre les flèches une par une depuis le début (O(n)). Tu n'en écriras quasiment jamais à la main : en PHP c'est SplDoublyLinkedList, en Python collections.deque, en Go container/list, et en JavaScript… il faut la coder soi-même.

Une table de hachage (le Set, la Map, le dict Python, l'array PHP) joue dans une autre cour : une fonction transforme la clé directement en position mémoire. Pas de parcours, pas de décalage : lire, écrire, tester l'appartenance, le tout en O(1). C'est pour ça que remplacer un array.includes() par un Set.has() change une courbe quadratique en courbe linéaire.

Les O(n) cachés derrière une ligne anodine

La vraie compétence n'est pas de réciter ces classes, c'est de les repérer dans son propre code, souvent planquées derrière une syntaxe innocente :

• array.unshift(x) et array.splice(i, 0, x) au milieu : O(n), tout se décale.
• array.includes(x) ou array.indexOf(x) dans une boucle : O(n²). Un Set ou une Map ramène à O(n).
• Une requête SQL WHERE email = ? sans index sur la colonne : la base fait un full scan, du O(n) sur des millions de lignes. L'index, c'est sa version de la recherche binaire, du O(log n).
• Un .find() dans un .map() pour « recoller » deux listes : encore une boucle dans une boucle. On indexe une des deux listes dans une Map d'abord.

Conclusion

Personne ne te demandera de réécrire une table de hachage, ton langage la fournit. Big O ne sert pas à ça. Il sert à lire une boucle et à voir son futur : celle-ci tiendra à un million d'éléments, celle-là figera la page. C'est une compétence de lecture, pas d'écriture.

Et l'ironie, c'est que l'IA n'y change rien, au contraire. Un assistant produit volontiers une boucle O(n²) qui passe tous les tests sur 50 lignes et meurt en prod. Reconnaître la forme de la courbe dans du code généré, ça, ça ne se délègue pas. Si le sujet te plaît, j'en ai fait toute une fiche de lecture sur Grokking Algorithms, le livre qui m'a enfin réconcilié avec les algos sans une seule preuve formelle.