La notation Big O expliquée avec du vrai code

#algorithms#computer-science#javascript

La notation Big O est enseignée avec des exemples abstraits (trier des tableaux d'entiers, chercher dans des arbres équilibrés) puis discrètement abandonnée dès que l'on commence à livrer de vraies fonctionnalités. C'est une erreur : le même raisonnement explique pourquoi une boucle imbriquée « simple » sur vos données de production peut faire tomber un serveur dès que ces données dépassent quelques milliers de lignes. Voici Big O ancré dans du code que vous écririez réellement.

Ce que mesure réellement Big O

Big O décrit comment le temps d'exécution d'un algorithme (ou son utilisation mémoire) croît quand la taille de l'entrée croît : pas le temps exact, qui dépend de votre CPU, mais la forme de la courbe de croissance. « O(n) » signifie « à peu près proportionnel à la taille de l'entrée ». « O(n²) » signifie « à peu près proportionnel au carré de la taille de l'entrée ». Les facteurs constants et le nombre exact d'instructions sont délibérément écartés ; ce qui compte, c'est ce qui se passe quand n devient grand.

Cela compte parce que les facteurs constants cessent d'avoir de l'importance à grande échelle, et que le taux de croissance est tout ce qui reste. Un algorithme en O(n²) plus rapide qu'un algorithme en O(n) à n = 100 perdra toujours dès que n est assez grand : ce n'est pas une question de « si », seulement de « où » se situe le point de croisement.

O(1) : temps constant

Chercher une valeur par clé dans une Map ou un objet ne ralentit pas quand la table grossit : hacher la clé et sauter vers son compartiment prend le même nombre d'étapes qu'il y ait 10 entrées ou 10 millions.

function getUserById(usersById, id) {
  return usersById.get(id); // O(1), regardless of map size
}

O(n) : temps linéaire

Le travail croît en proportion directe de la taille de l'entrée. Un seul passage sur un tableau (chercher une valeur, la sommer, transformer chaque élément) est le cas classique :

function findFirstAdmin(users) {
  for (const user of users) {
    if (user.role === 'admin') return user; // worst case: checks every user once
  }
  return null;
}

Doublez le tableau, doublez le travail dans le pire cas. C'est du linéaire, et pour la plupart des opérations courantes, c'est parfaitement acceptable.

O(n²) : temps quadratique, celui qui tue discrètement la production

C'est là que vivent les vrais bugs. Imbriquer une boucle dans une boucle sur les mêmes données multiplie le travail :

// find duplicate emails - O(n²): for every user, scan every other user
function findDuplicateEmails(users) {
  const duplicates = [];
  for (let i = 0; i < users.length; i++) {
    for (let j = i + 1; j < users.length; j++) {
      if (users[i].email === users[j].email) {
        duplicates.push(users[i].email);
      }
    }
  }
  return duplicates;
}

Avec 100 utilisateurs, cela fait environ 5 000 comparaisons : instantané. Avec 100 000 utilisateurs, environ 5 milliards : le genre de chose qui marche très bien dans une démo avec des données de test puis dépasse le délai dès qu'elle touche le vrai volume de production. Ce schéma précis (une boucle interne ou un appel interne à .find()/.includes() sur des données qui grossissent avec la boucle externe) est le bug quadratique accidentel le plus courant dans le code applicatif.

La solution consiste presque toujours à échanger de la mémoire contre du temps : construire une structure de recherche une fois (O(n)), puis faire des recherches en O(1) dans une seule boucle (O(n) au total) au lieu de recherches en O(n) dans une boucle (O(n²) au total).

// same result, O(n): one pass to build a Set, one pass to check membership
function findDuplicateEmails(users) {
  const seen = new Set();
  const duplicates = new Set();
  for (const user of users) {
    if (seen.has(user.email)) {
      duplicates.add(user.email);
    }
    seen.add(user.email);
  }
  return [...duplicates];
}

Même résultat, et cela reste rapide quand l'entrée grossit : c'est l'échange que représente presque toujours une Map/Set : payer un peu de mémoire pour transformer une recherche en O(n) en recherche en O(1).

O(log n) : temps logarithmique

Le travail croît bien plus lentement que la taille de l'entrée : chaque étape élimine une grande fraction de ce qu'il reste à chercher. La recherche dichotomique dans un tableau trié en est l'exemple canonique : regarder au milieu, écarter la moitié, recommencer.

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Chercher dans un tableau trié de 1 000 000 d'éléments demande au plus environ 20 comparaisons, et non 1 000 000 : c'est la différence entre O(log n) et O(n) en pratique. C'est aussi pourquoi les index de base de données (typiquement des arbres B) accélèrent les recherches sur de grandes tables : ils transforment ce qui serait un balayage de table en O(n) en un parcours d'arbre en O(log n).

O(n log n) : la complexité de la famille des tris

La plupart des algorithmes de tri par comparaison efficaces (tri fusion, cas moyen du tri rapide, et ce que Array.prototype.sort utilise en coulisses dans les moteurs JS modernes) s'exécutent en O(n log n) : mieux que O(n²), et c'est le plancher théorique du tri par comparaison. Si vous vous surprenez à écrire à la main un tri en O(n²) (comme un tri à bulles naïf), utilisez simplement le sort intégré : il est à la fois plus rapide et déjà correct.

Lire la complexité dans votre propre code

Quelques règles approximatives couvrent la plupart des cas courants :

Une seule boucle sur n éléments : O(n).
Une boucle imbriquée dans une autre, toutes deux sur à peu près le même n : O(n²).
Diviser par deux l'espace de recherche à chaque itération (recherche dichotomique, descente dans un arbre équilibré) : O(log n).
Les méthodes de tableau comme .includes(), .indexOf() et .find() sont chacune en O(n) : en appeler une dans une boucle est exactement le schéma de boucle imbriquée ci-dessus, simplement écrit autrement. C'est l'endroit le plus courant où le comportement quadratique se cache à la vue de tous.

// looks like one loop, is actually O(n²): .includes() scans the array each call
function withoutDuplicates(items) {
  const result = [];
  for (const item of items) {
    if (!result.includes(item)) result.push(item); // O(n) call, inside an O(n) loop
  }
  return result;
}

// O(n): Set.has() is O(1), so the loop stays linear
function withoutDuplicatesFast(items) {
  return [...new Set(items)];
}

À retenir

Big O n'a pas pour but de gratter des millisecondes sur du code qui tourne déjà bien : il s'agit de savoir quels schémas cessent silencieusement de passer à l'échelle. La chose précise qu'il vaut la peine d'entraîner vos yeux à repérer est une opération en O(n) ou pire (.includes(), .find(), une autre boucle) placée dans une boucle sur la même collection qui grossit. Ce seul schéma explique la plupart des bugs du type « ça marchait en dev et ça s'est effondré en production » que vous rencontrerez réellement.