02 — Compter les opérations et ignorer le bruit

Ce que tu vas apprendre

• Comment déterminer la complexité d'une fonction en lisant son code
• Pourquoi on ignore les constantes et les coefficients
• La règle du terme dominant
• La différence entre cas pire, cas moyen et cas meilleur

Prérequis

• 01 — La notation Big-O

Savoir lire les formes Big-O ne sert à rien si tu ne sais pas les attribuer à ton propre code. La bonne nouvelle : la méthode est mécanique. Tu comptes les opérations en fonction de n, puis tu simplifies avec deux règles. Une fois l'habitude prise, tu le fais de tête en survolant une fonction.

Compter les opérations

L'idée de base : une instruction simple coûte 1. Une boucle qui s'exécute n fois coûte n. Une boucle dans une boucle coûte n × n. On additionne ce qui est en séquence, on multiplie ce qui est imbriqué.

typescriptfunction exemple(items: number[]): number {
  let total = 0;              // 1 opération
  for (const x of items) {    // n itérations
    total += x;               // 1 opération × n
  }
  return total;               // 1 opération
}

Le compte exact : 1 + n + 1 = n + 2 opérations. La complexité, on va le voir, est O(n).

Deuxième exemple, avec une imbrication :

pythondef paires(items: list[int]) -> None:
    for a in items:        # n itérations
        for b in items:    # n itérations, pour chaque a
            print(a, b)    # exécuté n × n fois

Ici on a n × n = n² exécutions du print. La complexité est O(n²).

Règle 1 : on ignore les constantes

Une fonction qui fait n + 2 opérations et une autre qui en fait n + 1000 ont la même complexité : O(n). La constante additive ne change pas la pente. Quand n devient grand, le + 2 ou le + 1000 est négligeable devant n.

Même chose pour les coefficients multiplicateurs. Ces trois boucles sont toutes en O(n) :

typescriptfor (const x of items) f(x);                    // n
for (const x of items) { f(x); g(x); h(x); }     // 3n
for (let i = 0; i < items.length; i += 2) f(i);  // n/2

n, 3n, n/2 : pour Big-O, c'est pareil, O(n). Pourquoi cette désinvolture ? Parce que Big-O décrit la forme de croissance, pas le temps précis. Un code en 3n peut très bien être plus rapide en pratique qu'un code en 100n, mais les deux doublent quand n double. C'est cette propriété qu'on capture, et c'est elle qui décide du passage à l'échelle.

Attention, cela ne veut pas dire que les constantes sont sans importance dans la vraie vie. Diviser un temps de calcul par deux compte, quand on optimise. Mais pour répondre à la question « ce code tiendra-t-il quand les volumes seront multipliés par mille ? », seule la forme compte.

Règle 2 : on garde le terme dominant

Quand une fonction combine plusieurs complexités, seule la plus grande survit. Considère ce code :

pythondef traitement(items: list[int]) -> None:
    for x in items:            # O(n)
        print(x)
    for a in items:            # O(n²)
        for b in items:
            print(a, b)

Le compte total est n + n². Mais quand n grandit, le n² écrase le n. Pour n = 1000, on a 1000 + 1 000 000 : le premier terme est du bruit. On garde donc O(n²).

La hiérarchie des termes, du plus dominant au plus faible :

O(2ⁿ) > O(n²) > O(n log n) > O(n) > O(log n) > O(1)

Dans une somme de complexités, le terme le plus à gauche dans cette liste gagne. C'est pour ça que O(n² + n + 1) se réduit à O(n²), et que O(n log n + n) se réduit à O(n log n).

Cas pire, cas moyen, cas meilleur

Une même fonction n'a pas toujours le même coût selon les données qu'on lui donne. Reprenons une recherche linéaire :

typescriptfunction indexOf(items: number[], cible: number): number {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === cible) return i; // sortie anticipée
  }
  return -1;
}

• Meilleur cas : la cible est le premier élément. Une seule comparaison. O(1).
• Pire cas : la cible est absente, ou en dernière position. On parcourt tout. O(n).
• Cas moyen : en moyenne, la cible se trouve au milieu. Environ n/2 comparaisons, donc O(n).

Par convention, quand on parle de la complexité d'un algorithme sans préciser, on parle du pire cas. C'est la garantie : « ce code ne fera jamais pire que ça ». C'est ce dont tu as besoin pour dimensionner un système, parce que c'est le pire cas qui te réveille la nuit, pas le meilleur.

Le cas moyen est utile dans certaines situations. Le tri rapide, par exemple, est en O(n log n) en moyenne mais en O(n²) dans son pire cas. En pratique on l'utilise quand même, parce que son pire cas est rare et que sa moyenne est excellente. La recherche dans une hashmap, qu'on verra à l'article suivant, est en O(1) en moyenne mais O(n) dans un pire cas pathologique. Connaître les deux évite les mauvaises surprises.

La méthode complète en pratique

Face à une fonction, voici la marche à suivre :

1. Repère les boucles et leur nombre d'itérations en fonction de n.
2. Multiplie les boucles imbriquées, additionne les blocs en séquence.
3. Jette les constantes et les coefficients.
4. Garde uniquement le terme dominant.
5. Si le coût varie selon les données, raisonne sur le pire cas.

Applique ça à du vrai code régulièrement et l'estimation devient un réflexe. Tu repéreras une boucle imbriquée sur les mêmes données et tu sauras immédiatement que tu as un O(n²) sous les yeux, sans même réfléchir.

Maintenant qu'on sait analyser du code, l'article suivant attaque le cœur du sujet : le coût des structures de données. Pourquoi un tableau est imbattable pour lire par index mais catastrophique pour chercher une valeur, et pourquoi une hashmap inverse ce rapport de force.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 2 "Getting Started" et Chapitre 3 "Growth of Functions". MIT Press.
• McConnell, S. (2004). Code Complete (2nd ed.), Chapitre 25 "Code-Tuning Strategies". Microsoft Press.
• Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Section 2.1 "The RAM Model of Computation". Springer.