Big-O décrit comment le temps d'exécution ou la mémoire utilisée par un algorithme croît à mesure que la taille d'entrée n augmente. Elle capture le comportement asymptotique du pire cas, en ignorant les constantes et les termes d'ordre inférieur.
Nous nous intéressons au taux de croissance, pas aux comptages exacts d'étapes. O(2n + 5) est simplement O(n) car à mesure que n grandit, les constantes et les termes plus petits n'ont plus d'importance.
| Big-O | Nom | Exemple |
|---|---|---|
| O(1) | constante | accès à un élément du tableau |
| O(log n) | logarithmique | recherche binaire |
| O(n) | linéaire | parcourir une liste |
| O(n log n) | linéarithmique | tri fusion |
| O(n²) | quadratique | boucles imbriquées |
| O(2ⁿ) | exponentielle | sous-ensembles naïfs |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O cache les constantes : un algorithme O(n) avec une grande constante peut être surpassé par O(n log n) sur de petites entrées. Suivez aussi la complexité en espace, pas seulement le temps.
Big-O vous permet de comparer des algorithmes sans les exécuter ni vous préoccuper du matériel.
Elle prédit quelles solutions tiennent la route quand les entrées passent de centaines à millions — la différence entre une fonctionnalité qui passe à l'échelle et une qui dépasse le délai d'exécution.
C'est le vocabulaire que tout ingénieur utilise pour raisonner sur les performances.