Définitions, contrats et coûts
Relier opérations, invariants et modèles de coût.
| Notion | À retenir |
|---|---|
| Contrat | Décrire entrées, sorties, erreurs et mutations. |
| O / Θ | Borne supérieure / borne serrée ; annoncer pire cas, moyenne ou amortissement. |
| Mémoire | Compter stockage auxiliaire, copies et sortie séparément. |
Vérifier sur un exemple
Une somme vérifiable
Comparez une somme incrémentale à la spécification avant de raisonner sur son coût.
Python
Python # running_total.py
values = [4, -2, 7]
total = 0
for value in values:
total += value
assert total == sum(values)
print(total)
# Expected output:
# 9Résultat expliqué. Chaque élément est lu une fois : Θ(n) additions dans le modèle à entiers de taille bornée et Θ(1) mémoire auxiliaire.
Erreur à éviter. Des entiers arbitrairement grands changent le coût d’une addition.
Une boucle qui traite deux fois chaque élément devient-elle quadratique ?
Non : 2n opérations restent Θ(n), si chaque opération a un coût borné.