Complexité algorithmique

Pourquoi un programme rapide sur 100 éléments peut mettre 10 minutes sur 100 000 ? La réponse est la complexité algorithmique — comment le temps de calcul grandit avec la taille des données. Le TOSA Avancé teste cette compétence parce qu'elle sépare ceux qui écrivent du code qui marche de ceux qui écrivent du code qui tient la charge.

Pourquoi la complexité ?

Deux algorithmes peuvent résoudre le même problème, mais avec des performances radicalement différentes. Regardons un exemple concret : chercher si un élément est dans une collection.

Version 1 — recherche dans une liste

import time

# Liste de 100 000 éléments
grande_liste = list(range(100_000))

debut = time.time()
for _ in range(1000):         # on fait 1000 recherches
    _ = 99_999 in grande_liste
duree = time.time() - debut
print(f"Recherche dans une liste : {duree*1000:.0f} ms")

Version 2 — même chose avec un set

import time

grand_set = set(range(100_000))

debut = time.time()
for _ in range(1000):
    _ = 99_999 in grand_set
duree = time.time() - debut
print(f"Recherche dans un set : {duree*1000:.2f} ms")

Le set est des milliers de fois plus rapide pour cette opération. Pourquoi ? Parce que leurs complexités sont différentes. Comprendre ça change la façon d'écrire du code.

La notation Big O

La notation Big O exprime comment le temps (ou la mémoire) d'un algorithme grandit en fonction de la taille n des données.

On ignore les constantes et les termes de moindre ordre — on s'intéresse à l'ordre de grandeur.

Les complexités les plus courantes

Illustration concrète des ordres

Pour n = 1_000_000 (un million d'éléments), voici les durées approximatives (opérations élémentaires à 10⁹/s) :

La leçon : les algorithmes O(n²) deviennent insupportables à partir de quelques dizaines de milliers d'éléments.

O(1) — complexité constante

Le temps d'exécution ne dépend pas de la taille des données.

d = {f"clé_{i}": i for i in range(1_000_000)}

# Accès à un élément : O(1) — aussi rapide que pour 10 éléments
print(d["clé_500000"])

# Test d'appartenance : O(1)
print("clé_500000" in d)

Exemples d'opérations O(1) :

• d[clé], d[clé] = v (dict)
• x in set, set.add(x), set.remove(x)
• liste[i] (accès par indice)
• liste.append(x), liste.pop() (fin de liste)
• len(collection)

O(n) — complexité linéaire

Le temps est proportionnel à la taille des données.

liste = list(range(1_000_000))

# Parcourir : O(n)
total = 0
for x in liste:
    total += x

# Rechercher un élément dans une liste : O(n)
print(999_999 in liste)

# sum, max, min : O(n)
print(sum(liste))

Exemples d'opérations O(n) :

• x in liste ou x in chaîne
• Boucle simple sur toute la collection
• sum, min, max, len sur un générateur
• liste.copy(), list(iterable)
• liste.insert(0, x) — insertion au début (tout décaler !)

Piège des listes : in et insert(0)

O(n²) — complexité quadratique

Le temps grandit au carré de la taille. Typique des boucles imbriquées sur les mêmes données.

# Trouver tous les doublons dans une liste : approche naïve O(n²)
def doublons_naif(liste):
    doublons = []
    for i, a in enumerate(liste):
        for j, b in enumerate(liste):
            if i < j and a == b and a not in doublons:
                doublons.append(a)
    return doublons

print(doublons_naif([1, 2, 3, 1, 4, 2, 5]))

Pour n = 10_000, on fait déjà 100 millions de comparaisons.

Comment éviter O(n²) ?

Utiliser un set pour détecter les doublons en O(n) :

def doublons_efficace(liste):
    vus = set()
    doublons = set()
    for x in liste:
        if x in vus:
            doublons.add(x)
        vus.add(x)
    return list(doublons)

print(doublons_efficace([1, 2, 3, 1, 4, 2, 5]))

Chaque x in vus est O(1), donc l'ensemble du code est O(n) — linéairement plus rapide.