backend / algorithmes-structures-donnees
Complexité et notation Big O
Explication
Un peu d'histoire
Le mot "algorithme" vient du nom du mathématicien perse Al-Khwârizmî, qui a vécu au IXe siècle et dont les travaux sur le calcul ont été traduits et diffusés en Europe des siècles plus tard. L'étude formelle des algorithmes et des structures de données, elle, se développe surtout au XXe siècle avec les travaux d'Alan Turing sur le calcul, puis se systématise véritablement à partir de 1968 avec Donald Knuth et sa série de référence "The Art of Computer Programming", encore citée aujourd'hui.
Pourquoi apprendre les algorithmes et structures de données aujourd'hui
Ce n'est pas qu'un sujet d'entretien d'embauche (même si c'est effectivement une étape classique du recrutement dans beaucoup de grandes entreprises tech) : comprendre la complexité d'un algorithme et choisir la bonne structure de données, c'est ce qui fait qu'un programme reste rapide avec 100 utilisateurs ET avec 100 millions d'utilisateurs. C'est aussi ce qui permet de mieux comprendre ce qui se passe "sous le capot" des outils qu'on utilise tous les jours : un index de base de données, un moteur de recherche, un GPS qui calcule un itinéraire.
Ce que vous allez apprendre
- Lire et écrire la complexité d'un algorithme en notation Big O (O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), O(n!))
- Distinguer la complexité en temps de la complexité en espace
- Différencier meilleur cas, pire cas et cas moyen, et comprendre pourquoi le pire cas guide les décisions en production
- Repérer dans du code les opérations « cachées » qui coûtent plus cher qu'il n'y paraît (recherche dans une liste, concaténation de chaînes en boucle)
- Comparer deux algorithmes entre eux à partir de leur seule complexité, sans avoir besoin de les exécuter
Dans quel contexte ?
Une candidate passe un entretien technique chez une entreprise tech et doit trouver, dans un tableau de 50 000 entiers, tous les couples dont la somme atteint une valeur cible. Sa première solution, avec deux boucles imbriquées, passe les 5 exemples fournis dans l'énoncé... puis dépasse le temps limite sur le jeu de test réel de l'évaluateur automatique. Ce n'est pas un bug : c'est du O(n²) qui devient injouable dès que n grandit. Savoir dire « c'est O(n²), il existe une solution en O(n) avec une table de hachage » est exactement ce qui sépare une réponse qui passe l'entretien d'une réponse qui échoue au dernier test.
D'abord, la question que tout algorithme doit affronter
Avant d'écrire le moindre algorithme, il faut pouvoir répondre à une question simple : si mon jeu de données double, mon programme met-il deux fois plus de temps, quatre fois plus, ou reste-t-il quasiment aussi rapide ? La notation Big O est le langage qui répond à cette question sans dépendre de la machine, du langage ou de l'humeur du processeur ce jour-là.
Étape 1 : ignorer la vitesse absolue, regarder la croissance
Deux algorithmes peuvent mettre le même temps sur 100 éléments et diverger radicalement sur 100 000. Big O décrit comment le temps croît quand la taille de l'entrée grandit, en ignorant les constantes et les détails d'implémentation.
| Taille de n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 |
| 1 000 | 10 | 1 000 | 9 966 | 1 000 000 |
| 1 000 000 | 20 | 1 000 000 | 19 931 569 | 1 000 000 000 000 |
Ce tableau montre concrètement pourquoi la croissance compte plus que la vitesse brute : un algorithme en O(n²) devient impraticable bien avant le million d'éléments, alors qu'un O(n log n) reste parfaitement gérable.
Une conséquence contre-intuitive
Un algorithme en O(n) qui fait 1000 opérations par élément reste, asymptotiquement, plus rapide qu'un O(n²), dès que n devient assez grand — même s'il est plus lent au tout début, sur de petites entrées. C'est la croissance qui compte, pas le point de départ.
Astuce
Pour estimer rapidement la complexité d'un bout de code : une boucle simple sur n éléments = O(n), deux boucles imbriquées sur la même donnée = O(n²), une boucle qui divise la taille du problème par 2 à chaque tour = O(log n). Compter les boucles imbriquées suffit souvent à une première estimation fiable.
Étape 2 : pourquoi le pire cas domine les décisions
Un algorithme peut être rapide "en général" et catastrophique sur une entrée précise, comme un tableau déjà trié pour certains tris. En production, on ne choisit pas ses données : c'est pourquoi les ingénieurs raisonnent presque toujours en pire cas, quitte à mentionner le cas moyen comme argument secondaire.
Le piège classique à repérer
Beaucoup de bugs de performance ne viennent pas d'un mauvais algorithme mais d'une opération qu'on croit gratuite et qui ne l'est pas, comme une recherche dans une liste ou une concaténation de chaînes en boucle.
Piège fréquent
element in ma_liste est en O(n) sur une liste Python, mais en O(1) en moyenne sur un set ou les clés d'un dict. Remplacer une liste par un set dans une boucle qui teste l'appartenance des milliers de fois transforme souvent un programme de O(n²) en O(n), sans changer la moindre ligne de logique métier.
La compétence qui sous-tend tout ce cours
Savoir lire la complexité d'un bout de code, boucle par boucle, est la compétence qui sous-tend absolument tout le reste de ce cours : chaque structure et chaque algorithme que vous allez apprendre existe pour améliorer une complexité précise.
Vers la suite
Une fois qu'on sait mesurer la vitesse d'un algorithme, l'étape suivante consiste à choisir la bonne structure pour stocker les données elles-mêmes — le sujet de la prochaine leçon, sur les tableaux et les listes chaînées.
Commandes & code
Complexité et notation Big O
# O(1) -- temps constant : indépendant de la taille de l'entrée
def premier_element(tableau: list) -> int:
return tableau[0]
# O(n) -- temps linéaire : proportionnel à la taille de l'entrée
def somme(tableau: list[int]) -> int:
total = 0
for x in tableau: # une boucle simple sur n éléments
total += x
return total
# O(n^2) -- temps quadratique : boucle imbriquée sur la même donnée
def contient_doublon_naif(tableau: list) -> bool:
n = len(tableau)
for i in range(n):
for j in range(i + 1, n): # pour chaque i, on reparcourt le reste -> n*(n-1)/2 comparaisons
if tableau[i] == tableau[j]:
return True
return False
# O(log n) -- temps logarithmique : on divise le problème par 2 à chaque étape
def recherche_binaire(tableau: list[int], cible: int) -> int:
gauche, droite = 0, len(tableau) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if tableau[milieu] == cible:
return milieu
elif tableau[milieu] < cible:
gauche = milieu + 1
else:
droite = milieu - 1
return -1
# O(n log n) -- le tri par fusion/rapide, la classe des tris comparatifs optimaux
def tri_fusion(tableau: list[int]) -> list[int]:
if len(tableau) <= 1:
return tableau
milieu = len(tableau) // 2
gauche = tri_fusion(tableau[:milieu])
droite = tri_fusion(tableau[milieu:])
return _fusionner(gauche, droite)
def _fusionner(a: list[int], b: list[int]) -> list[int]:
resultat = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
resultat.append(a[i]); i += 1
else:
resultat.append(b[j]); j += 1
resultat.extend(a[i:]); resultat.extend(b[j:])
return resultat
# O(2^n) -- temps exponentiel : Fibonacci récursif naïf (chaque appel en génère 2)
def fib_naif(n: int) -> int:
if n <= 1:
return n
return fib_naif(n - 1) + fib_naif(n - 2) # explose très vite pour n > 35
# O(n!) -- factoriel : générer toutes les permutations d'un tableau
def permutations(tableau: list) -> list[list]:
if len(tableau) <= 1:
return [tableau]
resultat = []
for i in range(len(tableau)):
reste = tableau[:i] + tableau[i+1:]
for p in permutations(reste):
resultat.append([tableau[i]] + p)
return resultat
# Meilleur / pire / moyen cas -- exemple avec la recherche linéaire
def recherche_lineaire(tableau: list, cible) -> int:
# meilleur cas O(1) : cible en tableau[0]
# pire cas O(n) : cible absente ou en dernière position
# cas moyen O(n) : en moyenne on parcourt n/2 éléments
for i, valeur in enumerate(tableau):
if valeur == cible:
return i
return -1
# Complexité en espace (space complexity) : mémoire additionnelle utilisée
def inverser_en_place(tableau: list) -> None:
# O(1) en espace : pas de structure additionnelle, on échange les éléments sur place
gauche, droite = 0, len(tableau) - 1
while gauche < droite:
tableau[gauche], tableau[droite] = tableau[droite], tableau[gauche]
gauche += 1; droite -= 1
def inverser_nouvelle_liste(tableau: list) -> list:
# O(n) en espace : crée une nouvelle liste de même taille
return tableau[::-1]| Notation | Nom | Exemple |
|---|---|---|
| O(1) | Constant | accès tableau par index |
| O(log n) | Logarithmique | recherche binaire |
| O(n) | Linéaire | parcours simple |
| O(n log n) | Quasi-linéaire | tri fusion, tri rapide (moyen) |
| O(n^2) | Quadratique | boucles imbriquées, tri à bulles |
| O(2^n) | Exponentiel | Fibonacci récursif naïf |
| O(n!) | Factoriel | génération de permutations |
Résumé
- Big O décrit la croissance asymptotique du temps/espace, pas la vitesse réelle sur une entrée donnée.
- Toujours distinguer meilleur cas, pire cas et cas moyen : le pire cas guide les décisions en production.
- La complexité en espace compte autant que la complexité en temps (structures additionnelles, pile de récursion).
Exercices pratiques
Mission : sauver l'algorithme qui dépasse le temps limite
Objectif : Diagnostiquer pourquoi une solution O(n²) échoue à l'échelle, puis la réécrire avec une complexité inférieure.
Contexte
Une candidate a rendu une fonction qui, pour un tableau de n entiers, cherche s'il existe deux indices différents dont les valeurs sont égales (un doublon). Sa version utilise deux boucles imbriquées et passe tous les petits exemples de l'énoncé, mais l'évaluateur automatique la rejette pour dépassement de temps sur un tableau de 50 000 éléments.
Tu dois comprendre pourquoi cette solution s'effondre à grande échelle, puis produire une version qui reste rapide même avec des millions d'éléments.