La Big O Notation (ou notation Grand O) est un outil mathématique utilisé en informatique pour décrire la complexité d'un algorithme — c'est-à-dire comment son temps d'exécution ou sa consommation mémoire évolue en fonction de la taille des données en entrée.
Elle exprime le comportement dans le pire cas, ce qui permet de comparer objectivement des algorithmes indépendamment du matériel ou du langage utilisé.
Les complexités les plus courantes
| Notation | Nom | Exemple |
|---|---|---|
| O(1) | Constante | Accès direct à un élément |
| O(log n) | Logarithmique | Recherche binaire |
| O(n) | Linéaire | Parcours d'une liste |
| O(n log n) | Quasi-linéaire | Quicksort, Timsort |
| O(n²) | Quadratique | Boucles imbriquées, tri à bulles |
| O(2ⁿ) | Exponentielle | Récursion non optimisée |
Exemple pratique
# O(n) — on parcourt chaque élément une fois
def find_max(arr):
max_val = arr[0]
for item in arr:
if item > max_val:
max_val = item
return max_val
# O(n²) — deux boucles imbriquées
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]À retenir
La Big O Notation ne mesure pas une durée absolue mais une tendance de croissance. Un algorithme O(log n) reste efficace sur des millions d'entrées, là où un O(n²) devient rapidement prohibitif.
Pour aller plus loin : Complexité algorithmique et performance — analyse complète
