Complexité algorithmique
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
La théorie de la complexité algorithmique s'intéresse à l'estimation de l'efficacité 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 ?
[modifier] Histoire
Dans les années 1960 et au début des années 1970, alors qu'on en était à découvrir des algorithmes fondamentaux (tris tels que quicksort, arbres couvrants tels que les algorithmes de Kruskal ou de Prim), 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 standards. » (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 et du 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 (c'est-à-dire uniquement par comparaisons) 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).
Signalons également l'évaluation de la complexité en moyenne des algorithmes: son évaluation passe souvent par des techniques sophistiquées d'analyse mathématique.
[modifier] Détails
Pour qu'une analyse ne dépende pas de la vitesse d'exécution de la machine ni de la qualité du code produit par le compilateur, il faut utiliser comme unité de comparaison des « opérations élémentaires » en fonction de la taille des données en entrée.
Voici quelques 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.
Il faut souvent préciser quelles sont les opérations élémentaires pertinentes pour le problème étudié : si les nombres manipulés restent de taille raisonnable, on considérera que l'addition de deux entiers prend un temps constant, quels que soient les entiers considérés (ils seront en effet codés sur 32 bits). En revanche, lorsque l'on étudie des problèmes de calcul formel où la taille des nombres manipulés n'est pas bornée, le temps de calcul du produit de deux nombres dépendra de la taille de ces deux nombres.
On définit alors la taille de la donnée sur laquelle s'applique chaque problème par un entier lié au nombre d'éléments de la donnée. Par exemple, le nombre d'éléments dans un algorithme de tri, le nombre de sommets et d'arcs dans un graphe.
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 : comme le « plus mauvais cas » peut en pratique n'apparaître que très rarement, on étudie tm(n), l'espérance sur l'ensemble des temps d'exécution, où chaque entrée a une certaine probabilité de se présenter. L'analyse mathématique de la complexité moyenne est souvent délicate. De plus, la signification de la distribution des probabilités par rapport à l'exécution réelle (sur un problème réel) est à considérer.
On étudie systématiquement la complexité asymptotique, notée grâce aux notations de Landau.
- idée 1 : évaluer l'algorithme sur des données de grande taille. Par exemple, lorsque n est « grand », 3n3 + 2n2 est essentiellement 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. De 3 * n3, on ne retient que n3
L'algorithme est dit en O(n3).
L'idée de base est donc qu'un algorithme en O(na) est « meilleur » qu'un algorithme en O(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 ?
- 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 notion indispensable pour le développement d'algorithmes efficaces.
| Notation | Type de complexité |
|---|---|
| O(1) | complexité constante (indépendante de la taille de la donnée) |
| O(log(n)) | complexité logarithmique |
| O(n) | complexité linéaire |
| O(nlog(n)) | complexité quasi-linéaire |
| O(n2) | complexité quadratique |
| O(n3) | complexité cubique |
| O(np) | complexité polynomiale |
| O(nlog(n)) | complexité quasi-polynomiale |
| O(2n) | complexité exponentielle |
| O(n!) | complexité factorielle |
[modifier] Voir aussi
- Théorie de la complexité qui pose un cadre formel pour traiter de la complexité des problèmes : la complexité d'un problème est celle du meilleur algorithme permettant de résoudre ce problème.
- Théorie de la complexité algorithmique
