Numérique et sciences informatiques (spécialité) · Première · Algorithmique
Coût d'un algorithme
- Le coût d'un algorithme se mesure en temps (nombre d'opérations élémentaires comptées) ou en espace (mémoire maximale utilisée en même temps).
- On l'exprime en fonction de la taille de l'instance, jamais d'une donnée précise : on retient le plus souvent le pire des cas, parfois le meilleur ou le cas moyen.
- Un coût linéaire double quand la taille double ; la recherche dichotomique, en temps logarithmique, ajoute seulement une itération quand la taille double.
- Si la longueur vérifie , la dichotomie fait au plus itérations.