Aide-mémoire – Coût en opérations
BTS SIO SISR 2e année – Pour aller plus loin – S12
Un mot ou un sigle inconnu ? Passe la souris dessus, ou ouvre le glossaire.
Compter
| Structure | Coût |
|---|---|
for i in range(n) |
\(n\) |
| Deux boucles imbriquées | \(n^2\) |
| Boucle triangulaire | \(\dfrac{n(n-1)}{2}\) |
| Division par 2 jusqu'à 1 | \(\lfloor\log_2 n\rfloor\) tours |
Recherche séquentielle (n éléments)
| Cas | Comparaisons |
|---|---|
| Meilleur | 1 |
| Pire | \(n\) |
| Moyen | \((n+1)/2\) |
Méthode
- Choisir l'opération de référence.
- Exprimer le nombre de passages en fonction de \(n\).
- Raisonner sur le pire cas pour une garantie.
- Comparer sur des valeurs de \(n\) réalistes.