Analyse des algorithmes

L'efficacité d'un algorithme peut être analysée à deux stades différents, avant et après sa mise en œuvre. Elles sont les suivantes :

• Analyse a priori : Il s'agit d'une analyse théorique d'un algorithme. L'efficacité d'un algorithme est mesurée en supposant que tous les autres facteurs, par exemple la vitesse du processeur, sont constants et n'ont aucun effet sur la mise en œuvre.
• Analyse a posteriori : Il s'agit d'une analyse empirique d'un algorithme. L'algorithme sélectionné est mis en œuvre à l'aide d'un langage de programmation. Il est ensuite exécuté sur la machine informatique cible. Dans cette analyse, les statistiques réelles, telles que le temps d'exécution et l'espace requis, sont collectées.

Complexité de l'algorithme

Supposons que X soit un algorithme et que n soit la taille des données d'entrée. Le temps et l'espace utilisés par l'algorithme X sont les deux principaux facteurs qui déterminent l'efficacité de X.

• Facteur temps : Le temps est mesuré en comptant le nombre d'opérations clés telles que les comparaisons dans l'algorithme de tri.
• Facteur espace : L'espace est mesuré en comptant l'espace mémoire maximum requis par l'algorithme.

La complexité d'un algorithme f(n) donne le temps d'exécution et/ou l'espace de stockage requis par l'algorithme en fonction de n, la taille des données d'entrée.

Complexité de l'espace