Big O : lire la complexité en 2 minutes
La complexité décrit comment le coût d'un algorithme évolue quand la taille des données augmente. En entretien, on attend que tu l'annonces spontanément.
À retenir
- O(1) : accès direct (tableau par index, clé de dictionnaire).
- O(log n) : on divise le problème par deux (recherche binaire, arbre équilibré).
- O(n) : un parcours complet des données.
- O(n log n) : le tri de référence.
- O(n²) : deux boucles imbriquées — à éviter dès que n grandit.
Compter sans se tromper
Regarde les boucles et les appels récursifs. Deux boucles côte à côte donnent O(n + m), deux boucles imbriquées donnent O(n × m). Les constantes disparaissent : 3n + 10 reste O(n).
Le compromis temps / mémoire
Passer de O(n²) à O(n) se fait souvent en stockant ce qu'on a déjà vu dans un Set ou une Map. Tu échanges de la mémoire contre du temps : dis-le explicitement.
// O(n²)
for (const a of nums) for (const b of nums) ...
// O(n) avec une Map
const vus = new Map();
for (const [i, n] of nums.entries()) {
if (vus.has(cible - n)) return [vus.get(cible - n), i];
vus.set(n, i);
}La complexité mémoire compte aussi
Une solution récursive coûte O(profondeur) en pile. Une copie de tableau coûte O(n). Annonce toujours les deux : temps et espace.
Pièges fréquents
- Oublier la complexité du tri intégré (O(n log n)).
- Dire O(1) pour une recherche dans un tableau (c'est O(n)).
- Ignorer la mémoire consommée par la récursion.
Questions que le recruteur peut poser
- Quelle est la complexité de ta solution ?
- Peux-tu faire mieux en temps ? À quel coût mémoire ?
- Que se passe-t-il si n vaut 10 millions ?