Notation big-O et analyse de complexité : mesurer le coût d’un algorithme

📍 Guide principal : Mathématiques appliquées à l’informatique : le socle pratique
Ce tutoriel approfondit la partie analyse de complexité du guide principal — à parcourir d’abord pour situer pourquoi la classe asymptotique d’un algorithme prime sur les micro-optimisations.

Tout développeur a vu un programme qui marche très bien sur dix éléments et explose à dix mille. Cette discontinuité ne vient pas du langage, du framework ou du serveur : elle vient de la classe de complexité de l’algorithme. La notation O décrit comment le coût grandit avec la taille de l’entrée — et comprendre ce coût permet de prédire la limite de scaling avant qu’un incident de production ne le révèle. Ce tutoriel pose, étape par étape, les outils pour analyser un code, mesurer sa complexité réelle, et choisir entre plusieurs algorithmes en connaissance de cause.

Prérequis

• Python 3.10 ou plus récent
• matplotlib et numpy pour les graphiques (optionnel mais recommandé)
• Niveau attendu : intermédiaire — vous savez écrire une boucle imbriquée et une fonction récursive
• Temps estimé : 90 minutes

Étape 1 — Lire la définition formelle de O

Avant de plonger dans les exemples, il faut une définition précise. On dit que f(n) = O(g(n)) s’il existe deux constantes c > 0 et n₀ ≥ 0 telles que pour tout n ≥ n₀, f(n) ≤ c × g(n). Autrement dit, g majore f à une constante multiplicative près, à partir d’une certaine taille. Trois conséquences pratiques. D’abord, les constantes disparaissent : 3n + 100 est O(n). Ensuite, les termes dominés disparaissent : n² + n + 1 est O(n²). Enfin, la majoration est non stricte : O(n) est aussi O(n²), même si on préfère toujours la borne la plus serrée disponible.

Trois sœurs de la notation O complètent l’arsenal. Ω(g(n)) minore : il existe c, n₀ tels que f(n) ≥ c × g(n). Θ(g(n)) est l’encadrement : f = O(g) et f = Ω(g). La notation o(g(n)) est plus stricte que O : f est négligeable devant g. Quand on parle de la complexité d’un algorithme « en O(n log n) », on entend généralement Θ(n log n) — borne serrée — mais l’usage tolère O.

Étape 2 — Identifier la classe d’un code à la lecture

L’analyse à la lecture repose sur quelques règles simples. Une boucle for qui itère n fois contribue un facteur n. Deux boucles imbriquées contribuent n². Une boucle qui divise la plage par 2 à chaque étape (i = i // 2) contribue log n. Un appel récursif sur la moitié de l’entrée fait log n ; sur deux moitiés indépendantes, fait n log n via le théorème maître ; sur la totalité moins un, fait n.

# classify_examples.py — quelques cas typiques
def f1(arr):  # O(1) — accès direct
    return arr[0] if arr else None

def f2(arr):  # O(n) — un seul parcours
    return sum(arr)

def f3(arr):  # O(n²) — boucles imbriquées
    return sum(a + b for a in arr for b in arr)

def f4(n):  # O(log n) — division successive
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

def f5(arr):  # O(n log n) — tri Python (Timsort)
    return sorted(arr)

def f6(n):  # O(2^n) — Fibonacci naïf
    if n < 2: return n
    return f6(n-1) + f6(n-2)

Lisez chaque fonction en marquant mentalement sa classe. f1 exécute une opération constante. f2 visite chaque élément exactement une fois. f3 compose deux boucles indépendantes sur la même liste. f4 divise n par 2 jusqu’à 1 — c’est log₂(n) itérations. f5 appelle Timsort, qui est en O(n log n) dans le pire cas. f6 recalcule deux sous-problèmes à chaque appel — son arbre d’exécution est exponentiel. Ce dernier exemple est crucial : la récursion sans mémoïsation génère des coûts catastrophiques même pour des entrées raisonnables.

Étape 3 — Mesurer le coût réel avec timeit

L’analyse théorique est un bon guide mais pas un substitut à la mesure. Les constantes cachées par la notation O peuvent dominer pour de petites entrées, et certains algorithmes ont un cas moyen très différent de leur pire cas. Le module timeit de la bibliothèque standard de Python isole proprement le code mesuré, neutralise le ramasse-miettes et répète la mesure pour réduire le bruit.

# benchmark.py
import timeit, random

def linear_search(arr, target):
    for x in arr:
        if x == target: return True
    return False

def binary_search(arr, target):  # exige arr trié
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return True
        if arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return False

for n in (1_000, 10_000, 100_000, 1_000_000):
    arr = sorted(random.sample(range(n*10), n))
    target = arr[-1]  # pire cas pour linear_search
    t_lin = timeit.timeit(lambda: linear_search(arr, target), number=100)
    t_bin = timeit.timeit(lambda: binary_search(arr, target), number=100)
    print(f"n={n:>9} | linéaire={t_lin:.4f}s | binaire={t_bin:.5f}s | ratio={t_lin/t_bin:>7.0f}x")

L’exécution affiche un tableau qui montre concrètement la divergence : pour n=1000, la recherche linéaire est environ 100× plus lente que la dichotomique ; pour n=1000000, le facteur dépasse 10 000×. C’est exactement ce que prédit l’analyse asymptotique — n / log₂(n) = 1000000 / 20 = 50000 — modulo les constantes. Cette mesure systématique sur des tailles croissantes est le meilleur garde-fou contre l’illusion qu’un algorithme « marche bien » alors qu’il n’a été testé qu’à petite échelle.

Étape 4 — Tracer la courbe de coût

Un graphique vaut mille mesures. Tracer le temps d’exécution en fonction de n permet de reconnaître visuellement la classe de complexité : une droite (échelle linéaire) pour O(n), une parabole pour O(n²), une asymptote presque plate pour O(log n). En échelle log-log, chaque classe devient une droite dont la pente vaut l’exposant — c’est la technique standard pour estimer empiriquement la classe d’un algorithme dont le code est une boîte noire.

# plot_complexity.py
import timeit, matplotlib.pyplot as plt
import numpy as np

def quadratic(n):
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1
    return s

ns = [100, 200, 400, 800, 1600, 3200]
times = [timeit.timeit(lambda: quadratic(n), number=1) for n in ns]

plt.figure()
plt.loglog(ns, times, "o-", label="mesuré")
plt.loglog(ns, [t * (n/ns[0])**2 for n, t in zip(ns, [times[0]]*len(ns))], "--", label="modèle n²")
plt.xlabel("n"); plt.ylabel("temps (s)"); plt.legend()
plt.title("Courbe de complexité — log-log")
plt.savefig("complexity.png", dpi=120)
print("Graphique enregistré dans complexity.png")

Le script génère un fichier complexity.png où les points mesurés s’alignent presque parfaitement sur la droite théorique de pente 2 (signature de O(n²)). En production, ce diagnostic visuel permet de détecter qu’un endpoint « rapide en dev » dérive en O(n²) sous charge réaliste, avant qu’un client ne s’en plaigne. Si vous mesurez et que la pente n’est pas celle attendue, votre analyse théorique a un trou — c’est le moment de relire le code en cherchant la boucle cachée.

Étape 5 — Le théorème maître pour la récursion diviser-pour-régner

Beaucoup d’algorithmes récursifs satisfont une récurrence du type T(n) = a × T(n/b) + f(n), où a est le nombre d’appels récursifs et b la division de la taille. Le théorème maître (Bentley, Haken, Saxe, 1980 ; formalisation dans CLRS) donne directement la solution selon le rapport entre f(n) et n^(log_b a). Trois cas. Si f(n) = O(n^c) avec c < log_b a, alors T(n) = Θ(n^(log_b a)). Si c = log_b a, alors T(n) = Θ(n^c × log n). Si c > log_b a, alors T(n) = Θ(f(n)).

Trois exemples canoniques. Mergesort : T(n) = 2 × T(n/2) + Θ(n) ; log_2 2 = 1, c = 1, cas 2 → Θ(n log n). Recherche dichotomique : T(n) = T(n/2) + Θ(1) ; log_2 1 = 0, c = 0, cas 2 → Θ(log n). Strassen pour la multiplication matricielle : T(n) = 7 × T(n/2) + Θ(n²) ; log_2 7 ≈ 2.807, c = 2 < 2.807, cas 1 → Θ(n^2.807), ce qui bat le n³ de l’algorithme naïf.

Étape 6 — Mémoïser pour casser la complexité exponentielle

La récursion naïve qui recalcule les mêmes sous-problèmes peut être domptée par mémoïsation : on stocke chaque résultat intermédiaire. C’est le passage de O(2ⁿ) à O(n) pour Fibonacci, et de manière générale la première étape vers la programmation dynamique.

# memo.py
from functools import lru_cache
import time

def fib_naif(n):
    if n < 2: return n
    return fib_naif(n-1) + fib_naif(n-2)

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2: return n
    return fib_memo(n-1) + fib_memo(n-2)

t0 = time.perf_counter(); fib_naif(30); t1 = time.perf_counter()
t2 = time.perf_counter(); fib_memo(30); t3 = time.perf_counter()
print(f"Naif(30) : {t1-t0:.3f}s | Memo(30) : {t3-t2:.6f}s")
print(f"Memo(1000) : {fib_memo(1000)}")

L’exécution affiche un écart de plusieurs ordres de grandeur entre les deux versions sur n=30. La version mémoïsée gère sans peine fib_memo(1000) qui produit un nombre à 209 chiffres, là où la version naïve ne finirait jamais. Le décorateur @lru_cache de la bibliothèque standard est le réflexe à acquérir : il transforme une récursion exponentielle en récursion linéaire en deux lignes de code, sans perdre la lisibilité de la formulation récursive.

Étape 7 — Détecter une régression de complexité dans une CI

Une régression silencieuse de complexité — un développeur ajoute une boucle dans une fonction critique, faisant passer un endpoint de O(n) à O(n²) — est l’un des bugs les plus pernicieux. La meilleure défense est un test de performance qui mesure le ratio de coût entre deux tailles successives et compare à un modèle attendu.

# perf_regression.py
import timeit

def my_function(arr):
    return sorted(arr, reverse=True)

def measure(n):
    arr = list(range(n, 0, -1))
    return timeit.timeit(lambda: my_function(arr), number=10)

t_small = measure(10_000)
t_large = measure(100_000)
ratio = t_large / t_small

# Pour O(n log n), ratio attendu ≈ 10 × (log(100000)/log(10000)) ≈ 12.5
expected = 10 * (5.0/4.0)
assert ratio < expected * 2, f"Régression suspectée — ratio={ratio:.1f}, attendu ≈ {expected:.1f}"
print(f"OK — ratio={ratio:.1f}, attendu ≈ {expected:.1f}")

Le test mesure deux tailles, calcule le ratio, et le compare au ratio théorique. Pour O(n log n), le ratio attendu entre n=100000 et n=10000 est environ 10 × log₁₀(100000) / log₁₀(10000) = 12.5. Si une régression introduit du O(n²), le ratio explose à 100 et le test échoue. Intégrer ce genre d’assertion dans la CI prévient les dégradations qu’aucun test fonctionnel ne détecterait.

Erreurs fréquentes

Tutoriels associés

• Théorie des graphes en pratique : modéliser, BFS, DFS et Dijkstra
• Logique booléenne pour développeurs : tables de vérité, simplification et code

Pour aller plus loin

• 🔝 Retour au guide principal : Mathématiques appliquées à l’informatique : le socle pratique
• Documentation officielle timeit : docs.python.org/3/library/timeit.html
• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS), MIT Press, chapitres 3 et 4 (théorème maître)
• Donald Knuth — Big Omicron and big Omega and big Theta, ACM SIGACT News 8(2), 18-24 (1976)
• Cours MIT 6.006 — Introduction to Algorithms : ocw.mit.edu/courses/6-006

FAQ

Quelle est la différence entre big-O et big-Theta ?

Big-O est une borne supérieure : f(n) = O(g(n)) signifie que f ne grandit pas plus vite que g, à constante près. Big-Theta est un encadrement strict : f(n) = Θ(g(n)) signifie que f grandit exactement comme g à constantes près. En pratique, quand on parle de complexité « en O(n log n) », on entend souvent Θ(n log n).

Pourquoi O(log n) n’a-t-il pas de base ?

Parce que les logarithmes en différentes bases ne diffèrent que par une constante multiplicative (log_a(n) = log_b(n) / log_b(a)), absorbée dans la constante implicite de O. L’usage en informatique est cependant qu’on parle généralement de log₂ par défaut, sauf mention contraire.

Comment estimer la complexité d’une fonction tierce dont je n’ai pas le code ?

Mesurer empiriquement sur plusieurs tailles puis tracer en log-log. La pente donne l’exposant. Pour les bibliothèques sérieuses, la documentation officielle indique généralement la complexité de chaque méthode — c’est même un critère de choix entre bibliothèques.

Une complexité en O(n) est-elle toujours acceptable ?

Pas nécessairement. Pour des opérations à très haute fréquence (gestionnaire d’événements, boucle de jeu, traitement temps réel), O(1) amorti est obligatoire. Pour du batch, O(n log n) est largement acceptable. Le critère pertinent est le temps absolu sur la charge cible, pas la classe asymptotique seule.

Comment gérer les complexités mémoire ?

Même formalisme : on note O(g(n)) la mémoire utilisée par l’algorithme en fonction de l’entrée. Beaucoup d’algorithmes ont un compromis temps/mémoire : la mémoïsation gagne du temps en consommant de la mémoire, le streaming économise la mémoire mais peut complexifier le code. Connaître les deux dimensions est indispensable pour les systèmes contraints.