Comment mesurer l'efficacité d'un algorithme ?

Le choix ou l'écriture d'un algorithme pour résoudre un problème, est basé sur un certain nombre de critères dont le plus important est le temps d'exécution. Un algorithme est d'autant plus efficace que son temps d'exécution est moindre. Ainsi, la notion d'efficacité d'un algoriithme est étroitement liée à son temps d'exécution. Dans cet article, nous allons voir comment faire pour montrer q'un algorithme est efficace.

Méthodes de mesure du temps d'exécution d'un algorithme

Il existe deux (02) méthodes pour mesurer le temps d'exécution d'un algorithme :

• la méthode expérimentale ou méthode empirique et
• la méthode analytique ou méthode théorique.

La méthode expérimentale

De manière générale, la méthode expérimentale consiste en trois (03) étapes :

• implémenter l'algorithme dans un langage de programmation donné ;
• exécuter le programme écrit sur différentes données d'entrées et,
• enregistrer le temps d'exécution exact (en microsecondes, en secondes ou en minutes) pour chaque donnée d'entrée.

Cependant, cette méthode n'est très faisable et présente certains inconvénients :
Le premier problème rencontré avec cette approche est que nous devons implémenter l'algorithme dans un langage de programmation particulier, et exécuter le programme obtenu sur un ordinateur donné. Dans ce cas, le temps d'exécution est dépendant du logiciel et du matériel utilisé pour implémenter et exécuter l'algorithme ; ce qui peut parfois conduire à de faux résultats. Par exemple, un algorithme médiocre pourrait s'exécuter en moins de temps qu'un bon algorithme s'il est exécuté sur un ordinateur puissant ou implémenté dans un langage de programmation performant. Ainsi, si nous voulons comparer deux algorithmes et déterminer lequel est meilleur, nous devons implémenter et exécuter les deux algorithmes dans un même environnement matériel et logiciel ; ce qui n'est pas toujours possible.

Le second problème avec la méthode expérimentale est que nous ne pouvons exécuter le programme que sur un nombre limité de donnés d'entrées, ce qui conduit souvent à ne pas prendre en compte certaines données sur lesquelles l'algorithme se comporte différemment. Ainsi, le nombre limité de données d'entrées utilisées pour exécuter le programme n'indiquera pas le comportement adéquat de l'algorithme.

Et enfin, le troisième problème avec la méthode expérimentale est que cette approche nécessite parfois beaucoup de temps, car certains algorithmes peuvent prendre des heures, des jours, voire des mois pour s'exécuter pour certaines données d'entrées ; ce qui rend cette approche infaisable dans ce genre de situation. La méthode expérimentale n'est donc pas faisable pour des algorithmes qui s'exécutent sur une longue période de temps.
Ainsi dans la pratique, à cause de ces limitations, la méthode expérimentale n'est pas utilisée pour mesurer le temps d'exécution d'un algorithme. À la place, la méthode analytique ou méthode théorique est utilisée.

La méthode analytique

Dans la méthode analytique, le temps d'exécution des algorithmes est analysé sur la base de la taille des données d'entrées. Cette méthode est également connue sous le nom d'analyse asymptotique. Dans cette méthode, nous ne calculons pas le temps d'exécution exact d'un algorithme, et par conséquent, il n'est pas nécessaire d'exécuter le programme. Ainsi, cette approche nous permet d'analyser le temps d'exécution des algorithmes, indépendamment des environnements matériel et logiciel. Cette méthode prend également en compte toutes les données d'entrées possibles. Dans la section suivante, nous parlerons plus en détails de la méthode analytique pour mesurer l'efficacité d'un algorithme.

Mesurer l'efficacité d'un algorithme : La méthode analytique ou analyse asymptotique

Mesurer l'efficacité d'un algorithme revient à calculer son temps d'exécution. Le temps d'exécution d'un algorithme dépend de la taille de la donnée d'entrée qui est généralement désignée par la lettre "n". En fonction du problème qu'on est entrain de résoudre, cette donnée d'entrée peut faire reférence à plusieurs choses. Par exemple, si nous rechechons un élément ou faisons le tri dans un tableau, alors la taille (nombre d'éléments) du tableau représente la taille de la donnée d'entrée de l'algorithme.

Si la taille de la donnée d'entrée est petite, alors l'algorithme prendra moins de temps pour s'exécuter, et si par contre la taille de la donnée d'entrée est grande, alors l'algorithme prendra plus de temps pour s'exécuter. Par exemple, un algorithme de tri prendra moins de temps pour trier 100 nombres et plus de temps pour 10 000 nombres. Ainsi, plus la taille de la donnée d'entrée augmente, plus le temps d'exécution croît également. en supposant donc que la taille de la donnée d'entrée d'un algorithme a doublé, de toute évidence, le temps d'exécution de cet algorithme va également augmenter. Dans ce cas, le temps d'exécution pourrait donc doubler, quadrupler ou devenir 10 foix ou 100 foix plus. Tout dépend de l'algorithme. C'est donc ce comportement de l'algorithme que nous allons étudier dans l'analyse asymptotique.

Donc fondamentalement, pour analyser un algorithme, nous allons étudier comment le temps d'exécution de cet algorithme croît selon que la taille de la donnée d'entrée augmente. Si le temps d'exécution d'un algorithme croît très rapidement en fonction de la taille de la donnée d'entrée, alors, cet algorithme ne sera pas considéré comme un algorithme efficace. Ainsi dans l'analyse asymptotique, le temps d'exécution exact importe peu ; le plus important est de savoir ce qui se passe lorsque la taille de la donnée d'entrée devient grande.

Imaginons un instant que nous avons 2 algorithmes : Algorithme A et Algorithme B pour résoudre un problème particulier. Soit n la taille de la donnée d'entrée.

Pour n = 2, le temps d'exécution des 2 algorithmes est le même, soit 4.

Pour n = 4, le temps d'exécution de l'Algorithme A est de 8, celui de l'algorithme B est 16.

Pour n = 8, le temps d'exécution de l'Algorithme A est de 16, celui de l'algorithme B est 64.

Pour n = 100, le temps d'exécution de l'Algorithme A est de 200, celui de l'algorithme B est 10 000.

Pour n = 1 000, le temps d'exécution de l'Algorithme A est de 2 000, celui de l'algorithme B est 1 000 000.

Pour n = 10 000, le temps d'exécution de l'Algorithme A est de 20 000, celui de l'algorithme B est 100 000 000.

Nous pouvons voir que le temps d'exécution de l'Algorithme B croît très rapidement en fonction de la taille de la donnée d'entrée. Ainsi, pour une taille de la donnée d'entrée plus grande, cet algorithme prendra plus de temps pour s'exécuter. Donc si nous devons choisir entre l'Algorithme A et l'Algorithme B, notre choix se portera de toute évidence sur l'Algorithme A, car l'Algorithme B devient très inefficace pour de grandes entrées.

Pour déterminer à quelle fréquence le temps d'exécution d'un algorithme croît, nous allons utilisé un outil mathématique appelé Notation Grand O dont nous allons parler dans la section suivante.

Notation Grand O et efficacité des algorithmes

La notation Grand O est l'outil mathématique le plus largement utilisé pour comparer l'efficacité des algorithmes. Cet outil nous permet d'analyser le comportement asymptotique d'une fonction pour savoir à quelle vitesse une fonction f(n) croît lorsque n devient grand. Cette notation examine la fréquence de croissance d'une fonction en la comparant avec quelques fonctions standards dont la fréquence de croissance est déjà connue. À présent, voyons la définition formelle de la notation Grand O.

Définition de la Notation Grand O

f(n) est O(g(n)) si et seulement s'il existe des constantes c et n₀ telles que :
f(n) <= c.g(n) pour tout n >= n₀

En gros, cette définition signifie que la fonction f ne va jamais croître plus vite que la fonction g pour des valeurs plus grandes de n. En d'autres termes, nous pouvons dire que la fonction g est une borne supérieure de la fonction f. Ici, f est considérée comme la fonction dont nous voulons examiner la fréquence de croissance, et g est la fonction dont la fréquence de croissance est déjà connue.

Exemples

Prenons quelques exemples pour mieux comprendre. Supposons que nous ayons la fonction suivante : f(n) = 5n + 4, et prenons g(n) = n. Vérifions maintenant si nous pouvons affirmer que f est de l'odre de g c'est-à-dire que f(n) ∈ g(n).

5n + 4 sera de l'ordre de n si nous pouvons déterminer deux constantes c et n₀ telles que :
5n + 4 <= c.n pour tout n >= n₀ 
Si nous prenons par exemple c = 6 et n₀ = 4, alors la définition de la Notation Grand O est satisfaite et nous pouvons affirmer que 5n + 4 est de l'ordre de n.

Démonstration :

Pour n = 4, c = 6 et n₀ = 4 :
5n + 4 <= c.n
5*4 + 4 <= 6*4
24 <= 24 (ce qui est vrai)

Pour n = 5, c = 6 et n0 = 4 :
5n + 4 <= c.n
5*5 + 4 <= 6*5
29 <= 30 (ce qui est vrai)

Remarque : 5n + 4 est de l'ordre de n est synonyme de 5n + 4 est O(n) et se note 5n + 4 ∈ O(n).

Les constantes c = 6 et n₀ = 4 ne sont pas uniques, et il peut y avoir plusieurs valeurs de c et n₀ qui peuvent être utilisées pour montrer que 5n + 4 est de l'ordre de n. Ces valeurs ne sont pas importantes car elles sont utilisées juste pour démontrer que la fonction f(n) = 5n + 4 est de l'ordre de n.

Pareillement, nous pouvons montrer que les fonctions suivantes sont de l'ordre de n :

• 21n + 2 ∈ O(n)
• n + 5 ∈ O(n)
• 102n + 1 ∈ O(n)
• 15n ∈ O(n)

À présent, soient les fonctions suivantes, f(n) = 3n² + 4n + 7 et g(n) = n². En choisissant les constatntes appropriées (par exemple c = 5 et n₀ = 6), nous pouvons montrer que 3n² + 4n + 7 ∈ O(n²) c'est-à-dire que 3n² + 4n + 7 <= 5n² pour tout n >= 6

Démonstration :

Pour n = 6, c = 5 et n0 = 6 :
3n² + 4n + 7 <= c.n²
3(6)² + 4*6 + 7 <= 5(6)²
139 <= 180 (ce qui est vrai)

Pareillement, nous pouvons montrer que les fonctions suivantes sont de l'ordre de n² :

• 5n² + 3n ∈ O(n²)
• n² + 5 ∈ O(n²)
• 9n² + 7n + 35 ∈ O(n²)

Dans la pratique, nous ne déterminerons pas l'ordre d'une fonction de cette manière. Il existe un certain ensemble de règles dérivés de la définition de la Notation Grand O que nous pouvons utiliser pour déterminer l'ordre d'une fonction. Découvrons à présent dans la section qui suit quelques fonctions standards qui sont généralement utilisées à la place de la fonction g.

Quelques fonctions asymptotiques communes

Nous avons vu dans la section précédente que la fréquence de croissance d'une fonction f est examinée en fournissant une borne supérieure déterminée par la fonction g. Ainsi pour cette fonction g, seules quelques formes de fonctions sont utilisées. Ces formes sont pour la plupart composées d'un seul terme exprimé en fonction de n avec pour coefficient 1. Ces fonctions sont classées dans le tableau ci-dessous par fréquence de croissance croissante :

Remarque : Un algorithme est plus efficace qu'un autre si sa fréquence de croissance est la moins importante. Par conséquent, un algorithme qui s'exécute en O(1) est le plus efficace et un algorithme qui s'exécute en O(n!) est le moins efficace.

Dans le tableau ci-dessous, nous avons des valeurs de quelques unes de ces fonctions pour différentes valeurs de n :

Nous pouvons voir à partir de ce tableau que certaines fonctions croissent plus vite que d'autres. Par exemple, la fréquence de croissance de la fonction n³ est plus importante que celle de la fonction n ou n log n. Ainsi, si nous avons 2 fonctions f1 et f2 telles que f1 ∈ O(n) et f2 ∈ O(n³), alors nous pouvons affirmer que la fréquence de croissance de la fonction f2 est plus importante que celle f1, car la fréquence de croissance de cette fonction n³ augmente plus vite que celle de n.

Remarque : Un algorithme est donc plus efficace qu'un autre si sa fréquence de croissance est la plus faible. Ceci indique que le temps d'exécution de cet algorithme va croître moins vite lorsque la taille de la donnée d'entrée va augmenter.

Conclusion

Dans cet article, nous avons vu deux méthodes pour mesurer le temps d'exécution d'un algorithme : la méthode expérimentale et la méthode analytique. La méthode expérimentale présente certaines limitations, ce qui fait donc de la méthode analytique la plus appropriée pour mesurer le temps d'exécution d'un algorithme. Ainsi, pour déterminer l'efficacité d'un algorithme, nous devons observer comment se comporte le temps d'exécution de l'algorithme lorsque la taille de la donnée d'entrée augmente. Nous avons également parlé de la notation Grand O qui est un outil mathématique utilisé pour comparer l'efficacité des algorithmes. Pour découvrir l'ensemble des règles utilisées pour déterminer l'ordre d'une fonction, veuillez consulter l'article sur "Comment déterminer l'ordre d'une fonction algorithmique ?"