Complexité temporelle : Évaluer l'efficacité des algorithmes

Introduction

Dans la leçon précédente, nous avons comparé "intuitivement" l'efficacité des algorithmes de recherche et de tri. Nous avons vu que la recherche dichotomique est beaucoup plus rapide que la recherche linéaire sur de grands tableaux, et que certains tris sont plus performants que d'autres selon la situation.

Cependant, se fier à l'intuition ou à des tests sur une machine spécifique ne suffit pas. Deux ordinateurs différents donneront des temps d'exécution différents pour le même algorithme. Comment peut-on alors comparer des algorithmes de manière objective et universelle ?

L'objectif de cette leçon est de répondre à cette question en vous apprenant à définir la complexité temporelle et à comprendre son importance pour évaluer l'efficacité d'un algorithme. C'est la première étape pour maîtriser l'art de choisir le "bon" algorithme, une compétence essentielle pour écrire du code qui est non seulement correct, mais aussi performant – un pilier du "clean code" que vous visez.

1. Qu'est-ce que la Complexité Algorithmique ?

Commençons par une clarification importante : en informatique, le mot "complexité" ne signifie pas "difficile à comprendre". Un algorithme peut être très simple à écrire mais avoir une complexité très élevée, c'est-à-dire être très lent.

La complexité algorithmique est une mesure des ressources qu'un algorithme consomme. On distingue principalement deux types de complexité :

1. La complexité temporelle : Elle mesure le temps d'exécution de l'algorithme.
2. La complexité spatiale : Elle mesure l'espace mémoire utilisé par l'algorithme.

Bien que la complexité spatiale soit importante, la complexité temporelle est souvent le facteur le plus critique. C'est sur celle-ci que nous nous concentrerons.

Pour obtenir une définition formelle et bien comprendre les bases, je vous invite à lire les premières sections du document suivant.

Pour résumer et souligner les points les plus importants de cette lecture :

• La complexité temporelle est une information sur le temps d'exécution liée au volume de données à traiter, que l'on note généralement n.
• Cette mesure est indépendante des caractéristiques de la machine (processeur, mémoire) et du langage de programmation. C'est une propriété de l'algorithme lui-même.
• Le volume de données n peut représenter différentes choses selon le problème : la taille d'un tableau, la valeur d'un nombre, la longueur d'une chaîne de caractères, etc.

Le fait que cette mesure soit indépendante du matériel est fondamental. Cela nous permet de dire qu'un algorithme A est intrinsèquement plus efficace qu'un algorithme B, peu importe si on les exécute sur un superordinateur ou sur un vieux PC.

2. Comment Mesurer la Complexité Temporelle ?

Puisque nous ne mesurons pas le temps en secondes, comment procédons-nous ? La méthode consiste à compter le nombre d'opérations élémentaires que l'algorithme exécute.

Une opération élémentaire est une action si simple qu'on peut supposer qu'elle prend un temps constant et négligeable.

Le document suivant vous donnera la liste de ce que l'on considère comme des opérations élémentaires.

Les opérations élémentaires incluent donc :

• Les affectations de variables (ex: x <- 5)
• Les opérations arithmétiques (+, -, *, /)
• Les comparaisons (<, >, ==)
• L'accès à un élément d'un tableau (ex: T[i])

Exemple Pratique : Comptons les opérations !

Pour rendre cela concret, analysons un algorithme simple qui calcule la somme des éléments d'un tableau. C'est un excellent exercice pratique pour vous familiariser avec ce décompte.

Reprenons ensemble cette analyse. Soit n la longueur du tableau E.

Algorithme somme(E)

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

3.  `s <- s + E.tab[i]`
   

4. retourner s

Décompte des opérations :

• Ligne 1 : s <- 0. C'est 1 opération d'affectation.
• Ligne 2 (la boucle pour) :
  • Avant la boucle : i <- 0 et un premier test i <= n-1. C'est 2 opérations.
  • À chaque passage dans la boucle (il y en a n) :
    • Ligne 3 : s + E.tab[i] est une addition, et s <- ... est une affectation. Total : 2 opérations.
    • Maintenance de la boucle (cachée dans le pour) : i <- i + 1 (incrémentation) et i <= n-1 (test). Total : 2 opérations.
• Ligne 4 : retourner s. C'est 1 opération.

Calcul total du nombre d'opérations :
Le coût total, appelons-le $C(n)$, est la somme de toutes ces opérations :
$C(n)=1_{\text{(init s)}}+2_{\text{(init boucle)}}+n\times (2_{\text{(corps boucle)}}+2_{\text{(maint. boucle)}})+1_{\text{(retour)}}$
$C(n)=1+2+n\times 4+1$
$C(n)=4n+4$

Nous avons trouvé une fonction mathématique, $C(n)=4n+4$, qui nous donne le nombre exact d'opérations que cet algorithme effectue pour un tableau de taille n. C'est ce qu'on appelle la fonction de coût de l'algorithme.

3. L'Importance de la Complexité : La Croissance

Pourquoi se donner la peine de calculer une formule comme $4n+4$ ? Pour comprendre l'importance du résultat, regardons ce qui se passe quand n devient très grand.

• Si n = 10, $C(10)=4\times 10+4=44$ opérations.
• Si n = 1 000 000, $C(1000000)=4\times 1000000+4=4000004$ opérations.

Quand n est très grand, le + 4 à la fin devient complètement insignifiant. Ce qui compte vraiment, c'est le terme 4n. Il nous dit que le nombre d'opérations croît de manière proportionnelle (linéaire) à la taille des données. Si on double n, on double à peu près le temps d'exécution.

Maintenant, imaginez un autre algorithme (moins bon) qui trierait le tableau avec une fonction de coût de, disons, $2n^2+5n+10$.

• Si n = 10, le coût est de $2\times 100+5\times 10+10=260$ opérations.
• Si `n = 1 000), le coût est de $2\times 1000000+5\times 1000+10=2005010$ opérations.
  Le temps d'exécution explose ! Il croît de manière quadratique.

Le graphique suivant illustre magnifiquement l'impact de ces différents "ordres de croissance".

Ce graphique est la raison pour laquelle la complexité est si importante. Il montre que le choix d'un algorithme avec une "bonne" complexité (comme log n ou n) n'est pas une simple optimisation : c'est ce qui détermine si un problème est soluble en pratique pour de grandes quantités de données. Un algorithme en n² ou 2^n peut devenir inutilisable très rapidement.

Conclusion

Aujourd'hui, nous avons posé les fondations d'un des concepts les plus importants en algorithmique.

Points clés à retenir :

• La complexité temporelle est une mesure objective de l'efficacité d'un algorithme.
• Elle est exprimée en fonction de la taille des données d'entrée n et est indépendante de la machine ou du langage.
• On la mesure en comptant le nombre d'opérations élémentaires pour obtenir une fonction de coût (ex: $4n+4$).
• L'importance de la complexité réside dans la croissance du nombre d'opérations quand n augmente. Une mauvaise complexité peut rendre un algorithme inutilisable pour de grandes données.

Et après ?

Nous avons vu qu'une fonction de coût comme $4n+4$ nous informe que la croissance est linéaire. Cependant, les constantes (le 4 devant n et le + 4) sont souvent complexes à calculer et, comme nous l'avons vu, peu importantes pour comprendre le comportement global de l'algorithme.

Dans la prochaine leçon, nous allons introduire une notation qui nous permet de nous débarrasser de ces détails et de nous concentrer sur l'essentiel : l'ordre de croissance. C'est la fameuse notation "Big O", que vous avez déjà aperçue sur les graphiques (O(n), O(log n), etc.). C'est l'outil standard de l'industrie pour discuter et comparer l'efficacité des algorithmes.