Un script tourne en local sur un extrait de données. Il répond en un clin d'oeil, les tests passent, la revue de code ne relève rien. Le même script part en production, branché cette fois sur la base complète, et la requête met quinze secondes à revenir.
Entre les deux exécutions, le code est identique au caractère près. Ce qui a changé, c'est le nombre de lignes en entrée.
La notation Big O sert exactement à prévoir ce moment. Elle est enseignée comme un chapitre de mathématiques discrètes, avec des limites et des théorèmes, ce qui la rend inutilisable pour la plupart des gens qui écrivent du code tous les jours. Elle se ramène pourtant à une seule question, qui se pose en français et qui se vérifie avec un chronomètre.
Cet article prend la question par ce bout. Les chiffres qui suivent viennent de mesures exécutées pendant la rédaction, sur un conteneur Linux à un seul coeur (Intel Xeon 2,10 GHz, 3,9 Go de RAM), en Python 3.12.3 et Node.js 22.22.2. Les valeurs absolues dépendent de la machine, les rapports entre elles beaucoup moins.
Le moment exact où ça casse
Voici une fonction de dédoublonnage, écrite comme elle sort naturellement quand on apprend à programmer. Elle parcourt une liste d'adresses e-mail et ne garde que celles qu'elle n'a pas encore vues.
# Python 3.12
def dedoublonner(lignes: list[str]) -> list[str]:
resultat = []
for ligne in lignes:
if ligne not in resultat:
resultat.append(ligne)
return resultatElle est correcte. Elle rend le bon résultat sur n'importe quelle entrée. Et sur un fichier de test de 200 lignes, elle s'exécute en 0,07 milliseconde, ce qui ne déclenche aucun signal d'alarme nulle part.
Voici ce que donne la même fonction quand le fichier grossit.
400 fois plus de données, et plus de 200 000 fois plus de temps. La courbe ne monte pas, elle décolle. Un utilisateur qui déclenche cet import depuis une interface web voit sa requête partir en timeout, et l'équipe cherche du côté du serveur, du réseau ou de la base pendant que le coupable tient en six lignes.
Le fossé entre l'environnement de développement et la production ne se limite pas au volume de données, il touche aussi la configuration et les dépendances système. Ce sujet plus large est traité dans l'article sur la phrase "ça marche sur ma machine" et les projets portables.
Ce que Big O compte, et ce qu'il ne compte pas
Big O ne mesure pas des millisecondes. Il décrit la façon dont le nombre d'opérations évolue quand la taille de l'entrée augmente. Le n qui apparaît dans les formules, c'est cette taille : le nombre de lignes, d'utilisateurs, de fichiers, de produits.
La question à se poser devant une fonction tient en une phrase : si je double l'entrée, qu'est-ce qui arrive au temps d'exécution ?
- Il ne bouge pas. C'est du O(1). Accéder à
tableau[42], lire une clé de dictionnaire. - Il double aussi. C'est du O(n). Une boucle simple qui parcourt la liste une fois.
- Il double, plus un petit supplément. C'est du O(n log n), le régime des fonctions de tri intégrées au langage.
- Il quadruple. C'est du O(n²). Une boucle imbriquée, ou une recherche linéaire placée à l'intérieur d'une boucle.
Le O(log n) mérite une mention à part, sans lui consacrer un chapitre : c'est le régime d'une recherche dans un index de base de données, où multiplier le volume par mille n'ajoute qu'une poignée d'étapes. C'est la raison pour laquelle un index change tout sur une grosse table.
Le tableau de mesures plus haut illustre le quadruplement de façon imparfaite, et c'est intéressant de le dire. En passant de 5 000 à 40 000 lignes, soit huit fois plus de données, le temps est passé de 54 ms à 4,1 s, soit 76 fois plus. Le modèle quadratique prédisait 64 fois. L'écart vient du bruit de mesure, des effets de cache processeur et du fait qu'une machine partagée ne donne jamais deux fois le même chiffre. Big O donne un ordre de grandeur, pas une prédiction à la milliseconde.
Les trois formes de boucle imbriquée qu'on ne voit pas
La boucle dans la boucle avec deux indentations visibles se repère en une seconde en revue de code. Les trois écritures ci-dessous produisent la même complexité quadratique, sans qu'aucune imbrication n'apparaisse à l'oeil.
1. Une recherche linéaire cachée dans une méthode
C'est le cas de la fonction de dédoublonnage du début. Le not in resultat ressemble à un test unique, mais Python parcourt la liste entière pour répondre. Une boucle de n tours qui contient un parcours de n éléments donne bien n × n opérations, même si le code tient sur une ligne.
Les équivalents dans les autres langages : Array.includes() et indexOf() en JavaScript, in_array() en PHP, List.contains() en Java.
2. Un filtre à l'intérieur d'un parcours
Le croisement de deux collections est l'endroit où ça arrive le plus souvent. Filtrer des commandes selon une liste de clients actifs, par exemple.
// Node.js 22, modules ES
const commandesActives = commandes.filter(
(commande) => idsActifs.includes(commande.clientId)
);Une seule ligne, aucune accolade imbriquée, et pourtant includes rebalaye idsActifs du début à chaque commande. Mesuré sur des collections de même taille, après chauffe du compilateur à la volée de V8 : 0,24 ms pour 500 éléments, 3,21 ms pour 2 000, 107 ms pour 10 000, et 2,60 s pour 50 000.
3. Une requête SQL dans une boucle
Récupérer une liste d'articles, puis boucler dessus pour aller chercher le nom de l'auteur article par article. Une requête pour la liste, puis n requêtes pour les détails : c'est le fameux N+1, et il se glisse tout seul dès qu'un ORM charge une relation à la demande.
Sur un banc de mesure avec SQLite en mémoire, 5 000 articles chargés en N+1 demandent 5 001 requêtes et 9,85 ms, contre 3,12 ms pour la jointure unique qui rend le même résultat. Le rapport de 3 semble presque acceptable, et c'est un piège : SQLite en mémoire n'a aucune latence réseau. Avec une base sur un autre serveur, à un aller-retour de 1 ms, les mêmes 5 001 requêtes ajoutent cinq secondes d'attente pure. Ce coût-là ne se voit ni dans le profileur CPU, ni sur un poste de développement où la base tourne en local. La question de savoir où poser ces accès aux données est traitée dans l'article sur le repository pattern et la séparation de l'accès aux données.
Le geste qui corrige : passer de "parcourir" à "demander"
Une liste répond à la question "est-ce que tu contiens cette valeur ?" en regardant ses éléments un par un. Un ensemble, ou un dictionnaire, répond en calculant directement l'emplacement où la valeur devrait se trouver. Ce calcul ne dépend pas du nombre d'éléments stockés, ce qui fait passer la recherche de O(n) à O(1).
La correction de la fonction du début tient en deux lignes de plus.
# Python 3.12
def dedoublonner(lignes: list[str]) -> list[str]:
vus: set[str] = set()
resultat: list[str] = []
for ligne in lignes:
if ligne not in vus:
vus.add(ligne)
resultat.append(ligne)
return resultatSur les 80 000 lignes qui mettaient 15,6 secondes, cette version met 4,86 millisecondes. L'ordre est préservé, contrairement à un passage direct par set(), et le résultat est identique élément par élément.
Côté JavaScript, le même geste consiste à construire un Set avant la boucle plutôt que de rebalayer un tableau à l'intérieur.
// Node.js 22, modules ES
const actifs = new Set(idsActifs);
const commandesActives = commandes.filter(
(commande) => actifs.has(commande.clientId)
);Sur 50 000 éléments, la version avec Set passe de 2,60 s à 7,34 ms, soit un facteur 355. Une ligne ajoutée, un mot changé.
Les pièges
Construire un ensemble pour une seule recherche
Voici le chiffre que je n'attendais pas en préparant cet article. Sur une liste de 1 000 éléments, une seule recherche coûte 6,63 microsecondes en parcours linéaire, contre 9,38 microsecondes si on construit un ensemble avant d'interroger. La construction est elle-même en O(n), donc pour une question unique elle ne rentabilise jamais son coût.
Le basculement arrive à la deuxième recherche : 11,88 microsecondes en liste contre 8,28 avec l'ensemble. À partir de deux interrogations sur la même collection, la structure paie. En dessous, elle coûte.
Optimiser ce qui ne grossira jamais
Une double boucle sur les 12 mois de l'année fait 144 opérations, aujourd'hui et dans dix ans. Une comparaison croisée sur les 5 statuts d'une commande en fait 25. Réécrire ce code au nom de la complexité algorithmique rend le programme moins lisible sans rien gagner de mesurable.
Le critère de décision est simple : est-ce que la taille de l'entrée est fixée par le métier, ou est-ce qu'elle suit le nombre d'utilisateurs, de commandes ou de fichiers importés ? Dans le premier cas, la question ne se pose pas. Dans le second, elle se posera un jour, et le jour en question sera un vendredi soir.
Confondre nombre d'opérations et temps d'attente
Le cas N+1 le montre bien : côté processeur, 5 001 petites requêtes ne coûtent presque rien de plus qu'une grosse. Le coût se trouve entièrement dans l'aller-retour réseau répété. Big O compte des opérations, sans distinguer celles qui prennent une nanoseconde de celles qui prennent une milliseconde. Sur du code qui appelle une base de données, une API externe ou un système de fichiers, le nombre d'appels compte plus que le nombre d'itérations.
Mesurer une seule fois en JavaScript
Pendant la préparation des mesures de cet article, la première série sur 2 000 éléments donnait la version avec Set plus lente que la version avec includes, à 4,59 ms contre 4,04 ms. Résultat absurde au regard de la théorie, et pourtant reproductible : le compilateur à la volée de V8 n'avait pas encore optimisé le code au premier passage. Après une phase de chauffe, l'écart repassait à 26 fois en faveur du Set. Toute mesure en JavaScript qui ne fait tourner la fonction qu'une fois mesure la compilation autant que l'algorithme.
Attendre que la base de données rattrape le coup
Un moteur SQL sait faire des jointures efficaces, à condition qu'on lui donne le travail. Une jointure faite à la main en Python ou en JavaScript après avoir chargé deux tables entières en mémoire ne bénéficie d'aucun index ni d'aucune statistique de table. Le code applicatif refait alors, en moins bien, ce que le moteur aurait fait en quelques millisecondes.
Mesurer, plutôt que deviner
Le raisonnement Big O sert à savoir où regarder. Il ne remplace pas le chronomètre, parce que les constantes cachées et les optimisations du moteur d'exécution décident du résultat réel sur les petites entrées.
Les outils tiennent en trois commandes, disponibles sans rien installer :
- En Python, le module
timeitde la bibliothèque standard, qui répète la mesure et retient le minimum. C'est lui qui a produit tous les chiffres Python de cet article. - En JavaScript,
performance.now()encadrant l'appel, avec une phase de chauffe et plusieurs tours. - Côté base de données,
EXPLAIN ANALYZEsur PostgreSQL, qui donne le plan choisi et le temps réel de chaque étape.
La méthode qui fonctionne consiste à mesurer sur trois volumes croissants plutôt que sur un seul. Un temps isolé ne dit rien, deux temps donnent une pente, trois révèlent la forme de la courbe. Cette façon de procéder par observation avant de toucher au code se rapproche de ce qui est décrit dans l'article sur l'apprentissage du débogage.
Ces réflexes de structure de données font partie des fondations qu'on installe avant d'apprendre un framework. Ils sont travaillés en pratique dans la formation Algorithmique et logique de programmation (référence FND-ALG, 2 jours, 14 heures), dont le module sur les boucles imbriquées et celui sur les tableaux traitent exactement les cas de cet article. Pour aller plus loin sur la qualité du code au sens large, le hub sur les 20 principes de code donne la carte d'ensemble.
Un dernier chiffre pour la route : la fonction de six lignes du début, corrigée en deux lignes de plus, est passée de 15,6 secondes à 4,86 millisecondes. Aucun serveur supplémentaire, aucune bibliothèque ajoutée. Un ensemble à la place d'une liste.
