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.
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.
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")Recherche dans une liste : 497 msimport 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")Recherche dans un set : 0.00 msLe 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 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.
| Notation | Nom | Exemple |
|---|---|---|
| O(1) | Constant | Accès à liste[i], dict[clé], x in set |
| O(log n) | Logarithmique | Recherche dichotomique |
| O(n) | Linéaire | Parcourir une liste, x in liste |
| O(n log n) | Linéarithmique | Tri efficace (sorted) |
| O(n²) | Quadratique | Boucles imbriquées, tri à bulles |
| O(2ⁿ) | Exponentielle | Sous-ensembles, certains problèmes combinatoires |
| O(n!) | Factorielle | Permutations complètes |
Pour n = 1_000_000 (un million d’éléments), voici les durées approximatives (opérations élémentaires à 10⁹/s) :
| Complexité | Opérations | Durée estimée |
|---|---|---|
| O(1) | 1 | instantané |
| O(log n) | 20 | instantané |
| O(n) | 10⁶ | 1 ms |
| O(n log n) | 2×10⁷ | 20 ms |
| O(n²) | 10¹² | 15 minutes |
| O(2ⁿ) | 10³⁰¹⁰³⁰ | bien au-delà de l’âge de l’univers |
La leçon : les algorithmes O(n²) deviennent insupportables à partir de quelques dizaines de milliers d’éléments.
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)500000
TrueExemples 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)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))True
499999500000Exemples d’opérations O(n) :
x in liste ou x in chaînesum, min, max, len sur un générateurliste.copy(), list(iterable)liste.insert(0, x) — insertion au début (tout décaler !)in et insert(0)Certaines opérations sur les listes semblent simples mais sont O(n) :
x in liste : doit parcourir toute la liste.liste.insert(0, x) : doit décaler tous les éléments.del liste[0] : idem, décalage coûteux.Pour ces cas, utilisez collections.deque (file à deux bouts, O(1) aux deux extrémités) :
from collections import deque
d = deque([1, 2, 3])
d.appendleft(0) # O(1) — pas de décalage !
print(d)deque([0, 1, 2, 3])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]))[1, 2]Pour n = 10_000, on fait déjà 100 millions de comparaisons.
Typique des algorithmes qui divisent le problème par 2 à chaque étape.
Sur une liste triée de 1 million d’éléments, 20 itérations suffisent (log₂(1_000_000) ≈ 20).
def dicho(liste_triee, cible):
gauche, droite = 0, len(liste_triee) - 1
iterations = 0
while gauche <= droite:
iterations += 1
milieu = (gauche + droite) // 2
if liste_triee[milieu] == cible:
return milieu, iterations
elif liste_triee[milieu] < cible:
gauche = milieu + 1
else:
droite = milieu - 1
return -1, iterations
# Sur un million d'éléments
grande = list(range(1_000_000))
indice, iters = dicho(grande, 999_999)
print(f"Trouvé en {iters} itérations (sur {len(grande)} éléments)")Trouvé en 20 itérations (sur 1000000 éléments)C’est la complexité des algorithmes de tri efficaces comme Timsort (celui de Python).
import random
random.seed(42)
liste = [random.randint(1, 1000) for _ in range(100_000)]
import time
debut = time.time()
trie = sorted(liste)
duree = time.time() - debut
print(f"Tri de {len(liste):,} éléments en {duree*1000:.0f} ms")Tri de 100,000 éléments en 11 msC’est beaucoup plus rapide qu’un tri à bulles (O(n²)) qui prendrait des minutes sur la même liste.
Tableau à connaître pour le TOSA :
| Opération | Complexité |
|---|---|
liste[i] (accès) |
O(1) |
liste[i] = x |
O(1) |
liste.append(x) |
O(1) amorti |
liste.pop() (fin) |
O(1) |
liste.insert(0, x) |
O(n) |
liste.pop(0) |
O(n) |
x in liste |
O(n) |
liste.sort() / sorted(liste) |
O(n log n) |
liste + autre |
O(n+m) |
len(liste) |
O(1) |
| Opération | Complexité |
|---|---|
x in set, x in dict |
O(1) |
set.add(x), dict[k] = v |
O(1) |
set.remove(x), del dict[k] |
O(1) |
| Parcours complet | O(n) |
len |
O(1) |
| Opération | Complexité |
|---|---|
chaine[i] |
O(1) |
c in chaine (sous-chaîne de taille m) |
O(n·m) |
chaine1 + chaine2 |
O(n+m) |
".".join(liste) |
O(n) |
len(chaine) |
O(1) |
in, insert(0), pop(0)).Prenons un problème : compter combien d’éléments de la liste A sont aussi dans la liste B.
import time
a = list(range(10_000))
b = list(range(5_000, 15_000))
debut = time.time()
communs = 0
for x in a:
if x in b: # chaque test : O(m) dans une liste
communs += 1
duree = time.time() - debut
print(f"Version naïve : {communs} communs en {duree*1000:.0f} ms")Version naïve : 5000 communs en 304 msPour chaque élément de a (n), on parcourt b (m) → complexité O(n×m).
import time
a = list(range(10_000))
b = list(range(5_000, 15_000))
debut = time.time()
b_set = set(b) # conversion : O(m)
communs = 0
for x in a:
if x in b_set: # test : O(1)
communs += 1
duree = time.time() - debut
print(f"Version optimisée : {communs} communs en {duree*1000:.0f} ms")Version optimisée : 5000 communs en 1 msOn convertit b en set une seule fois, puis chaque test d’appartenance est O(1). Total : O(n+m) — gain énorme !
a = list(range(10_000))
b = list(range(5_000, 15_000))
communs = len(set(a) & set(b))
print(f"Version ensembliste : {communs} communs")Version ensembliste : 5000 communsdef exemple(liste):
# O(n)
for x in liste:
print(x)
# O(n log n)
liste.sort()
# Total : max(O(n), O(n log n)) = O(n log n)def exemple2(liste):
# O(n²) — boucles imbriquées
for i in liste:
for j in liste:
print(i, j)Une règle utile :
for sur n éléments = O(n) (s’il ne contient que des opérations O(1)).for imbriqués sur n éléments = O(n²).while qui divise par 2) = O(log n).Vous pouvez l’ignorer si :
Vous devez y faire attention si :
Le fameux adage : « Premature optimization is the root of all evil » (Knuth).
Écrivez d’abord du code clair qui marche. Mesurez si c’est trop lent. Ensuite optimisez, en commençant par les goulots d’étranglement.
time ou timeittime.time() (simple)import time
debut = time.time()
total = sum(range(1_000_000))
duree = time.time() - debut
print(f"Durée : {duree*1000:.2f} ms")Durée : 11.02 mstimeit (plus précis)Le module timeit répète l’opération et renvoie la durée moyenne — plus fiable.
import timeit
duree = timeit.timeit(
"sum(range(1000))",
number=10_000 # on répète 10_000 fois
)
print(f"Durée moyenne : {duree/10_000*1e6:.2f} µs par appel")Durée moyenne : 8.36 µs par appelQuelle est la complexité de x in liste (liste Python classique) ?
c) O(n) — Python doit parcourir la liste dans le pire cas. Pour des recherches fréquentes, convertir en set donne O(1).
Quelle est la complexité de x in set ?
a) O(1) — les sets utilisent une table de hachage, l’accès est (en moyenne) instantané. C’est l’atout principal des sets et dicts.
Combien d’opérations pour trier 1 million d’éléments avec sorted() ?
b) ~20 millions — Timsort est en O(n log n) = 10⁶ × log₂(10⁶) ≈ 10⁶ × 20. Sur une machine moderne, cela prend quelques centaines de millisecondes.
Quelle est la complexité de cette fonction ?
def f(liste):
for x in liste:
for y in liste:
print(x, y)c) O(n²) — boucles imbriquées sur la même taille. Pour n = 10_000, on fait 100 millions de print. À éviter pour de grandes données.
Que préférer pour vérifier si un élément existe souvent dans une collection ?
c) Un set — recherche O(1) au lieu de O(n). Astuce classique : s = set(liste) avant de faire beaucoup de x in s.
Quelle opération est O(n) sur une liste Python ?
liste[i] (accès)liste.append(x)liste.insert(0, x)len(liste)c) liste.insert(0, x) — insérer au début nécessite de décaler tous les éléments (O(n)). Préférez collections.deque ou appendleft si vous insérez beaucoup au début.
Combien d’itérations pour une recherche dichotomique dans 1024 éléments ?
b) 10 — log₂(1024) = 10. Chaque itération divise la plage par 2. La dichotomie est extrêmement rapide.
Si un algorithme en O(n²) met 1 seconde pour 10 000 éléments, combien pour 100 000 ?
b) 100 secondes — l’entrée est multipliée par 10, le temps par 10² = 100. C’est pourquoi O(n²) est vite insupportable.
On veut savoir combien de valeurs de liste_a sont dans liste_b. Voici une version naïve :
def compter_communs_naif(liste_a, liste_b):
compteur = 0
for x in liste_a:
if x in liste_b:
compteur += 1
return compteura = b = list(range(10_000)).import time
def compter_communs_naif(a, b):
compteur = 0
for x in a:
if x in b:
compteur += 1
return compteur
def compter_communs_opti(a, b):
...
# Benchmark
a = list(range(10_000))
b = list(range(5_000, 15_000))
# Mesurer les deux versionsimport time
def compter_communs_naif(a, b):
compteur = 0
for x in a:
if x in b: # O(m) à chaque itération
compteur += 1
return compteur
def compter_communs_opti(a, b):
b_set = set(b) # O(m) une seule fois
compteur = 0
for x in a:
if x in b_set: # O(1) !
compteur += 1
return compteur
# Benchmark — on utilise perf_counter() (précision µs)
# plutôt que time.time() (résolution ~15 ms sur Windows)
a = list(range(10_000))
b = list(range(5_000, 15_000))
debut = time.perf_counter()
r1 = compter_communs_naif(a, b)
t1 = time.perf_counter() - debut
debut = time.perf_counter()
r2 = compter_communs_opti(a, b)
t2 = time.perf_counter() - debut
print(f"Version naïve : {r1} en {t1*1000:.1f} ms")
print(f"Version optimisée : {r2} en {t2*1000:.3f} ms")
print(f"Gain : {t1/t2:.0f}× plus rapide")Version naïve : 5000 en 313.2 ms
Version optimisée : 5000 en 0.400 ms
Gain : 783× plus rapideComplexités :
a, on parcourt b.a = list(range(10_000))
b = list(range(5_000, 15_000))
r = len(set(a) & set(b))
print(f"Intersection : {r}")Intersection : 5000Pour chacun de ces codes, donnez la complexité en fonction de n = len(liste).
# Code 1
def f1(liste):
total = 0
for x in liste:
total += x
return total
# Code 2
def f2(liste):
for x in liste:
for y in liste:
print(x, y)
# Code 3
def f3(liste):
return sorted(liste)
# Code 4
def f4(liste):
return liste[0]
# Code 5
def f5(liste):
i = 0
while i < len(liste):
i *= 2 if i else 1
i += 1
return iCode 1 : O(n) — une boucle sur liste.
Code 2 : O(n²) — deux boucles imbriquées, chacune de n itérations → n × n.
Code 3 : O(n log n) — sorted utilise Timsort.
Code 4 : O(1) — accès par indice, ne dépend pas de la taille.
Code 5 : O(log n) — i double à chaque itération, donc on atteint n en environ log₂(n) étapes.
Comparez empiriquement les temps de ces 3 approches pour dédupliquer une liste :
if x not in resultat.set(liste).dict.fromkeys(liste) (préserve l’ordre).import time
import random
random.seed(42)
liste = [random.randint(1, 1000) for _ in range(50_000)]
# Version 1 : boucle naïve
def dedup_naif(l):
resultat = []
for x in l:
if x not in resultat:
resultat.append(x)
return resultat
# Version 2 : set
def dedup_set(l):
return list(set(l))
# Version 3 : dict.fromkeys (ordre préservé)
def dedup_dict(l):
return list(dict.fromkeys(l))
# Mesurer chacuneimport time
import random
random.seed(42)
liste = [random.randint(1, 1000) for _ in range(50_000)]
def dedup_naif(l):
resultat = []
for x in l:
if x not in resultat:
resultat.append(x)
return resultat
def dedup_set(l):
return list(set(l))
def dedup_dict(l):
return list(dict.fromkeys(l))
for fonction in [dedup_naif, dedup_set, dedup_dict]:
debut = time.time()
r = fonction(liste)
duree = time.time() - debut
print(f"{fonction.__name__:<12} : {duree*1000:>7.1f} ms, taille résultat = {len(r)}")dedup_naif : 115.0 ms, taille résultat = 1000
dedup_set : 0.0 ms, taille résultat = 1000
dedup_dict : 1.5 ms, taille résultat = 1000Analyse :
dedup_naif : O(n²) — x not in resultat est O(n), multiplié par n éléments.dedup_set : O(n) — construction du set en O(n), mais l’ordre n’est pas préservé.dedup_dict : O(n) — construction du dict en O(n), l’ordre est préservé.Leçon : sur de grosses listes, dedup_naif devient ingérable. Toujours préférer set ou dict.fromkeys selon qu’on veut l’ordre ou non.
in.insert(0) et pop(0) sur liste sont O(n). Utilisez deque pour des insertions/suppressions en début.timeit avant d’optimiser — ne spéculez pas.← Chapitre précédent : pip et l’écosystème • Chapitre suivant : Pattern matching →
Comment éviter O(n²) ?
Utiliser un set pour détecter les doublons en O(n) :
Chaque
x in vusest O(1), donc l’ensemble du code est O(n) — linéairement plus rapide.