Complexité temporelle

Pour avoir une idée du temps d'exécution d'un programme indépendamment du langage (ou de la machine), on évalue le nombre d’« opérations élémentaires » que ce programme doit exécuter. Parmi celles-ci, on trouve :

• affecter une valeur à une variable ;
• effectuer un test de comparaison (==, >, <, !=, ...) ;
• effectuer une opération arithmétique (addition, multiplication, ...) ;
• accéder à un élément d’un tableau, d’une chaîne de caractères, ...

Exemples

n est une variable de type entier.

1. On considère l'algorithme ci-dessous, rédigé en Python.

   if n <= 10 :
       n = 3*n
   else:
       n = 2*n
   

   Déterminer le nombre d'opérations élémentaires en fonction de la valeur de n.
   Une réponse

   Pour chaque valeur de l’entier n, il y a un test, une opération et une affectation. Il y a donc 3 opérations élémentaires dans ce code.

2. On considère l'algorithme ci-dessous, rédigé en Python

   s = 0
   for i in range(1, n+1):
       s = s+i
   

   Déterminer le nombre d'opérations élémentaires en fonction de la valeur de n.
   Une réponse

   Il y a une affectation hors de la boucle puis une addition et deux affectations (ne pas oublier l’affectation de i) dans la boucle. Puisqu’il y a n passages dans la boucle, on en déduit qu’il y a 3 n + 1 opérations élémentaires en tout.

Conséquences

En fait, il n'est pas utile de trop rentrer dans les détails car :

• d'une part cela peut devenir assez technique ;
• d'autre part, ces calculs dépendent beaucoup du langage utilisé.

L'important pour la suite sera de comprendre que chaque passage dans une boucle nécessite le même temps, car chaque passage réalise les mêmes opérations.