Un langage commun pour dire comment un algorithme grandit quand les données grandissent.
⏱️ Durée : environ 70 minutes · 🎓 Niveau : débutant · 🏅 Badge : Lecteur de courbes
🎬 L'histoire
Kodi compare deux solutions : l'une fait 3n + 5 opérations, l'autre n² / 100 + 2. Pour n = 10, la seconde gagne. Pour n = 10 000, c'est l'inverse.
« On ne s'intéresse pas à n = 10, dit Sam. On s'intéresse à ce qui se passe quand n devient immense. C'est le rôle du Big O. »
Tu apprends à lire et à écrire la notation qu'utilisent tous les ingénieurs pour parler de performance.
🎯 Ta mission
À la fin, je serai capable de :
- expliquer ce que signifie O(n)
- simplifier une formule de coût (ignorer constantes et termes mineurs)
- reconnaître les classes O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)
- ordonner ces classes par vitesse de croissance
- comparer deux algorithmes avec leur Big O
🧩 Défi d'échauffement (5 XP)
Voici deux formules de coût : A(n) = 100 n et B(n) = n². Calcule A et B pour n = 10, 100, 1 000, 10 000. À partir de quelle valeur de n, environ, B dépasse-t-il A ? Que se passe-t-il ensuite ?
💡 Le concept
L'idée
Le Big O décrit comment le coût croît quand n devient grand, en ignorant :
- les constantes multiplicatives (3n et n sont de la même famille) ;
- les termes mineurs (n² + 5n + 20 se comporte comme n²).
On écrit O(n²) et on lit « de l'ordre de n au carré ».
Règles de simplification
| Formule de coût | Big O |
|---|---|
| 5 | O(1) |
| 3n + 7 | O(n) |
| n² + 100n + 4 | O(n²) |
| 2n + n log n | O(n log n) |
| 500 | O(1) |
Les grandes familles
| Notation | Nom | Exemple typique |
|---|---|---|
| O(1) | constant | lire liste[i], accéder à un dictionnaire |
| O(log n) | logarithmique | recherche binaire |
| O(n) | linéaire | parcourir une liste |
| O(n log n) | quasi-linéaire | bons tris (fusion) |
| O(n²) | quadratique | double boucle |
| O(2ⁿ) | exponentiel | tester tous les sous-ensembles |
Combien d'opérations ?
| n | log n | n log n | n² | 2ⁿ |
|---|---|---|---|---|
| 10 | 3 | 33 | 100 | 1 024 |
| 100 | 7 | 664 | 10 000 | ≈ 10³⁰ |
| 1 000 | 10 | 9 966 | 1 000 000 | inimaginable |
| 1 000 000 | 20 | 20 millions | 10¹² | : |
Un ordinateur fait de l'ordre de un milliard d'opérations simples par seconde. Un algorithme en O(n²) sur 1 million d'éléments (10¹² opérations) prend des minutes à des heures ; en O(n log n), moins d'une seconde.
Ce que Big O ne dit pas
- Il ne compare pas deux algorithmes de même classe (deux O(n) peuvent différer d'un facteur 10).
- Il décrit les grandes valeurs de n. Pour de petites données, un algorithme « moins bon » peut gagner.
- Il dépend de l'hypothèse (pire cas, cas moyen).
🧠 Astuce : O(n) se lit « si les données sont multipliées par 10, le travail est multiplié par 10 ». O(n²) : « multiplié par 100 ».
🔍 Exemple pas à pas
Problème : classer ces algorithmes du plus rapide au plus lent pour de grandes données.
- Lire le premier élément d'une liste.
- Chercher dans une liste non triée.
- Chercher dans une liste triée par recherche binaire.
- Trier avec le tri fusion.
- Comparer toutes les paires.
| Algorithme | Big O |
|---|---|
| 1. Lire le premier | O(1) |
| 3. Recherche binaire | O(log n) |
| 2. Recherche linéaire | O(n) |
| 4. Tri fusion | O(n log n) |
| 5. Toutes les paires | O(n²) |
Vérification par le calcul (le nombre d'opérations pour n = 1 024) :
import math
n = 1024
print("O(1) :", 1)
print("O(log n) :", int(math.log2(n)))
print("O(n) :", n)
print("O(n log n):", int(n * math.log2(n)))
print("O(n²) :", n * n)
Simplification d'une formule : 4n² + 20n + 100. Quand n = 1 000, 4n² vaut 4 000 000, 20n vaut 20 000, 100 est négligeable. Le terme dominant décide : O(n²).
✍️ À toi, avec aide (10 XP)
Donne le Big O de chaque formule :
- 7n + 3
- 2n² + 50n
- 100
- n + n log n
- 3 × 2ⁿ + n³
Puis classe les cinq du plus lent au plus rapide pour n très grand.
💡 Indice 1
On garde le terme qui grandit le plus vite et on retire la constante qui le multiplie.
💡 Indice 2
n log n grandit plus vite que n, mais moins vite que n².
💡 Indice 3
2ⁿ finit toujours par dépasser n³.
✅ Réponse
- O(n) · 2. O(n²) · 3. O(1) · 4. O(n log n) · 5. O(2ⁿ).
Du plus lent au plus rapide : O(2ⁿ) > O(n²) > O(n log n) > O(n) > O(1).
🚀 À toi, en solo (20 XP)
Écris un petit programme qui, pour n = 10, 100, 1 000, 10 000, 100 000, affiche un tableau avec log₂ n, n, n log₂ n, n² (utilise math.log2) et, pour chaque n, indique le temps en secondes si un ordinateur fait 10⁹ opérations par seconde.
Puis réponds : pour n = 100 000, quel algorithme en O(n²) est-il encore utilisable ?
✅ Pistes de correction
import math
print(f"{'n':>8} {'log n':>6} {'n log n (s)':>14} {'n² (s)':>14}")
for n in (10, 100, 1_000, 10_000, 100_000):
nlogn = n * math.log2(n) / 1e9
carre = n * n / 1e9
print(f"{n:>8} {math.log2(n):>6.1f} {nlogn:>14.6f} {carre:>14.6f}")
Pour n = 100 000 : n² = 10¹⁰ opérations, soit environ 10 secondes à 10⁹ opérations par seconde. Utilisable pour un traitement ponctuel, pas pour une requête web. n log n vaut environ 1,7 million d'opérations, soit 2 millisecondes.
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Garder les constantes | 3n et n ne sont pas à distinguer en Big O | Retirer constantes et termes mineurs |
| Penser que O(n) = rapide | Deux O(n) peuvent différer de 100 fois | Mesurer quand l'écart compte |
| Ignorer les petits n | Un algorithme « lent » peut gagner sur 10 éléments | Choisir selon la taille réelle des données |
| Confondre log n et n | Erreur d'un facteur énorme | Se rappeler : log₂(1 000 000) ≈ 20 |
🐉 Mini-boss (40 XP)
Pour chaque fonction ci-dessous, donne le Big O, justifie en une phrase, puis vérifie en comptant les opérations pour n = 100, 200, 400.
def A(n):
c = 0
for i in range(n):
c += 1
return c
def B(n):
c = 0
i = 1
while i < n:
c += 1
i *= 2
return c
def C(n):
c = 0
for i in range(n):
for j in range(i):
c += 1
return c
def D(n):
c = 0
for i in range(n):
j = 1
while j < n:
c += 1
j *= 2
return c
✅ Pistes de correction
- A : O(n) · B : O(log n) (i double à chaque tour) · C : O(n²) (n(n−1)/2) · D : O(n log n) (n tours × log n tours internes).
def A(n):
c = 0
for i in range(n): c += 1
return c
def B(n):
c, i = 0, 1
while i < n: c += 1; i *= 2
return c
def C(n):
c = 0
for i in range(n):
for j in range(i): c += 1
return c
def D(n):
c = 0
for i in range(n):
j = 1
while j < n: c += 1; j *= 2
return c
for n in (100, 200, 400):
(n, A(n), B(n), C(n), D(n))
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. O(n²) signifie que si n est multiplié par 10, le travail est multiplié par :
- A. 10
- B. 1 000
- C. environ 100
2. La classe la plus rapide parmi celles-ci est :
- A. O(log n)
- B. O(n)
- C. O(n²)
3. On simplifie 5n² + 30n en :
- A. O(n)
- B. O(n²)
- C. O(30n)
4. 🔁 Révision mission 01 : Que devient le coût d'un algorithme linéaire si n double ?
- A. Il quadruple
- B. Il reste identique
- C. Il double
5. 🔁 Révision mission 01 : Le pire cas donne :
- A. une garantie
- B. un coût optimiste
- C. un coût moyen exact
✅ Réponses
- C.
- A.
- B.
- C.
- A.
🪞 Je réfléchis (10 XP)
- Dans ta vie, quelle tâche a un coût « quadratique » (chaque nouvel élément oblige à comparer avec tous les autres) ?
- Pourquoi ignorer les constantes est-il à la fois utile et dangereux ?
🎒 À retenir
- Big O décrit la croissance du coût pour de grands n.
- On ignore les constantes et les termes mineurs.
- Hiérarchie : O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
- Big O ne compare pas deux algorithmes de même classe.
- Pour de petites données, tout est rapide.
flowchart LR
T(["La notation Big O"])
T --> R1["1. Big O décrit la croissance du coût pour de grands n."]
T --> R2["2. On ignore les constantes et les termes mineurs."]
T --> R3["3. Hiérarchie : O1 Olog n On On log n On² O2ⁿ."]
T --> R4["4. Big O ne compare pas deux algorithmes de même classe."]
T --> R5["5. Pour de petites données, tout est rapide."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Lecteur de courbes
← Mission 01 — Compter ce que coûte un programme · Mission 03 — Boucles et compositions →
HEF-030 — Complexité

