| Terme | Définition |
|---|---|
| Benchmark | Mesure contrôlée et répétée des performances. |
| Big O | Notation qui décrit la croissance du coût pour de grands n, en ignorant constantes et termes mineurs. |
| Complexité en espace | Mémoire supplémentaire nécessaire en fonction de n. |
| Compromis temps-mémoire | Gagner du temps en utilisant plus de mémoire, ou l'inverse. |
| Coût amorti | Coût moyen par opération, en répartissant les opérations rares et chères. |
| Exponentiel | Coût qui double (ou plus) à chaque unité de n. |
| Goulot d'étranglement | Partie du programme qui limite la performance globale. |
| Loi d'Amdahl | Le gain global dépend de la part du temps que l'on accélère. |
| Médiane | Valeur du milieu d'une série de mesures, peu sensible aux pics. |
| Mémoïsation | Mémorisation des résultats déjà calculés pour éviter de les recalculer. |
| O(1) | Coût constant, indépendant de n. |
| O(log n) | Coût qui augmente lentement (division par deux à chaque étape). |
| O(n log n) | Coût des bons tris par comparaisons. |
| O(n) | Coût proportionnel à n. |
| O(n²) | Coût quadratique, typique d'une double boucle. |
| Opération élémentaire | Instruction de base comptée pour mesurer le coût (comparaison, addition…). |
| Pire cas | Entrée de taille n qui rend l'algorithme le plus coûteux. |
| Profileur | Outil qui mesure où le temps est passé dans un programme. |
| Récurrence | Équation décrivant le coût d'un algorithme récursif. |
| Taille de l'entrée (n) | Quantité qui mesure la taille du problème : nombre d'éléments, de lignes… |
HEF-030 — Complexité

