Introduction à La complexité Algorithmique

1. Introduction

Analyser un algorithme revient à prévoir les ressources  nécessaires à cet algorithme et à mesurer son temps d'exécution. En général, quand on analyse plusieurs algorithmes candidats pour un problème donné, on arrive aisément à identifier le candidat le plus efficace. Ce type d'analyse peut révéler plusieurs candidats valables et permet d'éliminer les autres.

L'analyse d'un algorithme, même simple, peut s'avérer difficile. Il est donc nécessaire de se donner des outils mathématiques pour parvenir à nos fins.

le temps d'exécution d'un programme dépend de plusieurs facteurs :

• les données de l'algorithme
• le type du compilateur 
• la vitesse d'exécution
• la complexité algorithmique.

En parle de deux type de coûts :

1. Temps d'exécution ( nombre d'opérations effectuées par l'algorithme), Complexité temporelle
2. Taille de mémoire nécessaire pour stocker les différentes structures de données pour l'exécution: complexité spatiale

2. Complexité temporelle
     Pour étudier la complexité temporelle, on ne raisonne pas en termes de durée mais en nombre d’opérations élémentaires. En effet, la durée d’exécution d’un programme dépend des performances de l’ordinateur ce qui n’est pas le cas du nombre d’opérations élémentaires qui ne dépend que du programme écrit.
La complexité est exprimée comme une fonction de la taille des données traitées.
On distingue :

• Complexité en meilleur cas : c’est la situation la plus favorable,
  par exemple : recherche d’un élément dans un tableau ; l'élément recherché situé à la première position du tableau
• Complexité en pire des cas : c’est la situation la plus défavorable,
  par exemple : recherche d’un élément dans un tableau,  alors qu’il ne figure pas dans le tableau.
  

3. Notation landau :( O- notation)
Quand nous calculons la complexité d'un algorithme , nous ne calculons pas sa complexité exacte ( c'est une estimation) , mais son ordre de grandeur .

Pour comparer des algorithmes, il n’est pas nécessaire d’utiliser la fonction T, mais seulement l’ordre de grandeur asymptotique, noté O (« grand O »).

Une fonction T(n) est en O(f(n)) (« en grand O de f(n)« ) si :

∃n0∈N,∃c∈R+,∀n∈R+,n≥n0⇒|T(n)|≤c|f(n)|

Autrement dit :

T(n) est en O(f(n)) s’il existe un seuil n0 à partir duquel la fonction T est toujours dominée par la fonction f, à une constante multiplicative fixée c près.