Les Taux De Croissance, Pas Les Coûts Absolus
O: Mesurer La Vitesse À Laquelle Les Coûts Croissent
La notation O mesure le taux de croissance du coût de l'algorithme — pas le coût absolu.
La question que répond O : à mesure que la taille de l'entrée N double, le travail double ? Quadruple ? Reste plat ?
Le 'O' signifie 'ordre de grandeur'. L'expression à l'intérieur des parenthèses décrit la forme de la courbe de croissance.
ClasseS De Complexité Clé :
- O(1) — constant : le coût ne croît pas. Exemple : rechercher une valeur par index dans un tableau. Que le tableau ait 10 éléments ou 10 millions, une recherche reste une recherche.
- O(N) — linéaire : le coût croît avec l'entrée. Exemple : lire chaque élément d'une liste une fois. Doublons la liste, doublons les lectures.
- O(N²) — quadratique : le coût croît en fonction du carré de l'entrée. Exemple : comparer chaque élément à chaque autre élément. Double N, quadruple le travail.
Tableau De Comparaison De La Croissance :
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
À N = 10, la différence semble petite. À N = 1,000, l'écart devient immense.
Comparer O(N) À O(N²)
Utilisez le tableau de comparaison de la croissance ci-dessus.
À N = 1,000 : O(N) nécessite 1,000 opérations. O(N²) nécessite 1,000,000 opérations.
Comment la structure du code révèle la complexité
Comment identifier Big O à partir du code
Big O se cache dans la forme de votre code. Quatre modèles couvrent la plupart des cas :
Boucle unique parcourant N éléments : O(N)
# O(N) : une passe à travers la liste
for item in list_of_n_items:
process(item)Boucles imbriquées, chacune parcourant N éléments : O(N²)
# O(N²) : chaque élément est associé à chaque autre élément
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Requête en temps constant : O(1)
Accès à un index d'ensemble, recherche dans un tableau hash — une étape indépendamment de la taille.
Diviser pour conquérir (couper le problème en deux à chaque étape) : O(log N)
Recherche binaire : chaque vérification divise les éléments restants par deux.
---
Big O caché : une liste à l'intérieur d'une boucle
# Ceci a l'air de O(N) mais il s'agit en réalité de O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # scanne tous les éléments de visited : O(N)
visited.append(item) # la boucle entière : O(N²)La ligne if item not in visited effectue un scan de chaque élément de visited à chaque itération. Un scan de liste coûte O(N). Une boucle qui s'exécute N fois, chaque fois faisant O(N) de travail : O(N) × O(N) = O(N²).
Ce modèle apparaît dans plus de 1 000 projets open source. La solution nécessite une seule caractère : remplacer visited = [] par visited = set(). L'examen de l'appartenance à un ensemble coûte O(1) et non O(N). Une seule modification. Mêmes résultats. 1 000× plus rapide à N = 1 000.
Classifiez et corrigez ce code
Lisez ce code :
result = []
for name in student_names:
if name not in result:
result.append(name)Théorie et pratique
Big O dans la nature
Big O n'est pas seulement de la théorie. Elle sépare les programmes qui se terminent en quelques secondes de ceux qui prennent 17 minutes - sur la même tâche exacte.
Exemple réel : détection de cycles de dépendances dans un système de build.
Lorsque vous installez du logiciel, votre ordinateur résout un graphe des dépendances : paquet A a besoin de B, B a besoin de C, et ainsi de suite. Un système de build vérifie ce graphe pour y trouver des cycles.
Un algorithme de détection de cycles en O(N²) fonctionne parfaitement à N = 100 paquets. À N = 50 000 paquets (un projet réel) : cela prend 17 minutes. La solution en O(N) : 10 secondes.
Cette défectuosité exacte existe dans GHC (compilateur Haskell), pip (gestionnaire de packages Python), Maven (système de build Java), Cargo (gestionnaire de packages Rust) et dans + de 1 000 autres projets.
Pas parce que leurs auteurs étaient négligents. visited = [] a été écrit lorsque N était petit. Le code a calcifié. N a augmenté. Personne ne s'en est aperçu jusqu'à ce que la build prenne la moitié d'une heure.
Big O est le vocabulaire qui vous permet de nommer ce qui s'est produit - et de le corriger.
---
Souhaitez-vous aller plus loin ? Notre cours Unhamming inclut un chapitre complet sur Big O, MOAD-0001 (une véritable défaillance O(N²) trouvée dans 1 000 projets open-source), et pourquoi nommer un modèle vous permet de le trouver partout. Voir [Le chapitre manquant : Complexité algorithmique](/fr/un/unhamming_algorithmic_complexity).
Prédisez les temps de build
Un système de build utilise la détection de cycles en O(N²).
Temps de build mesurés :
- N = 100 paquets : 0,01 secondes
- N = 1 000 paquets : 1 seconde
Pour O(N²) : le temps varie en (N_new / N_old)².
Pour O(N) : le temps varie en (N_new / N_old).