Complexité d'un algorithme

Fondamental

L'analyse d'algorithmes se veut un outil d'aide à la comparaison des performances des algorithmes. Nous utiliserons ci-après le mot complexité à son sens premier (du latin complexus enlacé, embrassé signifiant un objet constitué de plusieurs éléments ou plusieurs parties).

Les outils et méthodes que nous allons développer dans ce cours devrait vous convaincre que la complexité des algorithmes n'est pas compliquée (qui

est hélas le sens commun actuel du mot complexité) !

Dans le cadre de l'analyse d'algorithmes, il s'agit de mesurer les ressources critiques (coûteuses) utilisées par les algorithmes. Parmi les ressources fréquemment étudiées on trouve : le temps d'exécution ou de programmation, la mémoire, les processeurs, les messages, mais on pourrait tout aussi bien étudier sur les implémentations matérielles d'un algorithme la surface du circuit ou le nombre de portes logiques, l'énergie consommée, les radiations émises . . . ou encore le nombre de prions libérés (informatique biologique).

D'ailleurs lors de la conception de certains ordinateurs mobiles le problème crucial est celui de l'énergie (i.e. la consommation électrique) induite

par l'émission réception. Le calcul proprement dit engendrant une consommation négligeable. Il faut donc trouver des protocoles où l'on émet-écoute

le moins longtemps possible (à coup sûr).

Il s'agit d'évaluer les performances de l'algorithme en fonction de cette ressource, i.e. la taille de cette ressource utilisée par l'algorithme.

Définition

On appelle complexité de l'algorithme A pour la ressource R la fonction :

T(A, R, n) = max{ ressource R utilisée par A sur l'ensemble des données de taille n}

Définition

La taille d'une donnée est simplement la taille d'un bon codage en mémoire de cette donnée exprimée en nombres de bits.

Ainsi la taille d'un codage d'un entier n sera dlog2(n + 1)e, et non pas n. On préfère les codages binaires aux codages unaires des entiers.

Lorsqu'il n'y a pas d'ambiguïté, on notera T(A, R, n) simplement par T(n). Cette mesure est appelée la mesure du plus mauvais cas, car elle garantit que tout comportement de l'algorithme A utilisera au plus T(A, R, n) éléments de la ressource R