Objectifs de cette leçon
- Mesurer la complexité temporelle d'un algorithme
- Comprendre la notation Grand O (O(1), O(n), O(n²))
- Comparer l'efficacité de différentes solutions
Complexité algorithmique ⏱
Tu as appris à écrire des algorithmes. Mais comment savoir si ton algorithme est rapide ou lent ? Et si tu dois traiter 1 million de données, est-ce que ton programme mettra 1 seconde ou 1 semaine ? La complexité algorithmique répond à ces questions.
1. Pourquoi mesurer la performance ? 🤔
Deux algorithmes peuvent résoudre le même problème, mais l'un peut être 1000 fois plus rapide que l'autre.
Exemple concret : Chercher un mot dans un dictionnaire de 100 000 mots.
- Méthode 1 : regarder chaque mot un par un → jusqu'à 100 000 vérifications
- Méthode 2 : ouvrir au milieu, comparer, éliminer la moitié → seulement 17 vérifications !
La méthode 2 est beaucoup plus rapide — c'est ça, la complexité !
La complexité mesure comment le temps d'exécution augmente quand la taille des données (n) augmente.
2. La notation Grand O (Big O) 📏
La notation O(n) (on dit "Grand O de n") décrit la vitesse d'un algorithme en fonction de la taille des données n.
💡 Ne retiens que ça : O(n) veut dire "si n double, le nombre d'opérations double aussi".
Les voici du plus rapide au plus lent :
| Notation | Surnom | Si n = 1000… | Exemple |
|---|---|---|---|
| O(1) | Constant | 1 opération ⚡ | Accès à tab[5] |
| O(log n) | Logarithmique | ~10 opérations 🚀 | Recherche dans un dictionnaire |
| O(n) | Linéaire | 1000 opérations 🚗 | Parcourir une liste |
| O(n log n) | Quasi-linéaire | ~10 000 opérations 🚲 | Tri fusion |
| O(n²) | Quadratique | 1 000 000 opérations 🐢 | Deux boucles imbriquées |
| O(2^n) | Exponentiel | IMPOSSIBLE 💀 | Deviner un mot de passe |
🎯 L'essentiel : vise toujours le plus à gauche possible ! Si ton algo est O(n²) avec 10 000 données, ça fait 100 millions d'opérations. Avec O(n log n), seulement ~140 000.
3. Comment calculer la complexité ? 🧮
Règle 1 : On ignore les constantes
O(2n) = O(n), O(100n) = O(n). 2x ou 100x, c'est pareil : ça grandit linéairement.
Exécution pas à pas
pseudo1/5🔄POUR i ALLANT DE 0 À n FAIRE ⬅ n opérations🔄 BoucleVérifie si "POUR i ALLANT DE 0 À n ⬅ n opérations" est vrai. Si oui, on recommence. Sinon, on sort de la boucle.Répète les actions suivantes TANT QUE "POUR i ALLANT DE 0 À n ⬅ n opérations" est vraie. Dès que c'est faux, on continue après la boucle.
Règle 2 : On garde le terme dominant
Si ton code fait du O(n) + O(n²), le O(n²) est le plus gros → on dit O(n²).
Exécution pas à pas
pseudo1/9🔄POUR i ALLANT DE 0 À n FAIRE ⬅ O(n)🔄 BoucleVérifie si "POUR i ALLANT DE 0 À n ⬅ O(n)" est vrai. Si oui, on recommence. Sinon, on sort de la boucle.Répète les actions suivantes TANT QUE "POUR i ALLANT DE 0 À n ⬅ O(n)" est vraie. Dès que c'est faux, on continue après la boucle.
Règle 3 : Boucles imbriquées = multiplication
Une boucle dans une boucle → O(n × n) = O(n²)
Exécution pas à pas
pseudo1/6🔄POUR i ALLANT DE 0 À n FAIRE ⬅ n tours🔄 BoucleVérifie si "POUR i ALLANT DE 0 À n ⬅ n tours" est vrai. Si oui, on recommence. Sinon, on sort de la boucle.Répète les actions suivantes TANT QUE "POUR i ALLANT DE 0 À n ⬅ n tours" est vraie. Dès que c'est faux, on continue après la boucle.
4. Les 3 complexités à reconnaître 👀
O(n) — Linéaire : une boucle simple
Exécution pas à pas
pseudo1/4🔄POUR i ALLANT DE 0 À n FAIRE🔄 BoucleVérifie si "POUR i ALLANT DE 0 À n" est vrai. Si oui, on recommence. Sinon, on sort de la boucle.Répète les actions suivantes TANT QUE "POUR i ALLANT DE 0 À n" est vraie. Dès que c'est faux, on continue après la boucle.
⏱ Si n = 1000 → 1000 opérations. Si n = 1 000 000 → 1 000 000 opérations.
O(n²) — Quadratique : deux boucles imbriquées
Exécution pas à pas
pseudo1/6🔄POUR i ALLANT DE 0 À n FAIRE🔄 BoucleVérifie si "POUR i ALLANT DE 0 À n" est vrai. Si oui, on recommence. Sinon, on sort de la boucle.Répète les actions suivantes TANT QUE "POUR i ALLANT DE 0 À n" est vraie. Dès que c'est faux, on continue après la boucle.
⏱ Si n = 1000 → 1 000 000 opérations. Si n = 10 000 → 100 000 000 (bloquant !)
O(log n) — Logarithmique : la valeur double
Exécution pas à pas
pseudo1/6▶️i ← 1i ← 1Le programme exécute cette action, puis passe à la suivante.Le programme exécute cette instruction, puis passe à la suivante.
⏱ Si n = 1 000 000 → seulement ~20 opérations ! i vaut 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… On atteint 1 million en 20 étapes. C'est ultra-rapide ! 🚀
5. Comparaison visuelle des performances 📊
| n | O(1) | O(log n) | O(n) | O(n²) |
|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | 100 |
| 100 | 1 | ~7 | 100 | 10 000 |
| 1 000 | 1 | ~10 | 1 000 | 1 000 000 |
| 1 000 000 | 1 | ~20 | 1 000 000 | 10¹² (1 jour !) |
💡 Avec 1 million de données :
- O(n) = 1 million d'opérations → quelques millisecondes
- O(n²) = 1 million de millions → plusieurs jours
- O(log n) = 20 opérations → instantané
Choisis bien ton algorithme !
6. Complexité temporelle vs spatiale 🧠
- Complexité temporelle = nombre d'opérations (le temps)
- Complexité spatiale = quantité de mémoire utilisée
Parfois, on peut échanger de la mémoire contre de la vitesse. Exemple : au lieu de recalculer quelque chose à chaque fois, on le stocke dans un tableau. C'est la mémoïsation (ou cache).
💡 Règle d'or : Si tes données grossissent, choisis TOUJOURS le meilleur algorithme. Ce qui marche avec 100 éléments peut être catastrophique avec 1 000 000.
Exercices pour toi 🎯
Ouvre l'onglet Sandbox et détermine la complexité de ces extraits :
Exercice 1 : Combien d'opérations pour n = 1000 ?
for i in range(n): print(i)
→ O(n) — 1000 opérations
Exercice 2 : Et celui-ci ?
for i in range(n): for j in range(n): print(i, j)
→ O(n²) — 1 000 000 opérations
Exercice 3 : Et ce while ?
i = 1 while i < n: i *= 2 print(i)
→ O(log n) — seulement 10 opérations pour n = 1000 (i = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512)
Exercice 4 : À toi de jouer ! Quelle est la complexité ?
for i in range(n): for j in range(i, n): print(i, j)
(Indice : ça fait n + (n-1) + (n-2) + … + 1 = n(n+1)/2 → O(n²))
⚡ Simulateur — Complexité algorithmique
Étape 1/30La taille des données est n.