Complexité des algorithmes

La programmation n'est pas que de la pure bidouille, il y a une théorie derrière... C'est pour cela que je vous propose ce mois-ci de découvrir comment mesurer l'efficacité - la complexité temporelle - d'un algorithme. Vous pourrez avoir un exposé plus précis de ceci dans un cours d'informatique de premier ou second cycle universitaire (ou de classe prépa).

En fait, il faudrait distinguer deux types de complexité : la complexité temporelle et la complexité spatiale. La complexité temporelle permet d' évaluer quel va être la rapidité d'exécution d'un algorithme en fonction d'un ou de plusieurs paramètres dépendant de la ou des données en entrée. La complexité spatiale - vous l'aurez compris - permet d'évaluer l'occupation mémoire que va nécessiter un algorithme en fonction (toujours) de certains paramètres. Mais je ne vous apprendrais rien en vous disant que de nos jours la mémoire n'est plus un paramètre réellement limitant, le prix de la RAM ayant énormément baissé en une vingtaine d'années (de plus la mémoire virtuelle est une autre réponse à ce problème).

Ainsi, nous allons mesurer la complexité temporelle d'un algorithme. Pour y parvenir, nous devons déjà voir quelle 'unité' choisir... Prendre la seconde comme unité n'est pas un bon choix : en effet, la vitesse des microprocesseurs ne cesse d'évoluer et une instruction qui prendrait énormément de temps aujourd'hui risquerait de n'en prendre que très peu dans un futur proche. Ainsi, nous allons plutot étudier la complexité d'un algorithme en choisissant généralement l'instruction la plus coûteuse et en évaluant le nombre de fois qu'elle est exécutée en fonction d'un ou de plusieurs paramètres dépendant des données en entrée : la longueur n d'une liste, la hauteur n d'un arbre, l'indice n lorsque qu'il s'agit de calculer le n-ème terme d'une suite, ... Il est possible d'utiliser plus d'un seul paramètre ; par exemple, pour une fonction faisant l'union de deux arbres a et b , la complexité dépendra de la hauteur |a| de l'arbre a et de la hauteur |b| de l'arbre b. L'instruction la plus coûteuse est la comparaison de deux objets lors d'un algorithme de tri, les opérations arithmétiques + et * lors d'un algorithme de multiplication de polynomes ou de matrices, ...

Enfin, il nous faut une échelle de comparaison et c'est là que l'outil mathématique intervient :

Ainsi, avec un grand O, on sait à quoi s'attendre dans le pire des cas alors qu'avec un grand thêta, on sait à quoi s'attendre tout le temps. En général, on utilise surtout le grand O...

On peut alors classifier les complexités :

Allure des complexités usuelles simples

  1. complexité logarithmique en O(ln(n)) (ou lnk(n), k>1)
  2. complexité linéaire en O(n)
  3. complexité quasi-linéaire en O(n*ln(n))
  4. complexité polynômiale en O(nk) (k>1)
  5. complexité exponentielle en O(an) (a>1)
  6. complexité hyperexponentielle : revoir votre algorithme ! mais parfois on ne peut pas faire mieux, malheureusement...
On voit donc que le top du top, c'est la complexité logarithmique et le pire c'est la complexité hyperexponentielle...

Voici quelques exemples de calculs simples de complexité :

Voilà pour cette courte intrusion dans la théorie... La prochaine fois, je parlerais exclusivement de programmation mais je ne sais pas encore à quel sujet. D'ici là, portez-vous bien et essayez d'évaluer la complexité de vos algorithmes afin, éventuellement, de vous rendre compte qu'un petit changement de point de vue (donc d'algorithme) est bougrement nécessaire... ;-)

auteur : Seb/the Removers


Sommaire Sommaire du magazine


[Entrée du site] [Presentation du groupe] [Nos articles] [Nos logiciels] [Téléchargement] [Nos liens] [Contacts] [Nouveautés du site]

[Main page] [Presentation of the group] [Our products] [Download] [Links] [Contacts] [What's new]