00 — Du parcours naïf aux patterns efficaces

Ce que tu vas apprendre

• Pourquoi le parcours naïf cache souvent un O(n²)
• Les quatre patterns que cette série couvre
• Pourquoi ces patterns reviennent en prod et en entretien
• Le plan de la série

Prérequis

• La notation Big-O
• Le coût des structures de données

Face à un problème sur un tableau (« trouve la paire qui somme à 10 », « la plus longue sous-chaîne sans répétition », « la somme entre les index i et j »), le premier réflexe est presque toujours le bon en termes de correction, et presque toujours le mauvais en termes de performance. On écrit deux boucles imbriquées, on teste toutes les combinaisons, et ça marche. Sur 100 éléments. En production, sur des données réelles, ce O(n²) se réveille, comme on l'a vu dans la série Complexité.

Cette série présente les quatre patterns qui transforment ces O(n²) en O(n) ou O(log n). Ce ne sont pas des astuces obscures : ce sont les techniques de base de la manipulation de tableaux, qu'un développeur senior reconnaît instantanément face à un problème. Elles sont omniprésentes dans le vrai code (parser, traiter des flux, agréger des données) et dans les entretiens techniques, où elles sont attendues.

Le réflexe naïf, et son coût

Prenons un problème simple : deux éléments du tableau somment-ils à une cible ?

typescript// O(n²) : on teste toutes les paires
function paireSommeNaif(arr: number[], cible: number): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === cible) return true;
    }
  }
  return false;
}

Ça marche, mais c'est quadratique. Avec un Set (rappel de la série Complexité), on descend à O(n) : pour chaque élément, on cherche son complément en O(1).

typescript// O(n) : pour chaque x, le complément cible - x existe-t-il déjà ?
function paireSomme(arr: number[], cible: number): boolean {
  const vus = new Set<number>();
  for (const x of arr) {
    if (vus.has(cible - x)) return true;
    vus.add(x);
  }
  return false;
}

Et si le tableau est trié, le pattern des deux pointeurs (article 03) résout le même problème en O(n) sans mémoire supplémentaire. Un même problème, trois complexités, selon ce qu'on sait des données et le pattern qu'on applique.

Les quatre patterns de la série

Chaque pattern correspond à une situation reconnaissable.

• Recherche dichotomique : les données sont triées, et on cherche un élément ou une frontière. On élimine la moitié à chaque étape. O(log n).
• Deux pointeurs : on parcourt un tableau (souvent trié) avec deux indices qui se rapprochent ou avancent ensemble. O(n).
• Fenêtre glissante : on cherche le meilleur sous-tableau ou sous-chaîne contigu, en faisant glisser une fenêtre au lieu de la recalculer. O(n).
• Sommes préfixes : on précalcule des cumuls une fois, pour répondre ensuite à des requêtes de plage en O(1).

Le point commun de ces quatre patterns : ils remplacent un recalcul par une information qu'on maintient ou qu'on a préparée. C'est exactement l'esprit du compromis temps/espace et de l'indexation vus dans la série Complexité.

Le plan de la série

À la fin, face à un problème de tableau, tu sauras repérer l'indice qui révèle le bon pattern (« le tableau est trié » → dichotomie ou deux pointeurs ; « sous-tableau contigu » → fenêtre glissante ; « beaucoup de requêtes de somme » → sommes préfixes) au lieu de partir sur deux boucles imbriquées par défaut.

L'article suivant commence par le pattern le plus fondamental, celui qui transforme O(n) en O(log n) : la recherche dichotomique.

Sources

• Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 2 et Colonne 4 "Writing Correct Programs". Addison-Wesley.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Laakmann McDowell, G. (2015). Cracking the Coding Interview (6th ed.), Chapitre "Arrays and Strings". CareerCup.