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.
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.
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
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.
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.
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
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
useMemopour 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é).