Big O – La Boussole du Développeur

Comprendre la notation Big O pour analyser et optimiser les performances de vos algorithmes.

algorithmique

Les tests d'algo à l'oral, c'était mon pire blocage : sans fonctionnalité en face, c'était trop abstrait. Le déclic est venu quand j'ai relié chaque notion à du vrai code.

C'est ce que je te propose ici : relier la notation Big O à ce qui se passe dans ton ordinateur et dans tes composants React. Tu verras pourquoi une interface se fige, comment choisir entre Map, Set et Array, et comment estimer le coût d'un calcul avant de l'écrire.

Points essentiels à retenir :

  • Big O n'est pas juste un sujet théorique, mais un outil concret pour comprendre la consommation de ressources physiques
  • Comprendre Big O te permet d'anticiper les problèmes de performance avant qu'ils ne surviennent
  • La notation aide à choisir la meilleure solution selon les priorités : vitesse, mémoire ou lisibilité
  • Avec Big O, tu passes du code qui « fonctionne » au code qui « fonctionne efficacement »

1. Big O et réalité physique : ce qui se passe vraiment dans ton ordinateur

Avant d'entrer dans la théorie, visualisons concrètement ce qui se passe dans ton ordinateur quand du code s'exécute. Comprendre ces mécanismes physiques te permettra de saisir pourquoi la complexité temporelle est si importante.

Ton code, la RAM et le CPU À gauche, la RAM : des casiers numérotés, n° 40 à n° 45, chacun avec une valeur. Au milieu, le bus : le processeur y lit les valeurs et y écrit les résultats. À droite, le CPU, qui calcule et compare. Ton code, la RAM et le CPU RAMn° 4012n° 417n° 4231n° 435n° 4418n° 459un casier = une adresse CPUcalcule et compare lecture écriture le bus Ton code, la RAM et le CPU À gauche, la RAM : des casiers numérotés, n° 40 à n° 45, chacun avec une valeur. Au milieu, le bus : le processeur y lit les valeurs et y écrit les résultats. À droite, le CPU, qui calcule et compare. Ton code, la RAM et le CPU RAMn° 4012n° 417n° 4231n° 435n° 4418n° 459un casier = une adresse lecture écriture bus CPUcalcule et compare

Le processeur fait des milliards d'opérations par seconde : ce n'est pas une opération qui coûte cher, c'est d'en faire des millions.

Deux façons d'aller chercher une donnée Deux rangées de casiers numérotés de 38 à 45. Accès direct, O(1) : une seule flèche va droit au casier n° 42. Parcours, O(n) : la flèche saute de casier en casier, 38, 39, 40, 41, puis 42, une étape par casier visité. Deux façons d'aller chercher une donnée Accès direct O(1)3839404142434445n° 421 étape, quelle que soit la taille Parcours O(n)3839404142434445départ1 étape par casier visité Deux façons d'aller chercher une donnée Deux rangées de casiers numérotés de 38 à 45. Accès direct, O(1) : une seule flèche va droit au casier n° 42. Parcours, O(n) : la flèche saute de casier en casier, 38, 39, 40, 41, puis 42, une étape par casier visité. Deux façons d'aller chercher une donnée Accès direct O(1)3839404142434445n° 421 étape, quelle que soit la taille Parcours O(n)3839404142434445départ1 étape par casier visité

Comment ton code consomme des ressources physiques

Chaque ligne de code que tu écris se traduit par des opérations physiques dans ton ordinateur :

  • Accès mémoire : quand ton code lit ou écrit des données (tableaux, objets, variables), le CPU doit communiquer avec la RAM
  • Cycles CPU : chaque opération (addition, comparaison, boucle) consomme des cycles de processeur
  • Cache misses : les accès aléatoires à la mémoire peuvent forcer le processeur à attendre les données
Chercher l'utilisateur u7 Deux rangées de 7 casiers contenant des utilisateurs. Array.find(), O(n) : la flèche ouvre les casiers un par un, u3, u9, u1, u5, u2, u8, jusqu'à u7, le septième : 7 casiers ouverts. Map.get(), O(1) : la clé u7 passe par le hachage, qui donne directement le bon casier : 1 casier ouvert. Chercher l'utilisateur u7 Array.find() : O(n)u3u9u1u5u2u8u7départ7 casiers ouverts Map.get() : O(1)u2u9u5u7u1u8u3clé u7hachage1 casier ouvert Chercher l'utilisateur u7 Deux rangées de 7 casiers contenant des utilisateurs. Array.find(), O(n) : la flèche ouvre les casiers un par un, u3, u9, u1, u5, u2, u8, jusqu'à u7, le septième : 7 casiers ouverts. Map.get(), O(1) : la clé u7 passe par le hachage, qui donne directement le bon casier : 1 casier ouvert. Chercher l'utilisateur u7 Array.find() : O(n)u3u9u1u5u2u8u7départ7 casiers ouverts Map.get() : O(1)u2u9u5u7u1u8u3clé u7hachage1 casier ouvert

find() ouvre les casiers un par un jusqu'au bon : plus le tableau est long, plus il y a de casiers à ouvrir. Une Map transforme la clé en numéro de casier (le hachage) et ouvre directement le bon.

Quand n double : combien d'opérations ? Un carré par opération, pour n = 4 puis n = 8. O(1) : 1 opération, puis 1. O(n) : 4 opérations, puis 8. O(n²) : 16 opérations, puis 64. Quand n double : combien d'opérations ? O(1) O(n) O(n²) n = 4 1 opération 4 opérations 16 opérations n = 8 1 opération 8 opérations 64 opérations Quand n double : combien d'opérations ? Un carré par opération, pour n = 4 puis n = 8. O(1) : 1 opération, puis 1. O(n) : 4 opérations, puis 8. O(n²) : 16 opérations, puis 64. Quand n double : combien d'opérations ? n = 4 n = 8 O(1) 1 opération 1 opération O(n) 4 opérations 8 opérations O(n²) 16 opérations 64 opérations
Chaque carré est une opération. Quand n passe de 4 à 8, O(1) reste à 1, O(n) double (4 → 8) et O(n²) quadruple (16 → 64).

Pourquoi la complexité temporelle compte

Big O ne donne pas un temps, mais une croissance : combien d'opérations en plus quand n grandit. Voici ce que cela donne pour trois tailles de liste.

Complexité n = 10 n = 1 000 n = 1 000 000 Ressenti dans l'interface
O(1)
map.get(id)
1 1 1 Imperceptible, quelle que soit la taille
O(log n)
recherche dichotomique
≈ 3 ≈ 10 ≈ 20 Imperceptible
O(n)
filter(), find()
10 1 000 1 000 000 Imperceptible jusqu'au million pour des opérations simples. Afficher un million de lignes, en revanche, demande de virtualiser la liste
O(n log n)
sort()
≈ 33 ≈ 10 000 ≈ 20 000 000 Imperceptible à 1 000. Vers le million, plusieurs centaines de millisecondes : l'interface se fige
O(n²)
filter() dans un map()
100 1 000 000 1 000 000 000 000 Fluide à 10. À 1 000, quelques millisecondes, à repayer à chaque rendu. Au million, des dizaines de minutes : l'onglet ne répond plus

Ordres de grandeur, pas des mesures : nombre d'opérations arrondi, logarithme en base 2. Le temps réel dépend de la machine, du moteur JavaScript et du coût de chaque opération.

Ordre de grandeur : une boucle double (O(n²)) reste fluide sur 1 000 éléments, mais commence à figer l'interface vers 3 000 éléments (environ 10 millions d'opérations, au-delà des 50 ms).

Ce qui se passe dans ton navigateur : JavaScript exécute ton code et met à jour l'interface sur le même thread, le thread principal. Une tâche de plus de 50 ms est une tâche longue (MDN) : tant qu'elle tourne, clics, frappes et défilement attendent.

Pour visualiser : la soirée à 16 invités

Imagine une soirée avec 16 invités. Selon ce que tu dois y faire, le travail ne grandit pas de la même façon quand le nombre d'invités double.

  • O(1) : le videur vérifie ta carte à l'entrée. Un seul geste, qu'il y ait 16 ou 1 000 invités.
  • O(log n) : tu devines le numéro de vestiaire d'un invité, entre 1 et 16, en demandant « plus grand ou plus petit ? ». Chaque réponse élimine la moitié des numéros : 4 questions pour 16 invités, 5 pour 32.
  • O(n) : tu dis bonjour à chaque invité. 16 bonjours pour 16 invités, 32 pour 32.
  • O(n²) : chacun serre la main de tous les autres. 120 poignées de main pour 16 invités, 496 pour 32 : doubler les invités multiplie le travail par 4 environ.
Les poignées de main, étape par étape Des invités en cercle, reliés par un trait pour chaque poignée de main. 2 invités : 1 poignée de main. 3 invités : 3. 4 invités : 6. 5 invités : 10. 16 invités : 120 traits, le cercle est presque plein. Les poignées de main, étape par étape 2 invités→ 1 poignée 3 invités→ 3 poignées 4 invités→ 6 poignées 5 invités→ 10 poignées 16 invités→ 120 poignées Les poignées de main, étape par étape Des invités en cercle, reliés par un trait pour chaque poignée de main. 2 invités : 1 poignée de main. 3 invités : 3. 4 invités : 6. 5 invités : 10. 16 invités : 120 traits, le cercle est presque plein. Les poignées de main, étape par étape 2 invités→ 1 poignée 3 invités→ 3 poignées 4 invités→ 6 poignées 5 invités→ 10 poignées 16 invités→ 120 poignées
Chaque trait, c'est deux invités qui se serrent la main. Avec 2 fois plus d'invités, il y a environ 4 fois plus de poignées de main (120 pour 16 invités, 496 pour 32) : c'est ça, O(n²).

En Big O, on garde la forme de la croissance, pas le chiffre exact : n × (n − 1) / 2, c'est toujours O(n²).

2. Big O : qu'est-ce que c'est exactement ?

Big O est une notation mathématique qui décrit comment la performance d'un algorithme évolue à mesure que ses données d'entrée augmentent. En termes simples, c'est une façon de quantifier l'efficacité de ton code lorsqu'il doit traiter de plus en plus de données.

Pourquoi est-ce important pour un développeur React ?

Lorsque tu développes des applications React, l'efficacité devient critique. Un rendu inefficace peut rendre ton interface lente et peu réactive. Comprendre Big O t'aide à :

  • Optimiser tes rendus : les problèmes de performance dans React viennent souvent de rendus inutiles ou d'algorithmes inefficaces exécutés pendant le rendu
  • Gérer les données intelligemment : savoir manipuler efficacement de grands ensembles de données dans ton state
  • Prendre de meilleures décisions : choisir entre différentes structures de données ou méthodes selon le contexte
Croissance du temps selon la complexité : O(n²) dépasse le seuil des 50 ms vers 3 000 éléments. Quatre courbes, n de 0 à 10 000. O(1) reste plate, O(log n) monte puis s'aplatit, O(n) monte en ligne droite, ces trois-là restent sous le seuil des 50 ms. O(n²) croise la ligne pointillée des 50 ms vers 3 000 éléments, puis sort du cadre par le haut. fluide l'interface se fige 50 ms O(n²) ↑ explose O(1) O(log n) O(n) ≈ 3 000 éléments 0 1 000 3 000 10 000 n (nombre d'éléments) temps Croissance du temps selon la complexité : O(n²) dépasse le seuil des 50 ms vers 3 000 éléments. Quatre courbes, n de 0 à 10 000. O(1) reste plate, O(log n) monte puis s'aplatit, O(n) monte en ligne droite, ces trois-là restent sous le seuil des 50 ms. O(n²) croise la ligne pointillée des 50 ms vers 3 000 éléments, puis sort du cadre par le haut. fluide se fige 50 ms O(n²) ↑ O(1) O(log n) O(n) ≈ 3 000 éléments 0 1 000 3 000 10 000 n (nombre d'éléments) temps
Formes calculées à partir des fonctions. Le seuil de O(n²) suit la mesure de l'article ; la hauteur des trois autres courbes est illustrative.

3. Les notations Big O essentielles (et leur impact concret)

Voici les principales complexités que tu rencontreras, et ce qu'elles signifient pour ton code React.

Notation Nom Description Impact sur ton app React
O(1) Constant Le temps d'exécution reste le même quelle que soit la taille des données Idéal pour les opérations critiques au rendu : accès à un élément précis par sa clé
O(log n) Logarithmique Augmente lentement à mesure que les données grandissent Parfait pour les recherches dans de grandes collections triées
O(n) Linéaire Le temps d'exécution augmente proportionnellement avec les données Acceptable pour la plupart des rendus de listes, mais attention aux grandes listes
O(n²) Quadratique Le temps d'exécution augmente avec le carré de la taille des données Problématique pour les interfaces : peut bloquer le thread principal
O(2^n) Exponentiel Explosion du temps d'exécution avec la croissance des données À éviter dans le code client : l'interface se fige

4. Big O dans tes projets React

Voyons comment ces concepts s'appliquent concrètement dans du code React avec TypeScript que tu écris au quotidien.

Rendu de listes et complexité

Exemple 1 : rendu inefficace (O(n²))

type User = { id: string; name: string; friendIds: string[] };

// 🔴 O(n²) : pour chaque utilisateur, on reparcourt toute la liste
export function UserList({ users }: { users: User[] }) {
  return (
    <div>
      {users.map((user) => (
        <div key={user.id}>
          {user.name}
          <p>
            Amis :{' '}
            {users
              .filter((friend) => user.friendIds.includes(friend.id))
              .map((friend) => friend.name)
              .join(', ')}
          </p>
        </div>
      ))}
    </div>
  );
}

Exemple 2 : une Map id → nom, construite une fois (O(n + a))

import { useMemo } from 'react';

type User = { id: string; name: string; friendIds: string[] };

// ✅ O(n + a) : une Map id → nom, construite une fois (a = nombre total de liens d'amitié)
export function UserList({ users }: { users: User[] }) {
  // O(n), recalculée seulement quand users change
  const nameById = useMemo(
    () => new Map(users.map((user) => [user.id, user.name])),
    [users],
  );

  return (
    <div>
      {users.map((user) => {
        // Accès O(1) par id pour chaque ami
        const friendNames = user.friendIds
          .map((id) => nameById.get(id))
          .filter((name) => name !== undefined);

        return (
          <div key={user.id}>
            {user.name}
            <p>Amis : {friendNames.length > 0 ? friendNames.join(', ') : 'aucun'}</p>
          </div>
        );
      })}
    </div>
  );
}

La Map est construite une seule fois par liste d'utilisateurs, avec useMemo. Ensuite, chaque ami se retrouve par son id en O(1), et l'écran affiche bien des noms. Total : O(n + a), où a est le nombre total de liens d'amitié.

Conseil pratique : prétraite tes données une fois (Map, Set, index) plutôt que de refaire une recherche pour chaque élément pendant le rendu.

Optimisation des hooks React

Avant : un calcul O(n²) dans un useEffect

import { useEffect, useState } from 'react';

type Product = { id: string; name: string; category: string; price: number };

// 🔴 O(n²), et un rendu de plus à chaque changement de products
export function ProductGrid({ products }: { products: Product[] }) {
  const [filteredProducts, setFilteredProducts] = useState<Product[]>([]);

  useEffect(() => {
    // Pour chaque produit, on reparcourt tous les produits : O(n²)
    const filtered = products.filter((product) =>
      products.some((p) => p.category === product.category && p.price < product.price),
    );
    setFilteredProducts(filtered); // second rendu
  }, [products]);

  return (
    <ul>
      {filteredProducts.map((product) => (
        <li key={product.id}>{product.name}</li>
      ))}
    </ul>
  );
}

Après : useMemo et une Map, O(n)

import { useMemo } from 'react';

type Product = { id: string; name: string; category: string; price: number };

// ✅ O(n) : deux passages et une Map, calculés pendant le rendu
export function ProductGrid({ products }: { products: Product[] }) {
  const filteredProducts = useMemo(() => {
    // 1er passage, O(n) : prix minimum de chaque catégorie
    const minPriceByCategory = new Map<string, number>();
    for (const product of products) {
      const currentMin = minPriceByCategory.get(product.category) ?? Infinity;
      if (product.price < currentMin) {
        minPriceByCategory.set(product.category, product.price);
      }
    }

    // 2e passage, O(n) : les produits plus chers que le minimum de leur catégorie
    return products.filter(
      (product) => product.price > (minPriceByCategory.get(product.category) ?? Infinity),
    );
  }, [products]);

  return (
    <ul>
      {filteredProducts.map((product) => (
        <li key={product.id}>{product.name}</li>
      ))}
    </ul>
  );
}

La liste filtrée se déduit de products : pas besoin d'état ni d'effet (Vous n’avez pas forcément besoin d’un Effet, sur react.dev).

5. Structures de données et leur complexité

Le choix d'une structure de données peut fortement changer les performances de ton application React. Comprendre les caractéristiques de chacune est essentiel pour faire le bon choix.

Structure Accès Recherche Insertion Suppression Idéale pour
Object / Map O(1)*** O(1) par clé***
O(n) par valeur
O(1)*** O(1)*** Cache, lookups, associer des données
Array O(1) O(n) O(n)* O(n)* Listes ordonnées, accès par index
Set N/A O(1)*** O(1)*** O(1)*** Valeurs uniques, vérifications d'appartenance
LinkedList O(n) O(n) O(1)** O(1)** Insertions/suppressions fréquentes

* O(1) à la fin du tableau, mais O(n) ailleurs
** O(1) si la position est connue
*** En moyenne : Map, Set et les objets reposent sur des tables de hachage

Ce gain de vitesse a un prix : une Map rend la recherche O(1), mais elle occupe de la mémoire en plus de ton tableau, une entrée par élément. C'est un compromis entre temps et mémoire, un choix à faire, pas un gain gratuit.

Application concrète en React

Un sélecteur de produits avec une Map

import { useMemo } from 'react';

type Product = { id: string; name: string; category: string; price: number };

type Props = {
  products: Product[];
  onSelect: (product: Product) => void;
};

// ✅ Map id → produit dérivée de products : O(n) une fois, puis O(1) par sélection
export function ProductSelector({ products, onSelect }: Props) {
  const productById = useMemo(
    () => new Map(products.map((product) => [product.id, product])),
    [products],
  );

  const handleSelect = (id: string) => {
    const product = productById.get(id); // O(1), là où products.find() serait O(n)
    if (product) onSelect(product);
  };

  return (
    <select defaultValue="" onChange={(event) => handleSelect(event.target.value)}>
      <option value="" disabled>
        Choisis un produit
      </option>
      {products.map((product) => (
        <option key={product.id} value={product.id}>
          {product.name}
        </option>
      ))}
    </select>
  );
}

La Map se déduit entièrement de products : useMemo la calcule pendant le rendu, là où useState + useEffect affichait d'abord une Map vide, déclenchait un second rendu et gardait une copie de products à synchroniser.

6. Le bon réflexe : estimer n avant de choisir

Avant de choisir une structure ou d'optimiser, pose-toi deux questions.

  • Combien d'éléments aujourd'hui, et dans un an ? 50 produits dans un menu, un O(n²) passe. Un catalogue qui atteindra 50 000 lignes, non. Prends le volume prévu, pas celui de ta base de test.
  • Où est la boucle dans le rendu ? Un calcul fait une fois au chargement ne pèse pas comme un calcul refait à chaque rendu, à chaque frappe dans un champ de recherche, ou pour chaque élément d'une liste.

Si n reste petit, garde le code le plus lisible. Si n grandit, ou si la boucle tourne à chaque rendu, choisis la bonne structure (Map, Set) et mémorise le résultat avec useMemo. En cas de doute, mesure : l'onglet Performance des DevTools signale les tâches longues.

7. En entretien

Pourquoi préférer une Map à Array.find() ?

find() parcourt le tableau jusqu'à trouver l'élément : O(n) à chaque recherche. Une Map construite une fois en O(n) répond ensuite en O(1) par clé, ce qui paie dès que les recherches se répètent.

Quelle est la complexité de deux boucles imbriquées sur le même tableau ?

O(n²) : pour chacun des n éléments, la boucle intérieure en parcourt n. C'est le cas d'un filter() ou d'un includes() appelé dans un map().

useMemo rend-il un calcul plus rapide ?

Non : il évite de le refaire tant que ses dépendances ne changent pas. Le premier calcul garde la même complexité ; pour aller plus vite, il faut changer d'algorithme ou de structure.

8. Erreurs courantes et comment les éviter

Patterns à éviter en React

  • Boucles imbriquées dans les rendus (O(n²)) : prétraite les données avant le rendu
  • Calculs répétés : utilise useMemo pour mémoriser les résultats coûteux
  • Recherches inefficaces : préfère Map ou Set à filter() pour des recherches fréquentes
  • Un Context mal découpé : chaque changement de sa valeur fait re-rendre tous les composants qui le lisent. Sépare les données qui changent souvent de celles qui bougent peu, et mémorise la valeur passée au Provider

Règle pratique : jusqu'à quelques centaines d'éléments, presque tout passe. Au-delà de quelques milliers, évite O(n²) dans le rendu. Vers le million, même un tri en O(n log n) dépasse les 50 ms : sors le calcul du thread principal (Web Worker) ou fais-le côté serveur.

À retenir

  • Big O n'est pas qu'un concept théorique : c'est ta boussole pour comprendre comment ton code consomme des ressources physiques (CPU, RAM, stockage).
  • Choisis les bonnes structures : Map pour les recherches fréquentes par clé (O(1)), Array pour l'accès séquentiel, Set pour les vérifications d'appartenance.
  • Prétraite tes données : sors les opérations coûteuses des boucles du rendu et mémorise les résultats dérivés avec useMemo, plutôt qu'avec un état et un effet.
  • Estime n avant de choisir : combien d'éléments aujourd'hui et dans un an, et combien de fois la boucle tourne (une fois, ou à chaque rendu).
  • Le contexte décide : le meilleur algorithme dépend toujours des priorités du projet (vitesse, mémoire ou lisibilité).