Les classes de croissance
| Classe | Si n est multiplié par 10 | Exemple |
|---|---|---|
| O(1) | inchangé | accès dictionnaire |
| O(log n) | +3 étapes | recherche binaire |
| O(n) | ×10 | parcours |
| O(n log n) | ×13 environ | tri efficace |
| O(n²) | ×100 | double boucle |
| O(2ⁿ) | explose | tous les sous-ensembles |
Coûts Python à connaître
liste[i],append: O(1) ·x in liste,insert(0, …),pop(0): O(n)x in ensemble,dict[cle]: O(1) en moyennesorted: O(n log n)
Démarche d'optimisation
- Objectif chiffré
- Mesure de base
- Profil
- Hypothèse (complexité)
- Correction minimale
- Preuve (équivalence + mesure)
- Rapport
Rappel mesure
- Répéter, médiane, plusieurs tailles
- Rapport T(2n)/T(n) : ≈2 → n ; ≈4 → n²
HEF-030 — Complexité

