01 — La notation Big-O, lue sans maths

Ce que tu vas apprendre

• Ce que la lettre O et le n veulent dire concrètement
• Les six complexités que tu rencontres au quotidien
• Comment chacune se traduit en code
• À quel point l'écart entre elles devient énorme sur de gros volumes

Prérequis

• 00 — Introduction

La notation Big-O fait peur parce qu'elle ressemble à des maths. En réalité, c'est juste une façon courte de dire « voici comment le coût grandit quand les données grandissent ». Pas besoin de savoir calculer une limite. Il faut savoir lire six formes, et reconnaître laquelle décrit ton code.

O(...) se lit « de l'ordre de ». Le n à l'intérieur représente la taille de l'entrée : le nombre d'éléments dans une liste, le nombre de lignes d'un fichier, le nombre d'utilisateurs. Ce qu'il y a entre parenthèses décrit comment le travail augmente quand n augmente.

Voyons les six formes, de la plus rapide à la plus lente.

O(1) — temps constant

Le coût ne dépend pas de la taille. Que tu aies 10 éléments ou 10 millions, c'est le même travail.

typescriptfunction premier(items: number[]): number {
  return items[0]; // un seul accès, peu importe la taille
}

pythondef premier(items: list[int]) -> int:
    return items[0]  # un seul accès, peu importe la taille

Lire une case d'un tableau par son index, ajouter en fin de tableau, lire une valeur dans un dictionnaire : ce sont des opérations en temps constant. C'est le meilleur cas possible.

O(log n) — temps logarithmique

À chaque étape, tu élimines la moitié des données restantes. Doubler la taille de l'entrée n'ajoute qu'une seule étape. C'est ce que fait la recherche dichotomique dans un tableau trié.

typescriptfunction rechercheDichotomique(items: number[], cible: number): number {
  let bas = 0;
  let haut = items.length - 1;
  while (bas <= haut) {
    const milieu = Math.floor((bas + haut) / 2);
    if (items[milieu] === cible) return milieu;
    if (items[milieu] < cible) bas = milieu + 1;
    else haut = milieu - 1;
  }
  return -1;
}

Sur un million d'éléments, une recherche linéaire fait jusqu'à un million de comparaisons. La recherche dichotomique en fait au plus 20. C'est la magie du logarithme : log₂(1 000 000) ≈ 20. Le prix à payer, c'est que les données doivent être triées au préalable.

O(n) — temps linéaire

Le coût grandit proportionnellement à la taille. Deux fois plus de données, deux fois plus de travail. C'est le cas dès que tu parcours une fois chaque élément.

pythondef somme(items: list[int]) -> int:
    total = 0
    for x in items:   # une passe sur n éléments
        total += x
    return total

La plupart des traitements honnêtes sont en O(n) : filtrer une liste, calculer une somme, chercher un élément sans index. C'est souvent le mieux qu'on puisse faire, parce qu'il faut bien regarder chaque donnée au moins une fois.

O(n log n) — la complexité des bons tris

C'est la complexité des algorithmes de tri efficaces (le tri fusion, le tri rapide en moyenne). C'est aussi celle de Array.prototype.sort en JavaScript et de sorted() en Python.

typescriptconst tries = [...items].sort((a, b) => a - b); // O(n log n)

Intuitivement : tu fais n fois un travail qui coûte log n. C'est un peu plus cher que O(n), mais ça reste très raisonnable. Trier un million d'éléments demande environ 20 millions d'opérations, l'affaire de quelques dizaines de millisecondes.

O(n²) — temps quadratique

Le coût grandit au carré. Doubler les données quadruple le travail. C'est le signe d'une boucle imbriquée dans une autre boucle, chacune parcourant les données.

pythondef doublons(items: list[int]) -> list[int]:
    result = []
    for i in range(len(items)):       # n itérations
        for j in range(i + 1, len(items)):  # n itérations
            if items[i] == items[j]:
                result.append(items[i])
    return result

C'était mon bug de déduplication de l'article précédent. Sur 100 éléments, 10 000 opérations : invisible. Sur 100 000 éléments, 10 milliards d'opérations : plusieurs minutes. Le quadratique est le seuil où le code commence à mourir en production. Dès que tu vois deux boucles imbriquées sur les mêmes données, une alarme doit sonner.

O(2ⁿ) — temps exponentiel

Chaque élément supplémentaire double le travail. C'est la complexité des solutions naïves à certains problèmes combinatoires, comme le calcul récursif de Fibonacci sans mémoïsation.

typescriptfunction fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // deux appels par niveau
}

fib(40) déclenche plus d'un milliard d'appels. fib(60) ne terminera jamais de ton vivant. L'exponentiel est ingérable au-delà d'une quarantaine d'éléments. Quand un algorithme est en O(2ⁿ), la seule réponse est de changer d'approche, pas d'optimiser les détails.

L'écart entre les formes

Les noms restent abstraits tant qu'on ne met pas des chiffres derrière. Voici le nombre d'opérations pour chaque complexité, selon la taille de l'entrée.

La leçon : sur de petits volumes, tout se vaut. C'est pour ça que la dette de complexité est invisible au début. Mais la pente diverge violemment. Passer de O(n²) à O(n log n), ou de O(n) à O(log n), peut transformer une fonction inutilisable en une fonction instantanée. C'est exactement ce que permettent les structures de données, le sujet des articles à venir.

L'article suivant montre comment déterminer la complexité d'un code en comptant ses opérations, et pourquoi on jette les constantes au passage.

Sources

• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 3 "Growth of Functions". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.4 "Analysis of Algorithms". Addison-Wesley.
• Knuth, D. E. (1976). Big Omicron and Big Omega and Big Theta. ACM SIGACT News, 8(2), 18-24.