Introduction
Avoir une bonne représentation de la performance d’un algorithme est un élément important pour un programmeur et, malheureusement, évaluer cette performance est généralement très difficile et peu intuitif. Il ne suffit pas de diminuer le nombre de lignes de code pour augmenter la performance. En fait, il arrive souvent que des algorithmes plus performants soient également plus gros et plus complexes à comprendre.
Les bases
Par performance d’un algorithme, on entend la balance entre la rapidité d’exécution de l’algorithme par rapport à l’espace mémoire utilisé.
En effet, un algorithme bien conçu devra décider pourra stocker une grande quantité de valeurs en mémoire (ce que nous appelons une cache) afin d’éviter de traiter ces valeurs, ce qui fait un algorithme plus rapide. Inversement, au lieu de stocker des valeurs en mémoire, il est souvent possible de les recalculer au besoin, ce qui augmente la performance mémoire, mais diminue la vitesse.
Par contre, avant de balancer la performance mémoire et la vitesse d’exécution d’un algorithme, il faut s’assurer que l’algorithme est optimal. Le calcul permettant de mesurer la performance (particulièrement la vitesse) d’un algorithme est appelé la complexité algorithmique.
La complexité algorithmique
La complexité algorithmique permet le calcul et la notation de la performance d’un algorithme. En d’autres mots, ça nous permet d’avoir une mesure permettant de comparer la performance de différents algorithmes.
La complexité d’un problème
Un algorithme est une mécanique permettant de résoudre un problème (peu importe le type de problème). Par exemple, il y a des algorithmes permettant de ressourdre les problèmes: Trouver un élément dans une structure (liste, arbre, etc.), calculer une moyenne, ressourdre un Rubiks cube, calculer le chemin le plus rapide pour partir de ma résidence jusqu’à mon travail, etc.
On dit que tous les problèmes ont une complexité. C’est-à-dire une performance optimale permettant de résoudre le problème. Cette complexité est un idéal et n’est pas toujours connue. L’objectif d’un programmeur est de trouver un algorithme qui a une complexité qui se rapproche le plus de la complexité du problème.
La complexité d’un algorithme
Il est important de comprendre que, de base, ce qui augmente la complexité d’un algorithme, c’est les boucles de cet algorithme. Par exemple, l’algorithme suivant (en Java):
public int addition(int aValeur1, int aValeur2) {
return aValeur1 + aValeur2;
}
est plus performant que l’algorithme suivant:
public int addition(int aValeur1, int aValeur2) {
int lRetour = aValeur1;
for (int i = 0; i < aValeur2; i = i + 1){
lRetour = lRetour + 1;
}
return lRetour;
}
La notation O
On note la complexité d’un algorithme avec la notation O(complexité). Par exemple, un algorithme peut être 0(1), O(n), O(log(n)), O(n^2), etc. Le « n » dans les notations représente le nombre de valeurs à traiter. Par exemple, dans les deux exemples précédents, le premier exemple (l’addition avec une seule ligne de retour) est O(2) puisqu’il doit faire une addition et une assignation, et le second exemple (l’addition avec une boucle) est O(2*aValeur2 + 2), le « 2*aValeur2 » correspondant à l’addition et l’assignation dans la boucle et le « + 2 » correspondant aux 2 assignations à l’extérieur de la boucle.
Le principe d’ordre de grandeur
Il est important de comprendre que ce qui nous intéresse dans la complexité algorithmique, c’est l’ordre de grandeur de cette complexité. L’ordre de grandeur se calcule toujours par rapport à une variable. Ainsi, les multiplications de constante ne sont pas prises en compte. Par exemple, les ordres de complexité suivants sont tous équivalents:
O(2) = O(1000000) = O(-345) = O(1)
O(2*n) = O(1000000*n) = O(-543*n) = O(n)
O(2*n²) = O(1000000*n²) = O(-923*n²) = O(n²)
O(2*n³) = O(1000000*n³) = O(-923*n³) = O(n³)
O(2*log(n)) = O(log(2*n)) = O(log(1000000*n)) = O(log(n))
Il est important de voir que les derniers éléments de chaque ligne d’égalités est comment on note cet ordre de complexité. Ainsi, dans les exemples précédents, le premier exemple (l’addition avec une seule ligne de retour) doit être noté O(1) et non O(2) comme précisé plus haut.
Également, l’ordre de grandeur de complexité algorithmique ignore les additions de polynôme contenant des indéterminés identiques. Seul l’indéterminé ayant le plus haut degré est gardé. Par exemple, voici des ordres de complexité qui sont équivalents:
O(3n + 5) = O(n)
O(3*n + 5*n² + n + 1000) = O(n² + log(n)) = O(n²)
O(n*log(n) + log(n) + log(log(n))) = O(n*log(n))
Encore une fois, le dernier élément des égalités représente comment nous devrions noter les ordres algorithmiques.
Ainsi, dans les exemples précédents, le second exemple (le addition avec une boucle pour calculer le résultat), doit être noté O(aValeur2) et non O(2* aValeur2 + 2) comme précisé plus haut.
Comment calculer l’ordre de complexité d’un algorithme
Les techniques de calcul d’ordre de complexité algorithmique sont hors des notions à voir dans ce cours. Néanmoins, je crois qu’il est important d’avoir une bonne compréhension de ce qui cause les ordres de complexité classique.
L’ordre de complexité algorithmique correspond au nombre maximal de fois que seraient exécutés des capteurs d’exécution qui seraient placés entre chaque instruction de l’algorithme. Par exemple, prenons l’algorithme suivant:
public void afficherInformations() {
System.out.println("Prenom: Boba");
System.out.println("Nom: Fett");
System.out.println("Age: 12 ans");
}
En plaçant les capteurs entre chaque instruction, on obtiendrait:
public void afficherInformations() {
Capteur1
System.out.println("Prenom: Boba");
Capteur2
System.out.println("Nom: Fett");
Capteur3
System.out.println("Age: 12 ans");
Capteur4
}
Si on exécutait cet algorithme, chaque capteur s’exécuterait une seule fois. On obtient donc que cet algorithme est d’ordre O(1).
Voici un autre exemple:
public int calculerMoyenne(List<Integer> aValeurs) {
int lSomme = 0;
for (Integer laValeur : aValeurs) {
lSomme = lSomme + laValeur.intValue();
}
return lSomme / aValeurs.size();
}
Si on ajoute les capteurs dans cet algorithme, on obtient:
public int calculerMoyenne(List<Integer> aValeurs) {
Capteur1
int lSomme = 0;
Capteur2
for (Integer laValeur : aValeurs) {
Capteur3
lSomme = lSomme + laValeur.intValue();
Capteur4
}
Capteur5
return lSomme / aValeurs.size();
Capteur6
}
Ici, si on exécute cet algorithme avec des listes différentes, nous remarquons rapidement que les capteurs ayant les plus d’exécution sont les capteurs 3 et 4 et que leurs nombres d’exécutions correspondent à la taille de la liste reçue en entrée. On obtient donc la complexité algorithmique O(n) ou n=aValeurs.size().
Voici un autre exemple:
public int valeurMaximale(List<List<Integer>> aMatrice) {
int lResultat = aMatrice.get(0).get(0).intValue();
for (List<Integer> laLigne : aMatrice) {
for (Integer laValeur : laLigne) {
if (lResultat < laValeur.intValue()) {
lResultat = laValeur.intValue();
}
}
}
return lResultat;
}
Si on ajoute nos capteurs, on obtient:
public int valeurMaximale(List<List<Integer>> aMatrice) {
Capteur1
int lResultat = aMatrice.get(0).get(0).intValue();
Capteur2
for (List<Integer> laLigne : aMatrice) {
Capteur3
for (Integer laValeur : laLigne) {
Capteur4
if (lResultat < laValeur.intValue()) {
Capteur5
lResultat = laValeur.intValue();
Capteur6
}
Capteur7
}
Capteur8
}
Capteur9
return lResultat;
Capteur10
}
Si on exécute cet algorithme, on obtient que les capteurs les plus exécutés soient les capteurs 4 à 7. Leurs nombres d’exécutions est de O(m*n) ou m=nombre de ligne de la matrice et n=nombre de colonne de la matrice.
Ce résultat est un peu embêtant parce qu’il correspond à un ordre de complexité quadratique(ou O(n²)), mais il est difficile de s’en rendre compte seulement en regardant la notation O(n*m). Par contre, puisque c’est simplement l’ordre de complexité du pire cas qui nous importe et non la complexité réelle, nous pouvons indiquer quelque chose comme O(n²) ou n=Max(Ligne et colonne de la matrice).
Résumons
On voit qu’on peut, instinctivement (sans placer de capteur), déduire l’ordre de complexité d’un algorithme en regardant la profondeur des boucles. Bien entendu, il y a des subtilités, mais généralement, un algorithme sans boucle est O(1), un algorithme avec une boucle (ou plusieurs boucles sécancielles) sont O(n), un algorithme avec une boucle imbriquée dans une autre est O(n²), un algorithme avec une boucle imbriquée dans une autre qui est à son tour imbriquée dans une autre est O(n³), etc.
Vous devez faire attention parce que parfois, les boucles peuvent être cachées dans des sous-routines. Elles doivent également être prises en compte dans le calcul d’ordre de complexité algorithmique.
Le pire cas
Lorsque nous cherchons la complexité d’un algorithme, nous nous intéressons au pire cas possible dans cet algorithme. Par exemple, si nous faisons un algorithme effectuant une recherche dans une liste, il est inutile de continuer l’algorithme si l’élément a été trouvé. Il serait donc possible de sortir de l’algorithme bien avant d’avoir terminé la recherche et de cette manière, rendre l’algorithme plus performant. Par contre, lorsqu’on calcule l’ordre de complexité algorithmique, on évalue le pire cas. Dans l’exemple de la recherche dans une liste, le pire cas correspond au fait que l’élément est trouvé à la dernière cellule de la liste qui est vérifiée (ou encore pire, l’élément n’est pas trouvé).
Pour aller plus loin
Il est à noter qu’il existe des algorithmes d’ordre logarithmique (avec ou sans multiplicateur variable). Par exemple, il y a des algorithmes d’ordre O(log(n)), d’autres d’ordre O(n*log(n)), d’autre d’ordre O(n²*log(n)), O(log(log(n))), etc. Il s’agit généralement d’algorithme récursif de type diviser pour régner si vous voulez voir à quoi ça ressemble (voir par exemple le tri fusion qui est O(n*log(n))). Savoir ordonner ces ordres de grandeur est important. Donc, voici une liste comparative non exhaustive qui pourrait vous être utile:
O(p^n) > O(n³*log(n)) > O(n³*log(log(n))) > O(n³) > O(n²*log(n)) >
O(n²*log(log(n))) > O(n²) > O(n*log(n)) > O(n*log(log(n))) > O(n) >
O(log(n)) > O(log(log(n))) > O(1)
Le « p » indiqué dans O(p^n) représente une constante entière p > 1.
Auteur: Louis Marchand
Sauf pour les sections spécifiées autrement, ce travail est sous licence Creative Commons Attribution 4.0 International.