05 — Les pièges qui transforment du code propre en O(n²)

Ce que tu vas apprendre

• Le piège du includes ou in dans une boucle
• Les boucles imbriquées cachées derrière des appels de méthode
• La concaténation de chaînes qui dégénère en O(n²)
• Le recalcul inutile dans une condition de boucle

Prérequis

• 04 — La complexité spatiale

Les pires bugs de complexité ne ressemblent pas à du mauvais code. Ils ressemblent à du code propre, lisible, qui passe la revue sans problème. Le coût quadratique est caché derrière un appel de méthode innocent ou une habitude anodine. Voici les pièges que je vois le plus souvent, et comment les repérer.

Piège 1 : `includes` ou `in` dans une boucle

C'est le piège numéro un, de très loin. Tu parcours une liste, et pour chaque élément tu vérifies sa présence dans une autre liste avec includes (JavaScript) ou in (Python sur une liste).

typescript// O(n²) caché : includes est O(n), exécuté n fois
function communs(a: number[], b: number[]): number[] {
  return a.filter((x) => b.includes(x));
}

Le filter parcourt a (n itérations), et à chaque tour b.includes(x) reparcourt tout b (n opérations). Total : O(n²). Sur deux listes de 50 000 éléments, c'est 2,5 milliards d'opérations.

La correction : transformer la liste cherchée en Set une seule fois, puis tester en O(1).

typescript// O(n) : le Set rend chaque test instantané
function communs(a: number[], b: number[]): number[] {
  const setB = new Set(b);        // O(n) une seule fois
  return a.filter((x) => setB.has(x)); // O(1) par test
}

Même piège en Python avec in sur une liste, et même correction avec un set :

python# Lent : x in b est O(n)
communs = [x for x in a if x in b]

# Rapide : x in set_b est O(1)
set_b = set(b)
communs = [x for x in a if x in set_b]

Dès que tu vois un test de présence à l'intérieur d'une boucle, demande-toi si la collection cherchée peut devenir un Set en amont.

Piège 2 : les boucles imbriquées déguisées

Une boucle imbriquée saute aux yeux quand elle est écrite avec deux for. Mais beaucoup de méthodes du langage cachent une boucle. Les enchaîner crée une imbrication invisible.

typescript// Ça ressemble à une seule passe, mais c'en est deux imbriquées
const result = liste.map((x) => {
  const trouve = autres.find((y) => y.id === x.id); // find est O(n)
  return { ...x, label: trouve?.label };
});

Le map est O(n), et le find à l'intérieur est O(n) aussi. C'est un O(n²) déguisé en deux lignes propres. La solution est encore d'indexer : on construit une fois une Map des autres par id, puis chaque recherche devient O(1).

typescriptconst index = new Map(autres.map((y) => [y.id, y])); // O(n)
const result = liste.map((x) => ({
  ...x,
  label: index.get(x.id)?.label, // O(1)
}));

Les méthodes à surveiller, parce qu'elles cachent un O(n) : find, findIndex, includes, indexOf, filter, some, every. Aucune n'est gratuite. Une seule dans une boucle est sans danger, mais imbriquée dans une autre passe, elle fait basculer en quadratique.

Piège 3 : la concaténation de chaînes dans une boucle

Construire une grande chaîne en l'accumulant += dans une boucle est un piège classique, parce que dans beaucoup de langages les chaînes sont immuables : chaque += recopie toute la chaîne existante.

python# O(n²) : chaque += recopie toute la chaîne accumulée
result = ""
for ligne in lignes:
    result += ligne + "\n"

À la k-ième itération, la chaîne fait déjà k caractères, et on la recopie entièrement. La somme des recopies donne O(n²). La correction : accumuler dans une liste, puis joindre en une fois.

python# O(n) : on accumule les morceaux, une seule fusion à la fin
morceaux = []
for ligne in lignes:
    morceaux.append(ligne)
result = "\n".join(morceaux)

En JavaScript, le moteur optimise souvent la concaténation, mais l'approche par tableau + join reste plus sûre et plus claire :

typescriptconst morceaux: string[] = [];
for (const ligne of lignes) morceaux.push(ligne);
const result = morceaux.join("\n");

Piège 4 : recalculer dans la condition de boucle

Un grand classique en JavaScript : appeler une fonction coûteuse dans la condition d'une boucle, qui la réexécute à chaque tour.

typescript// items.filter(...) est recalculé à CHAQUE itération
for (let i = 0; i < items.filter((x) => x.actif).length; i++) {
  // ...
}

Le items.filter(...).length est recalculé à chaque test de la condition, soit n fois, et chaque filtrage est O(n). On retombe en O(n²) pour une boucle qui devrait être O(n). La correction est triviale : calculer une fois, avant la boucle.

typescriptconst actifs = items.filter((x) => x.actif); // une seule fois
for (let i = 0; i < actifs.length; i++) {
  // ...
}

Le même réflexe vaut pour tout calcul invariant glissé dans une condition ou un corps de boucle : sors de la boucle ce qui ne dépend pas de l'itération.

Le réflexe de revue

Tous ces pièges ont un point commun : une opération en O(n) glissée à l'intérieur d'une autre passe en O(n). Quand tu relis du code, le tien ou celui d'un collègue, pose-toi systématiquement la question : « cette ligne, à l'intérieur de la boucle, combien coûte-t-elle ? ». Si la réponse est « ça reparcourt une collection », tu tiens probablement un quadratique.

Le correctif est presque toujours le même : indexer en amont avec un Set ou une Map pour rendre les recherches instantanées, ou sortir de la boucle ce qui ne change pas. C'est l'application directe de l'article 03 : connaître le coût des structures permet de choisir celle qui rend l'opération chaude gratuite.

L'article suivant clôt la série en assemblant tout : comment choisir, face à un problème concret, la structure de données qui te donnera la meilleure complexité.

Sources

• McConnell, S. (2004). Code Complete (2nd ed.), Chapitre 25 "Code-Tuning Strategies" et Chapitre 26 "Code-Tuning Techniques". Microsoft Press.
• Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 8 "Algorithm Design Techniques". Addison-Wesley.
• Goldberg, D. (1991). What Every Computer Scientist Should Know About Floating-Point Arithmetic — pour le coût caché des opérations apparemment simples. ACM Computing Surveys, 23(1).