Introduction à la complexité

I. Définition

La complexité d'un algorithme désigne l'ordre de grandeur de la fonction qui associe à la taille d'un problème le nombre de ressources

d'un type donné considérées.

On étudie en général 2 types de complexité :

• la complexité en temps
• la complexité en mémoire

Par ailleurs, lorsqu'on étudie une complexité,on peut s'intéresser à :

• la complexité en moyenne
• la complexité au pire

En effet, suivant les données, un même algorithme peut être plus ou moins efficace.

II. Pourquoi étudier la complexité

Sur des problèmes "petits", la complexité est rarement un critère fondamental. Elle devient critique dans 2 cas :

• des problèmes moyens exécutés très fréquemment ;
• des problèmes de grande taille.

C'est surtout d'ailleurs ce deuxième cas qui est problématique. L'augmentation de la puissance de calcul ne change rien à la complexité. Cela permet seulement de reculer un peu les limites de l'acceptable. Cela est d'autant plus vrai que la mise à disposition d'un nombre croissant de données grâce à Internet augmente le nombre de cas d'utilisation d'algorithmes sur de gros volumes de données.