Estimation du coût algorithmique : identifier les opérations élémentaires.

Introduction

Dans la leçon précédente, nous avons découvert le concept de complexité temporelle. Nous avons compris qu'il s'agit d'une mesure objective de l'efficacité d'un algorithme, indépendante de la machine qui l'exécute. Pour la calculer, nous avons appris à décomposer un algorithme en opérations élémentaires et à les compter pour obtenir une fonction de coût, comme $C(n)=4n+4$.

Aujourd'hui, nous allons approfondir cette technique. L'objectif de cette leçon est d'identifier précisément ce que sont les opérations élémentaires et de s'entraîner à estimer le coût d'algorithmes un peu plus complexes. C'est une compétence fondamentale qui vous permettra de "sentir" l'efficacité d'un algorithme avant même de l'écrire. Maîtriser cette étape vous préparera parfaitement pour la prochaine leçon, où nous apprendrons à simplifier ces fonctions de coût avec la notation "Big O".

1. Qu'est-ce qu'une Opération Élémentaire ?

Dans la leçon précédente, nous avons intuitivement défini une opération élémentaire comme une action simple. Formalisons cela : une opération élémentaire est une instruction dont on peut supposer que le temps d'exécution est constant, c'est-à-dire qu'il ne dépend pas de la taille des données d'entrée.

Pour obtenir une liste claire de ce que l'on considère comme élémentaire, je vous propose de consulter le document suivant.

Pour résumer et traduire en pseudo-code, voici les opérations que nous compterons généralement comme une seule opération (coût = 1) :

• Affectation : variable <- valeur (ex: x <- 10, nom <- "Alice")
• Opérations arithmétiques : +, -, *, /, % (modulo)
• Comparaisons : ==, !=, <, >, <=, >=
• Opérateurs logiques : ET, OU, NON
• Accès à un élément de tableau : Tableau[i]
• Retour d'une fonction : retourner valeur

Il est tout aussi important de noter ce qui n'est PAS une opération élémentaire. Par exemple, la recopie d'un tableau entier ou la recherche d'un élément dans une liste ne sont pas des opérations à coût constant. Leur coût dépend de la taille du tableau !

2. Estimer le Coût d'un Algorithme

Maintenant que nous avons notre "catalogue" d'opérations, comment estimer le coût total ? La méthode consiste à analyser l'algorithme structure par structure.

Le document ci-dessous explique très bien comment le coût est calculé pour les différentes structures de contrôle.

Synthétisons la méthode :

1. Bloc d'instructions séquentielles : Le coût total est la somme des coûts de chaque instruction.
2. Structure conditionnelle (Si...Alors...Sinon) : Le coût est celui du test, plus le coût de la branche qui est exécutée. Pour une analyse "dans le pire des cas", on prend le coût de la branche la plus coûteuse.
3. Boucle (Pour, Tant que) : Le coût est approximativement le nombre d'itérations multiplié par le coût du corps de la boucle.

Exemple 1 : Une boucle simple avec condition

Appliquons cette méthode à un exemple concret : un algorithme qui compte le nombre de fois qu'un élément x apparaît dans un tableau t.

Reprenons l'analyse ensemble en pseudo-code. Soit n la taille du tableau t.

Algorithme nombre_occurrences(x, t)

1. c <- 0
2. pour i de 0 à n-1 faire

3.  `si t[i] == x alors`
   

4.      `c <- c + 1`
   

5. retourner c

Analyse du coût :

• Ligne 1 : c <- 0 -> 1 opération (affectation).
• Ligne 2 : La boucle s'exécute n fois.
• À chaque tour de boucle :
  • Ligne 3 : t[i] (accès), == (comparaison) -> 2 opérations.
  • Ligne 4 (dans le pire des cas, cette ligne est toujours exécutée) : c + 1 (addition), c <- ... (affectation) -> 2 opérations.
• Ligne 5 : retourner c -> 1 opération.

Coût total (dans le pire des cas) :
Le coût de ce qu'il y a dans la boucle est de $2+2=4$ opérations.
$C(n)=1_{\text{(init c)}}+n\times (4_{\text{(corps boucle)}})+1_{\text{(retour)}}$
$C(n)=4n+2$
(Note : le document arrive à 5n+2 en comptant différemment la gestion de la boucle, mais l'important est de voir que le résultat est une fonction linéaire en n).

Exemple 2 : Des boucles imbriquées

Que se passe-t-il lorsque des boucles sont les unes dans les autres ? Leurs coûts se multiplient.

Considérons un tableau t à 2 dimensions avec n lignes et p colonnes.

Algorithme est_element(x, t)

1. pour i de 0 à n-1 faire

2.  `pour j de 0 à p-1 faire`
   

3.      `si t[i][j] == x alors`
   

4.          `retourner Vrai`
   

5. retourner Faux

Analyse du coût (dans le pire des cas, l'élément n'est pas trouvé) :

• La boucle externe (sur i) s'exécute n fois.
• Pour chacune de ces n fois, la boucle interne (sur j) s'exécute p fois.
• Le nombre total de fois où le corps de la boucle interne est exécuté est donc $n\times p$.
• Le corps de la boucle (si t[i][j] == x) a un coût constant (disons k opérations).
• Le coût total est donc approximativement $k\times n\times p$. C'est une fonction qui dépend des deux dimensions du tableau.

3. À vous de jouer !

La meilleure façon de comprendre est de pratiquer. Analysons ensemble un algorithme simple avec deux boucles imbriquées.

Voici l'algorithme f1 tiré des exercices du document LINK.

Algorithme f1(n)

1. x <- 0
2. pour i de 0 à n-1 faire

3.  `pour j de 0 à n-1 faire`
   

4.      `x <- x + 1`
   

5. retourner x

Prenez un instant pour réfléchir. En vous basant sur l'exemple précédent, quel serait le coût de cet algorithme en fonction de n ?

...

Analysons-le ensemble :

1. Ligne 1 : x <- 0 -> 1 opération.
2. Ligne 2 : La boucle sur i s'exécute n fois.
3. Ligne 3 : Pour chaque tour de la boucle i, la boucle sur j s'exécute aussi n fois.
4. Ligne 4 : L'instruction x <- x + 1 est exécutée à chaque tour de la boucle la plus interne. Elle coûte 2 opérations (1 addition, 1 affectation).
5. Ligne 5 : retourner x -> 1 opération.

Le nombre total d'exécutions de la ligne 4 est $n\times n=n^2$.
Le coût total est donc :
$C(n)=1_{\text{(init x)}}+n\times n\times (2_{\text{(corps boucle)}})+1_{\text{(retour)}}$
$C(n)=2n^2+2$

Le coût de cet algorithme est quadratique. Si n double, le temps d'exécution est multiplié par quatre !

Si vous souhaitez aller plus loin, vous pouvez consulter les exercices Q1 à Q6 et leurs corrigés dans le document. C'est un excellent entraînement.

Conclusion

Aujourd'hui, nous avons mis en pratique la théorie de la leçon précédente en apprenant à disséquer un algorithme pour en estimer le coût.

Points clés à retenir :

• Une opération élémentaire a un coût constant (ex: affectation, addition, comparaison).
• L'estimation du coût d'un algorithme se fait en analysant sa structure :
  • Les coûts des instructions séquentielles s'additionnent.
  • Pour une boucle, on multiplie le nombre d'itérations par le coût du corps de la boucle.
  • Pour des boucles imbriquées, les nombres d'itérations se multiplient entre eux.
• Cette analyse nous donne une fonction de coût (ex: $4n+2$, $2n^2+2$) qui décrit précisément le nombre d'opérations en fonction de la taille des données n.

Et après ?

Vous avez peut-être remarqué qu'obtenir la fonction de coût exacte, comme $2n^2+2$, peut être un peu fastidieux. De plus, est-ce que le + 2 est vraiment important quand n vaut un million ?

La réponse est non. Ce qui compte vraiment, c'est le terme qui croît le plus vite, ici n². Dans la prochaine leçon, nous introduirons un outil essentiel pour simplifier tout cela : la notation Big O. Elle nous permettra de passer de "le coût est de $2n^2+2$" à "la complexité est $O(n^2)$", nous concentrant ainsi sur l'essentiel : l'ordre de grandeur de la croissance de l'algorithme.