Bilan sur les coûts

Coût d'un algorithme

Le coût d'un algorithme mesure le nombre d'opérations élémentaires qu'il effectue.

Ce nombre d'opérations est souvent lié à la taille de la donnée d'entrée de l'algorithme.

Pour exprimer le coût d'un algorithme, on peut souvent se limiter au décompte du nombre d'itérations élémentaires réalisées.

Pire des cas

Pour évaluer le coût d'un algorithme dans le « pire des cas », on évalue son coût lorsque l'entrée va maximiser le nombre d'opérations réalisées.

On peut alors classer les algorithmes selon leur coût. Il faut toutefois garder à l'esprit que cette classification se base sur l'étude du pire des cas.

Face à certaines entrées il est tout à fait possible qu'un algorithme de coût important soit très efficace en moyenne.

Différents coûts

Il existe de nombreux types de relation entre la taille de l'entrée \(N\) et le nombre d'opérations réalisées.

On peut retenir :

• le nombre d'opérations ne dépend pas de la taille de \(N\) : coût constant,

• le nombre d'opérations évolue proportionnellement à \(N\) : coût linéaire,

• le nombre d'opérations évolue proportionnellement au nombre de fois où \(N\) peut être divisé par \(2\) : coût logarithmique,

• le nombre d'opérations évolue proportionnellement au carré de \(N\) : coût quadratique.