Skip to content

Texte

Approche analytique : comptons le nombre d'instructions

Essayons d'exprimer la complexité d'un algorithme par une fonction mathématique du nombre d'instructions élémentaires réalisées; celle-ci dépend de la taille du problème à résoudre.

Exemple: la recherche du minimum

Le travail nécessaire pour qu'un programme s'exécute dépend de la 'taille' du jeu de données fourni.

Par exemple, si nous analysons le code qui effectue une recherche du minimum dans une liste Python s de petits entiers, il est intuitivement normal que cet algorithme prenne un temps proportionnel à len(s), et soit noté, par exemple, \(T(len(s))\).

Dénotons \(len(s) = n\). \(n\) est la taille de la liste et donc par extension, également la taille du problème.

Donnons ici la partie traitement de cet algorithme en ayant eu soin de transformer le for en while pour mieux détailler chaque étape d'exécution de l'algorithme et nous supposons n = len(s) connu dans le programme :

1  res = s[0]  
2  i = 1       
3  while  i < n:    
4     if  s[i] < res:
5        res = s[i]
6     i = i + 1 
7  return res

Pour obtenir des résultats qui restent valables quel que soit l'ordinateur utilisé, il faut réaliser des calculs simples donnant une approximation dans une unité qui soit indépendante du processeur utilisé. On peut, par exemple, faire l'approximation que chaque assignation de donnée simple ou test élémentaire représente une unité de temps d'exécution.

D'autres hypothèses auraient pu être faites. Par exemple, on aurait pu ne considérer que les assignations et rechercher la complexité en nombre d'assignations, ou ne considérer que les tests et rechercher la complexité en nombres de tests effectués par l'algorithme.

La complexité dépend donc fortement de l'unité prise qui doit être clairement précisée.

Avec nos hypothèses, les instructions des lignes 1, 2 et 7 prennent chacune une unité de temps d'exécution.

La boucle while de la ligne 3 à 6 s'exécute \(n-1\) fois, mais le test s'effectue \(n\) fois. La ligne 3 prend \(n\) unités et la ligne 6, \(n-1\) unités.

Le test de la ligne 4 prend une unité; il est effectué \(n-1\) fois et donc la ligne 4 utilisera au total \(n-1\) unités.

L'assignation de la ligne 5 prend une unité. Elle n'est effectuée que lorsque le test du if est vérifié. Si l'on ne désire pas uniquement faire une seule mesure sur un jeu de données bien précis, il faut donc expliciter si l'on désire connaître le temps d'exécution dans le meilleur des cas \(T_{min}(n)\), le pire des cas \(T_{MAX}(n))\), ou en moyenne \(T_{moyen}(n)\). Ici:

  • \(T_{min}(n)\) est donné dans le cas où le test du if n'est jamais vérifié, ce qui signifie que le minimum se trouve à la première composante. On a alors: \(T_{min}(n) = 1+1+n+(n-1)+(n-1)+1 = 3n+1\)

  • \(T_{MAX}(n)\) est donné dans le cas où le test du if est à chaque fois vérifié, ce qui correspond au cas où toutes les valeurs de s sont distinctes et triées en ordre décroissant. On a alors: \(T_{MAX}(n) = 1+1+n+(n-1)+(n-1)+(n-1)+1 = 4n\)

Le calcul de \(T_{moyen}(n)\) est généralement beaucoup plus difficile à effectuer. Si nous faisons des hypothèses simplificatrices que toutes les valeurs de la liste sont différentes et distribuées uniformément, nous obtenons :

\(3n+\ell n(n) < T_{moyen}(n) < 3n+\ell n(n)+1\)

Tout cela fait beaucoup de calculs juste pour 7 lignes de codes. Essayons de trouver plus simple !