La complexité algorithmique sert à répondre à une question simple : que se passe-t-il quand la taille des données augmente ? Un programme Python peut sembler rapide avec 10 éléments, puis devenir inutilisable avec 100 000 éléments. La notation Big O permet d’anticiper ce comportement sans mesurer chaque cas possible.
Par exemple, parcourir une liste une seule fois est généralement en O(n). Comparer chaque élément avec tous les autres est souvent en O(n²). Chercher dans un dictionnaire ou un ensemble est en moyenne en O(1). Ces différences ne sont pas théoriques : elles changent directement la performance de vos scripts, de vos algorithmes de tri, de vos graphes et de vos traitements de données.
def contient_lentement(valeurs, cible):
for valeur in valeurs:
if valeur == cible:
return True
return False
def contient_rapidement(valeurs, cible):
ensemble = set(valeurs)
return cible in ensemble
Les deux fonctions peuvent donner le même résultat. Mais leur coût n’évolue pas de la même façon.
La réponse courte
La complexité décrit l’évolution du temps ou de la mémoire quand la taille de l’entrée augmente. On note souvent cette taille n.
| Notation | Idée simple | Exemple Python |
|---|---|---|
O(1) |
coût constant | accès à liste[i], lookup moyen dans dict |
O(log n) |
coût qui grandit très lentement | recherche binaire |
O(n) |
coût proportionnel à la taille | parcourir une liste |
O(n log n) |
souvent lié aux tris efficaces | sorted(liste) |
O(n²) |
deux boucles imbriquées | comparer toutes les paires |
O(2^n) |
explosion combinatoire | explorer tous les sous-ensembles |
Le but n’est pas de calculer une durée exacte. Le but est de comparer les tendances.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)
Plus la taille des données grandit, plus l’écart devient visible.
Pourquoi Big O ignore les petites différences
Big O ne mesure pas les secondes. Il décrit l’ordre de grandeur.
Prenons deux fonctions :
def fonction_a(n):
for i in range(n):
print(i)
def fonction_b(n):
for i in range(n):
print(i)
for i in range(n):
print(i)
fonction_a fait environ n opérations. fonction_b en fait environ 2n. En Big O, les deux sont en O(n), car elles grandissent linéairement.
La constante 2 compte dans la vraie vie, mais elle ne change pas la famille de croissance. Si n double, le coût double aussi.
Même logique ici :
def exemple(n):
for i in range(n):
print(i)
print("fin")
Le print("fin") ajoute un coût constant. On garde O(n), pas O(n + 1).
O(1) : le coût constant
Un algorithme est en O(1) si son coût ne dépend pas de la taille de l’entrée.
def premier_element(valeurs):
return valeurs[0]
Que la liste contienne 10 éléments ou 10 millions, accéder à valeurs[0] reste une opération directe.
Autres exemples courants en Python :
valeurs.append(42) # O(1) amorti
element = valeurs[3] # O(1)
taille = len(valeurs) # O(1)
Les dictionnaires et les ensembles ont aussi des opérations moyennes en O(1) :
ages = {"Ada": 36, "Grace": 85}
print(ages["Ada"]) # O(1) en moyenne
print("Ada" in ages) # O(1) en moyenne
Le mot important est “en moyenne”. Dans des cas pathologiques de collisions, une table de hachage peut se dégrader, mais pour un usage normal en Python, dict et set sont des structures très efficaces.
O(n) : le parcours linéaire
Un algorithme est en O(n) si son coût augmente proportionnellement au nombre d’éléments.
def somme(valeurs):
total = 0
for valeur in valeurs:
total += valeur
return total
Si la liste contient deux fois plus d’éléments, la boucle travaille environ deux fois plus.
La recherche dans une liste est aussi en O(n) dans le cas général.
def contient(valeurs, cible):
for valeur in valeurs:
if valeur == cible:
return True
return False
Même si Python permet d’écrire :
cible in valeurs
cela reste une recherche linéaire si valeurs est une liste.
Pour beaucoup d’articles et de scripts, cette distinction est centrale : x in liste et x in set ne coûtent pas la même chose.
valeurs = list(range(1_000_000))
ensemble = set(valeurs)
999_999 in valeurs # O(n)
999_999 in ensemble # O(1) en moyenne
O(log n) : diviser le problème
O(log n) apparaît souvent quand on divise le problème à chaque étape.
L’exemple classique est la recherche binaire. Elle fonctionne sur une liste triée.
def recherche_binaire(valeurs, cible):
gauche = 0
droite = len(valeurs) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if valeurs[milieu] == cible:
return milieu
if valeurs[milieu] < cible:
gauche = milieu + 1
else:
droite = milieu - 1
return -1
À chaque tour, on élimine environ la moitié des valeurs restantes.
Si une liste contient 1 000 000 d’éléments, une recherche binaire ne parcourt pas 1 000 000 d’éléments. Elle prend environ 20 étapes, car 2^20 vaut un peu plus d’un million.
Python fournit aussi le module bisect pour travailler avec des listes triées.
import bisect
valeurs = [1, 3, 5, 7, 9]
position = bisect.bisect_left(valeurs, 7)
print(position) # 3
Attention : trouver la position est en O(log n), mais insérer dans une liste peut rester en O(n), car il faut décaler des éléments.
O(n log n) : le cas fréquent des tris efficaces
Beaucoup d’algorithmes de tri efficaces sont en O(n log n).
En Python, sorted() et .sort() utilisent Timsort, un algorithme performant qui exploite les portions déjà triées des données.
valeurs = [5, 2, 9, 1, 7]
triees = sorted(valeurs)
print(triees)
Dans le cas général, le tri est souvent résumé comme O(n log n).
Ce coût apparaît aussi dans plusieurs algorithmes qui combinent :
- une étape de tri ;
- une structure de priorité ;
- une stratégie de division ;
- une organisation hiérarchique des données.
Exemple dans les graphes : Dijkstra avec heapq, Prim avec une file de priorité ou Kruskal avec tri des arêtes. Ces sujets ont des détails propres, mais l’idée reste la même : la structure de données influence fortement le coût.
O(n²) : les boucles imbriquées
O(n²) apparaît souvent quand on compare chaque élément avec chaque autre élément.
def afficher_paires(valeurs):
for a in valeurs:
for b in valeurs:
print(a, b)
Si valeurs contient n éléments, la boucle intérieure tourne n fois pour chaque tour de la boucle extérieure. On obtient donc environ n * n opérations.
n = 10 -> 100 paires
n = 100 -> 10 000 paires
n = 1 000 -> 1 000 000 paires
C’est pourquoi un code en O(n²) peut sembler correct en test local, puis devenir très lent en production.
Un exemple concret : chercher des doublons naïvement.
def contient_doublon_lent(valeurs):
for i in range(len(valeurs)):
for j in range(i + 1, len(valeurs)):
if valeurs[i] == valeurs[j]:
return True
return False
On peut faire beaucoup mieux avec un set.
def contient_doublon_rapide(valeurs):
vus = set()
for valeur in valeurs:
if valeur in vus:
return True
vus.add(valeur)
return False
Cette version est en O(n) en moyenne, car chaque lookup dans le set est en moyenne en O(1).
O(2^n) : quand tout explose
Certaines approches explorent toutes les combinaisons possibles. Elles deviennent vite impossibles à utiliser.
def sous_ensembles(valeurs):
if not valeurs:
return [[]]
premier = valeurs[0]
reste = sous_ensembles(valeurs[1:])
return reste + [[premier] + sous for sous in reste]
Pour n éléments, il existe 2^n sous-ensembles.
n = 10 -> 1 024 sous-ensembles
n = 20 -> 1 048 576 sous-ensembles
n = 30 -> plus d'un milliard
Ce type de complexité apparaît dans des problèmes d’optimisation, de recherche exhaustive, de jeux ou de programmation dynamique mal maîtrisée. Le but n’est pas toujours de l’éviter complètement, mais de savoir quand elle devient inacceptable.
Complexité en temps et complexité en mémoire
On parle souvent du temps d’exécution, mais la mémoire compte aussi.
Cette fonction est en O(n) en temps et en O(1) en mémoire supplémentaire :
def somme(valeurs):
total = 0
for valeur in valeurs:
total += valeur
return total
Elle parcourt la liste, mais ne crée pas une nouvelle structure proportionnelle à n.
Cette autre fonction crée une nouvelle liste :
def doubler(valeurs):
return [valeur * 2 for valeur in valeurs]
Elle est en O(n) en temps, mais aussi en O(n) en mémoire supplémentaire, car elle stocke n nouveaux éléments.
Cette distinction est importante quand vous traitez de gros fichiers, des tableaux NumPy, des graphes ou des données issues d’une API.
Les opérations Python à connaître
Voici quelques ordres de grandeur utiles en pratique.
| Opération | Complexité courante |
|---|---|
len(liste) |
O(1) |
liste[i] |
O(1) |
liste.append(x) |
O(1) amorti |
x in liste |
O(n) |
liste.pop() |
O(1) |
liste.pop(0) |
O(n) |
x in set |
O(1) en moyenne |
dict[cle] |
O(1) en moyenne |
sorted(liste) |
O(n log n) |
deque.popleft() |
O(1) |
Le cas de pop(0) est un piège classique.
valeurs = [1, 2, 3, 4]
valeurs.pop(0)
Cette opération retire le premier élément, mais elle doit décaler tous les suivants. Pour une file FIFO, utilisez plutôt deque.
from collections import deque
file = deque([1, 2, 3, 4])
file.popleft() # O(1)
C’est précisément pour cela que BFS s’implémente mieux avec deque qu’avec une liste.
Mesurer ne remplace pas comprendre
La complexité donne une tendance. La mesure donne un résultat sur une machine, une version de Python et un jeu de données.
Pour mesurer proprement un petit morceau de code, Python fournit timeit.
import timeit
temps = timeit.timeit(
"999_999 in valeurs",
setup="valeurs = list(range(1_000_000))",
number=100,
)
print(temps)
On peut comparer avec un ensemble :
temps = timeit.timeit(
"999_999 in valeurs",
setup="valeurs = set(range(1_000_000))",
number=100,
)
print(temps)
La mesure montre l’écart concret. La complexité explique pourquoi cet écart grandit quand la taille augmente.
Comment analyser une fonction Python
Prenons une fonction simple.
def trouver_maximum(valeurs):
maximum = valeurs[0]
for valeur in valeurs:
if valeur > maximum:
maximum = valeur
return maximum
Étapes d’analyse :
maximum = valeurs[0]coûteO(1).- La boucle parcourt
néléments. - Le test
valeur > maximumest constant. - La fonction est donc en
O(n).
Autre exemple :
def toutes_les_paires(valeurs):
paires = []
for i in range(len(valeurs)):
for j in range(i + 1, len(valeurs)):
paires.append((valeurs[i], valeurs[j]))
return paires
Il y a deux boucles imbriquées, mais la deuxième ne parcourt pas toujours n éléments. Malgré cela, l’ordre de grandeur reste O(n²), car le nombre de paires croît comme n * (n - 1) / 2.
Les erreurs fréquentes
Croire qu’une ligne Python est toujours en O(1)
Une ligne courte peut cacher une boucle.
if cible in valeurs:
...
Si valeurs est une liste, cette ligne peut parcourir toute la liste. Si valeurs est un set, le coût moyen est très différent.
Optimiser trop tôt
La complexité aide à éviter les mauvais choix évidents. Elle ne signifie pas qu’il faut rendre chaque fonction plus compliquée.
Pour 20 éléments, une solution simple en O(n²) peut être largement suffisante. Pour 2 millions d’éléments, elle ne l’est probablement pas.
Le bon réflexe :
- écrire une solution correcte ;
- identifier la taille probable des données ;
- analyser l’ordre de grandeur ;
- mesurer si nécessaire ;
- optimiser le vrai goulot d’étranglement.
Confondre pire cas, meilleur cas et cas moyen
Une recherche dans une liste peut s’arrêter au premier élément.
def contient(valeurs, cible):
for valeur in valeurs:
if valeur == cible:
return True
return False
Meilleur cas : la cible est au début, coût proche de O(1).
Pire cas : la cible est absente ou à la fin, coût O(n).
En complexité, on parle souvent du pire cas, sauf précision contraire.
Oublier le coût de construction d’une structure
Transformer une liste en set coûte O(n).
ensemble = set(valeurs)
Ensuite, les recherches sont rapides. Ce choix est rentable si vous effectuez plusieurs recherches.
ensemble = set(valeurs)
for cible in nombreuses_cibles:
if cible in ensemble:
...
Mais pour une seule recherche, construire le set peut être inutile.
Mini-exercices
Essayez de deviner la complexité avant de lire la réponse.
Exercice 1
def afficher(valeurs):
for valeur in valeurs:
print(valeur)
Réponse : O(n).
Exercice 2
def premier(valeurs):
return valeurs[0]
Réponse : O(1).
Exercice 3
def comparer(valeurs):
for a in valeurs:
for b in valeurs:
print(a, b)
Réponse : O(n²).
Exercice 4
def chercher(valeurs, cible):
gauche = 0
droite = len(valeurs) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if valeurs[milieu] == cible:
return True
if valeurs[milieu] < cible:
gauche = milieu + 1
else:
droite = milieu - 1
return False
Réponse : O(log n), si la liste est déjà triée.
Le réflexe à garder
Quand vous lisez ou écrivez un algorithme Python, posez trois questions :
- Combien d’éléments sont parcourus ?
- Y a-t-il une boucle dans une boucle ?
- Les structures utilisées sont-elles adaptées : liste, set, dict, deque, heap ?
Ces trois questions suffisent déjà à éviter beaucoup de problèmes de performance.
La complexité algorithmique n’est pas une formule abstraite réservée aux cours d’informatique. C’est une grille de lecture pratique pour choisir entre deux implémentations, comprendre pourquoi un script ralentit, ou décider quand utiliser une structure plus adaptée.
Pour aller plus loin
Ce guide complète plusieurs articles du site :
- le tri à bulles en Python, utile pour comprendre un algorithme simple mais coûteux ;
- Dijkstra en Python, où la file de priorité change fortement la performance ;
- Prim vs Kruskal en Python, pour comparer deux stratégies de graphe ;
- les algorithmes de graphes en Python, pour replacer BFS, DFS, Dijkstra, Prim et Kruskal dans un parcours complet ;
- la méthode de Monte Carlo en Python, où le nombre d’itérations détermine directement le coût.
Références
- Documentation Python –
timeit - Documentation Python –
collections.deque - Documentation Python –
bisect - Python Wiki – TimeComplexity
