La complexité : compter les opérations, pas les secondes
Objectif : ce qui se passe quand les données deviennent grandes
L’essentiel
Mesurer un algorithme au chronomètre revient à mesurer une machine, un jour donné, sur un jeu d'essai donné. Changez de machine, la mesure change. La COMPLEXITÉ répond autrement : elle compte le NOMBRE D'OPÉRATIONS effectuées en fonction de la taille des données, notée n.
À retenir
- La complexité compte les opérations selon la taille n, pas les secondes sur une machine
- On garde l'ordre de grandeur : le terme dominant, sans ses constantes
- Deux boucles imbriquées sur les mêmes données donnent du n au carré
- Une complexité exponentielle est condamnée dès quelques dizaines de données
Le tableau à connaître
| La famille | La notation | Quand n double | Exemple typique |
|---|---|---|---|
| Constante | O(1) | Rien ne change | Lire le premier élément d'une liste |
| Logarithmique | O(log n) | Une opération de plus | La recherche dichotomique |
| Linéaire | O(n) | Le temps double | Le parcours complet d'une liste |
| Quadratique | O(n²) | Le temps quadruple | Le tri par sélection, deux boucles imbriquées |
| Exponentielle | O(2 puissance n) | Le temps est mis au carré | L'essai de toutes les combinaisons |
⚠ Attention, piège
- Une complexité meilleure ne garantit pas un programme plus rapide SUR LES PETITES DONNÉES.
Exemples
- Algorithme du tri par sélection. La boucle extérieure fait n moins 1 passes.
Le plan de la leçon
- Le chronomètre est un mauvais juge
- Les cinq familles qu'on rencontre
- Compter, sur un cas concret
- Ce que cela permet de décider avant d'écrire
Je me teste
Un algorithme en O(n²) traite 1 000 éléments en 1 seconde. Et 10 000 ?
- Environ 1 seconde
- Environ 100 secondes
- Environ 10 secondes
Que signifie O(log n) quand la taille des données double ?
- Le carré des opérations
- Deux fois plus d'opérations
- Une opération de plus environ
Le mot d’Oscar — Combien pour dix mille ?
Réponses : 1. B · 2. C