La Notation Big O Expliquée avec des Exemples de Code

Une recherche dans un dictionnaire Python prend environ 100 nanosecondes, que le dictionnaire contienne 1 000 clés ou 1 000 000. Une double boucle qui cherche des doublons dans une liste prend une demi-milliseconde sur 200 éléments et 136 millisecondes sur 3 200. Seize fois l’entrée, presque 280 fois l’attente. Même machine, même Python. La notation Big O est le nom de cette différence.

Ce que mesure la notation Big O

Big O décrit comment le temps d’exécution (ou l’utilisation de la mémoire) d’un morceau de code croît quand l’entrée grandit. Ce n’est pas une mesure au chronomètre, et peu importe que votre ordinateur soit rapide ou lent. Ce qui compte, c’est la forme de la courbe de croissance : quand vous doublez l’entrée, le temps double-t-il, quadruple-t-il, ou bouge-t-il à peine ?

La notation élimine tout ce qui ne change pas cette forme, des facteurs constants au matériel sur lequel le code tourne. O(n) signifie “proportionnel à n”, que le coût réel soit 3n + 7 ou 0.001n + 1000000. Rendez n assez grand et il ne reste que la forme.

Exemples de Big O en Python, chronométrés à des tailles d’entrée croissantes

Chaque fonction ci-dessous a été chronométrée avec le module timeit de Python sur Python 3.11, à des tailles d’entrée séparées d’un ordre de grandeur (ou d’un doublement).

Temps constant : une recherche dans un dictionnaire

1
2

def dict_lookup(d, key):
    return d[key]

L’entrée est multipliée par mille. Le temps par appel reste stable, dans le bruit de mesure. Un dictionnaire est une table de hachage : Python calcule le hash de la clé et saute directement au bucket correspondant, quel que soit le nombre d’autres entrées. C’est du O(1), temps constant.

Temps linéaire : additionner une liste

1
2
3
4
5

def sum_loop(nums):
    total = 0
    for n in nums:
        total += n
    return total

Chaque fois que n est multiplié par dix, le temps augmente d’environ dix fois. La boucle touche chaque élément exactement une fois, donc le travail évolue directement avec l’entrée. C’est du O(n), temps linéaire, et c’est là que vit la majorité du code quotidien.

Temps quadratique : chercher des doublons de façon naïve

1
2
3
4
5
6

def has_duplicate_naive(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Doubler n quadruple approximativement le temps à chaque étape. La boucle externe tourne n fois et la boucle interne tourne près de n fois à chaque itération externe, donc le travail total est proportionnel à n * n. C’est du O(n^2), temps quadratique. C’est la classe qui ruine le code en production, parce qu’elle a l’air correcte avec un test de 50 lignes et qu’elle expire avec 50 000.

Temps logarithmique : recherche binaire

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Une multiplication par mille de n fait à peine doubler le temps. Chaque étape de la boucle élimine la moitié de l’intervalle restant, donc le nombre d’étapes nécessaires croît avec log2(n) plutôt qu’avec n : environ 10 étapes pour mille éléments, environ 20 pour un million. C’est du O(log n). Git bisect exécute le même algorithme sur l’historique des commits plutôt que sur un tableau trié : il trouve le commit fautif parmi des centaines en quelques étapes seulement, car chaque test élimine la moitié de l’intervalle restant.

Temps linéarithmique : trier

1

sorted_nums = sorted(nums)

Chaque multiplication par dix de n coûte plus de dix fois plus de temps, mais bien loin du facteur cent qu’afficherait un algorithme quadratique. La fonction sorted() de Python utilise Timsort, qui effectue O(n log n) comparaisons : la fusion se déroule en environ log n rounds, et chaque round touche chacun des n éléments une fois pour fusionner les séquences adjacentes. Tout tri généraliste que vous utiliserez au quotidien (Timsort, tri fusion, le cas moyen du tri rapide) se situe ici, ce qui explique pourquoi O(n log n) est considéré comme “le mieux qu’un tri puisse faire” plutôt que comparé à O(n).

Les classes de complexité Big O les plus courantes, de la plus rapide à la plus lente

Regardez les deux dernières lignes. Passer de O(n log n) à O(n^2) avec un million d’éléments, c’est la différence entre un rapport qui s’exécute en une seconde et un autre encore en cours quand quelqu’un tue le processus.

Ce que la notation Big O ne dit pas

Big O décrit la croissance asymptotique, c’est-à-dire ce qui se passe quand n devient arbitrairement grand. Trois choses échappent à cette description.

Les constantes sont invisibles. Un O(n) avec un facteur constant de 1000 peut être plus lent en pratique qu’un O(n^2) avec une constante minuscule, pour tout n que vous verrez jamais. Big O vous dit quelle courbe l’emporte à terme, pas quelle fonction est la plus rapide sur vos données. C’est pourquoi le tri par insertion, qui est en O(n^2), reste le meilleur choix pour les très petits tableaux, et pourquoi Timsort utilise un tri par insertion binaire pour construire chaque petite séquence (run) jusqu’à une longueur minimale (minrun, typiquement 32 à 64 éléments) avant de commencer à fusionner les séquences entre elles.

Un petit n ne montre pas la courbe. Les temps quadratiques ci-dessus ne sont devenus visiblement quadratiques qu’à partir de quelques centaines d’éléments. À n = 10, presque tout se termine avant qu’on le remarque, ce qui explique qu’une fonction peut passer tous les tests écrits en local et s’effondrer ensuite sur les volumes de données de production.

La complexité spatiale est un axe à part. dict_lookup, sum_loop, has_duplicate_naive et binary_search tournent toutes avec une mémoire supplémentaire quasiment constante : aucune n’alloue une seconde structure de données proportionnelle à l’entrée. sorted() si : elle renvoie une nouvelle liste de la même taille que l’entrée, O(n) en espace, parce qu’elle ne trie jamais sur place. Certains algorithmes échangent délibérément de la mémoire contre de la vitesse : une fonction de Fibonacci avec mémoïsation stocke chaque résultat déjà calculé, dépensant O(n) d’espace pour transformer O(2^n) de temps en O(n). Quand vous annoncez la complexité d’une fonction, précisez l’axe concerné : la version la plus rapide est souvent celle qui consomme le plus de mémoire.

Comment repérer un O(n^2) caché dans votre code

La double boucle vue plus haut est le cas évident. Celui qui arrive en production n’a généralement aucune boucle imbriquée visible.

Des tests d’appartenance dans une boucle. x in une_liste est en O(n) sur une liste, car Python doit la parcourir entièrement. Exécuter ce test dans une boucle qui tourne déjà n fois vous donne un O(n^2) sans qu’un second for soit visible :

1
2
3
4
5
6

# O(n^2) : "in" parcourt toute la liste à chaque itération
seen = []
for item in items:
    if item in seen:
        continue
    seen.append(item)

Remplacez la liste par un set, où l’appartenance est en O(1), et la boucle redescend à O(n) :

1
2
3
4
5
6

# O(n) : "in" est une recherche par hachage
seen = set()
for item in items:
    if item in seen:
        continue
    seen.add(item)

Reconstruire une liste au lieu d’y ajouter des éléments. result + [item] alloue une nouvelle liste et y copie chaque élément déjà existant ; result.append(item) fait grandir la liste existante sur place.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def build_with_plus(n):
    result = []
    for i in range(n):
        result = result + [i]   # copie tout ce qui a été construit jusqu'ici, à chaque fois
    return result

def build_with_append(n):
    result = []
    for i in range(n):
        result.append(i)        # O(1) amorti
    return result

Construire une liste de 8 000 éléments avec + a pris 65 ms. La même liste avec .append() a pris 0,15 ms. L’écart se creuse à mesure que n grandit, parce que l’un est quadratique et l’autre linéaire.

La requête N+1. Vous récupérez une liste de lignes, puis vous la parcourez en lançant une requête supplémentaire par ligne pour les données associées, et une seule requête est devenue n + 1 : O(n) allers-retours vers la base de données au lieu d’un seul. Un index, comme vu dans comment fonctionnent les index de base de données, transforme une recherche unique d’un balayage O(n) de la table en O(log n). Il ne fait rien pour une boucle qui envoie mille requêtes séparées. Le correctif a la même forme que celui du set ci-dessus : remplacez l’opération par ligne par une opération faite une seule fois. Ici, cela veut dire une seule requête avec une jointure, que les types de JOIN en SQL expliqués avec des exemples détaille.

Comment mesurer la complexité de votre propre code

Choisissez la fonction suspecte, généralement celle avec une boucle dont le nombre d’itérations dépend de la taille des données. Chronométrez-la avec timeit à trois ou quatre tailles d’entrée, chacune dix fois la précédente, et divisez chaque temps par le précédent. Un ratio proche de 1 indique du O(1) ou du O(log n). Proche de 10, c’est linéaire. Entre 10 et 100, c’est du O(n log n), comme le 17-21 affiché par le tableau de sorted(). Proche de 100 signifie qu’il y a un O(n^2) à débusquer ; si cela rend les grandes tailles trop lentes à attendre, doublez n au lieu de le multiplier par dix et cherchez un ratio proche de 4. Commencez par les tests d’appartenance sur des listes et les reconstructions avec + dans cette boucle, puis toute requête envoyée une fois par ligne.

Articles associés

• Git Bisect : trouver le commit qui a introduit un bug
• Comment Fonctionnent les Index de Base de Données
• Les Types de JOIN en SQL Expliqués avec des Exemples