Complexité algorithmique
| Image manquante Symbole-ordinateur.png | Cet article est une ébauche concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
La théorie de la complexité algorithmique s'intéresse à la bonne utilisation des algorithmes.
Elle s'attache à la question : entre différents algorithmes réalisant une même tâche, quel est le plus rapide et dans quelles conditions ?
Dans les années 1960 et au début des années 1970, alors qu'on en était à découvrir des algorithmes fondamentaux (quicksort, Boyer-Moore...), on ne mesurait pas leur efficacité. On se contentait de dire : « cet algorithme (de tri) se déroule en 6 secondes avec un tableau de 50 000 entiers choisis au hasard en entrée, sur un ordinateur IBM 360/91. Le langage de programmation PL/I a été utilisé avec les optimisations standard ». (cet exemple est imaginaire)
Une telle démarche rendait difficile la comparaison des algorithmes entre eux. La mesure publiée était dépendante du processeur utilisé, des temps d'accès à la mémoire vive et de masse, du langage de programmation/compilateur utilisé, etc.
Une approche indépendante des facteurs matériels était nécessaire pour évaluer l'efficacité des algorithmes. Donald Knuth fut un des premiers à l'appliquer systématiquement dès les premiers volumes de sa série The art of computer programming. Il complétait cette analyse de considérations propres à la théorie de l'information : celle-ci par exemple, combinée à la formule de Stirling, montre qu'il ne sera pas possible d'effectuer un tri général de N élements en un temps croissant moins rapidement avec N que N ln N sur une machine algorithmique (à la différence peut-être d'un ordinateur quantique).
Détails
Si l'on élimine de l'analyse de la complexité la question de la vitesse d'exécution de la machine et la qualité du code produit par le compilateur, il ne reste comme paramètre significatif que « la taille des données sur lesquelles il s'exécute ».
On exprime donc le temps d'exécution en nombre d'opérations élémentaires. Le temps d'exécution d'une opération élémentaire ne dépend pas de la taille de la donnée (par exemple, l'addition de deux entiers codés sur 32 bits prend un même temps, quels que soient les entiers considérés).
Exemples d'opérations élémentaires : accès à une cellule mémoire, comparaison de valeurs, opérations arithmétiques (sur valeurs à codage de taille fixe), opérations sur des pointeurs.
Pour la taille de la donnée, on se limite à un ou plusieurs entiers liés au nombre d'éléments de la donnée. Par exemple, le nombre d'éléments dans un algorithme de tri, dans un ensemble, le nombre de sommets et d'arcs dans un graphe orienté.
On évalue le nombre d'opérations élémentaires en fonction de la taille de la donnée : si 'n' est la taille, on calcule une fonction t(n).
Les critères d'analyse : le nombre d'opérations élémentaires peut varier substantiellement pour deux données de même taille. On retiendra deux critères :
- analyse au sens du plus mauvais cas : t(n) est le temps d'exécution du plus mauvais cas et le maximum sur toutes les données de taille n. Par exemple, le tri par insertion simple avec des entiers présents en ordre décroissants.
- analyse au sens de la moyenne : tm(n) est l'espérance sur l'ensemble des temps d'exécution muni d'une distribution des probabilités des temps d'exécution. L'analyse mathématique de la complexité moyenne est souvent très délicate. De plus, la signification de la distribution des probabilité par rapport à l'exécution réelle (sur un problème réel) est à considérer.
On a donc introduit des notations asymptotiques ou notations de Landau.
- idée 1 : évaluer l'algorithme sur des données de grande taille. Par exemple, lorsque n est 'grand', 3n3 + 2n2 devient indiscernable de 3n3.
- idée 2 : on élimine les constantes multiplicatrices, car deux ordinateurs de puissances différentes diffèrent en temps d'exécution par une constante multiplicatrice. À partir de là, 3*n^3 devient n^3
L'algorithme est dit en 0(n3).
L'idée de base est donc qu'un algorithme en 0(na) est « meilleur » qu'un algorithme en 0(nb) si a < b.
Les limites de cette théorie :
- le coefficient multiplicateur est oublié : est-ce qu'en pratique 100 * n2 est « meilleur » que 5 * n3 ?
- le « plus mauvais cas » peut en pratique n'apparaître que très rarement,
- l'occupation mémoire, les problèmes d'entrées/sorties sont occultés,
- dans les algorithmes numériques, la précision et la stabilité sont primordiaux.
Point fort : c'est une aide incomparable pour le développement d'algorithmes efficaces.
Les classes de complexité :
- linéaire : an + b
- polynomiale :
- exponentielle : an
- factorielle : n!