L'estimation des algorithmes

On n’abordera pas ici toute la méthodologie à suivre lorsque l’on veut estimer un algorithme mais simplement ce qu’il faut se dire à chaque fois que l’on veut estimer un code.

Qu’est-ce qu’un bon algorithme ? C’est bien entendu un algorithme qui répond correctement au problème posé. On souhaite généralement qu’il soit aussi rapide et n’utilise pas trop de mémoire.

Quel que soit la mesure choisie, il est clair que la qualité de l’algorithme n’est pas absolue mais dépend des données d’entrée. Les mesures d’efficacité sont donc des fonctions des données d’entrée. Pour évaluer le temps d’exécution d’un algorithme (par exemple un tri) sur une donnée d (par exemple un ensemble d’entiers à trier), on calcule le nombre d’opérations élémentaires (opérations arithmétiques, affectation, instruction de contrôle, etc.) effectuées pour traiter la donnée d. On admet communément que toute opération élémentaire prend un temps constant. Attention, cette hypothèse n’est valable que si tous les nombres sont codés sur un même nombre de bits.

Plutôt que de calculer le nombre d’opérations associé à chaque donnée, on cherche souvent à évaluer le nombre d’opérations nécessaires pour traiter les données qui ont une certaine “taille”. Il existe souvent un paramètre naturel qui est un estimateur raisonnable de la taille d’une donnée (par exemple, le nombre n d’éléments à trier pour un algorithme de tri, la taille n,m d’une matrice pour le calcul du déterminant, la longueur n d’une liste pour une inversion, etc.). Pour simplifier nous supposerons dans la suite que la “taille” d’une donnée est évaluée par un unique entier n. Les informaticiens s’intéressent à l’ordre de grandeur des temps d’exécution (ou de taille mémoire) quand n devient très grand. Le coût exact en secondes est en effet très difficile à mesurer et dépend de très nombreux paramètres. On utilise donc les notations O, Θ et Ω pour exprimer des relations de domination.

Ces notions s’étendent à la consommation mémoire d’un algorithme. On parle alors de complexité spatiale (maximale ou moyenne).