Analyse d'Algorithmes : Efficacité et Complexité
Classé dans Informatique
Écrit le en 
français avec une taille de 3,46 KB
Il existe plusieurs façons de résoudre un problème.
Comment peut-on choisir entre elles ? Il y a généralement deux objectifs dans la conception de programmes informatiques :
- La conception d'un algorithme qui est facile à comprendre, à coder et à déboguer (*Software Engineering*).
- La conception d'un algorithme qui permet une utilisation efficace des ressources informatiques (analyse et conception d'algorithmes).
L'analyse d'algorithmes permet de mesurer la difficulté d'un problème et d'évaluer l'efficacité d'un algorithme.
Vous ne pouvez pas mesurer le temps en secondes, car il n'y a pas d'ordinateur standard de référence. Au lieu de cela, on mesure le nombre d'opérations de base ou élémentaires.
Les opérations de base sont effectuées par l'ordinateur en un temps borné par une constante, par exemple :
- Les opérations arithmétiques de base
- La répartition des types prédéfinis
- Les sauts (appels à des fonctions, des procédures et retour)
- Les comparaisons logiques
- Les structures d'accès de base (vecteurs et matrices)
Il est possible d'étudier la complexité d'un algorithme basé uniquement sur un petit ensemble de phrases, par exemple, celles qui influent sur l'environnement d'exécution.
Pour mesurer le temps d'exécution d'un algorithme, il existe plusieurs méthodes.
Certaines d'entre elles sont :
a) Benchmarking
La technique de *benchmarking* est considérée comme une collection d'entrées qui représente une charge de travail typique d'un programme.
b) Le profilage
Le profilage consiste à associer à chaque instruction d'un programme un nombre qui représente la fraction du temps total nécessaire pour exécuter cette instruction particulière. Une des techniques les plus connues (et informelle) est la règle 90-10, qui stipule que 90% du temps d'exécution est passé à 10% du code.
c) Analyse
L'analyse consiste à regrouper les entrées en fonction de leur taille, et à estimer le temps d'exécution des entrées du programme de cette taille, T(n). Cette technique est à étudier dans le cours.
Ainsi, le temps d'exécution peut être défini comme une fonction de l'entrée. On note T(n) le temps d'exécution d'un algorithme pour une entrée de taille n.
L'objectif principal de l'analyse des algorithmes réside dans la façon dont le temps d'exécution augmente lorsque la taille de l'entrée augmente. C'est l'efficacité asymptotique de l'algorithme. Elle est appelée "asymptotique", car elle analyse le comportement des fonctions dans la limite, c'est-à-dire, son taux de croissance.
La notation asymptotique est décrite par une fonction dont le domaine est les nombres naturels (N), estimée à partir du temps d'exécution ou de l'espace mémoire d'algorithmes basés sur la longueur de l'entrée. On considère asymptotiquement les fonctions non négatives.
La notation asymptotique capture le comportement de la fonction pour les grandes valeurs de N.
Les notations ne sont pas à charge sur les trois cas déjà vus, c'est pourquoi une notation qui détermine le pire des cas peut être présente dans une ou dans toutes les situations.