Le Big O, pourquoi et comment

Le Big O décrit comment le temps d'exécution (ou la mémoire utilisée) d'un algorithme grandit quand la taille de l'entrée `n` grandit. Ce n'est pas une mesure en secondes : c'est une mesure de tendance, utile pour comparer deux approches indépendamment du matériel.

Les complexités les plus courantes, de la plus rapide à la plus lente : O(1) constant, O(log n) logarithmique, O(n) linéaire, O(n log n), O(n²) quadratique, O(2ⁿ) exponentiel. En entretien, tu dois pouvoir nommer la complexité de ta solution et justifier pourquoi.

Pour l'estimer à partir du code : une boucle simple sur `n` éléments → O(n). Deux boucles imbriquées sur `n` → O(n²). Diviser le problème par deux à chaque étape (recherche binaire) → O(log n). Un appel récursif qui explore deux branches à chaque niveau → souvent O(2ⁿ).

La complexité spatiale suit la même logique mais mesure la mémoire supplémentaire utilisée (hors l'entrée elle-même) : un tableau auxiliaire de taille `n` → O(n) d'espace ; quelques variables → O(1) d'espace.

Règle pratique en entretien : commence toujours par une solution brute force (souvent O(n²) ou pire), énonce sa complexité, puis cherche à l'améliorer en identifiant le travail redondant — c'est souvent là qu'apparaissent les hashmaps, les deux pointeurs ou le tri préalable.

Vidéo

Quiz