Analyse d’algorithme
L’analyse de l’efficacité d’un algorithme peut être effectuée à deux stades différents, avant la mise en œuvre et après la mise en œuvre, comme
Analyse a priori – Elle est définie comme l’analyse théorique d’un algorithme. L’efficacité de l’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.
Une analyse a posteriori – Elle est définie comme l’analyse empirique d’un algorithme. L’algorithme choisi est mis en œuvre à l’aide d’un langage de programmation. Ensuite, l’algorithme choisi est exécuté sur la machine informatique cible. Dans cette analyse, les statistiques réelles comme le temps d’exécution et l’espace nécessaire sont collectées.
L’analyse de l’algorithme est traitée avec l’exécution ou le temps d’exécution des différentes opérations impliquées. Le temps d’exécution d’une opération peut être défini comme le nombre d’instructions informatiques exécutées par opération.
Complexité de l’algorithme
Supposons que X soit traité comme un algorithme et que N soit traité comme la taille des données d’entrée, le temps et l’espace mis en œuvre par l’algorithme X sont les deux principaux facteurs qui déterminent l’efficacité de X.
Facteur temps – Le temps est calculé ou mesuré en comptant le nombre d’opérations clés telles que les comparaisons dans l’algorithme de tri.
Facteur espace – L’espace est calculé ou mesuré en comptant l’espace mémoire maximal requis par l’algorithme.
La complexité d’un algorithme f(N) fournit le temps d’exécution et / ou l’espace de stockage nécessaire à l’algorithme par rapport à N comme taille des données d’entrée.
Complexité spatiale
La complexité spatiale d’un algorithme représente la quantité d’espace mémoire nécessaire à l’algorithme dans son cycle de vie.
L’espace nécessaire à un algorithme est égal à la somme des deux composantes suivantes
Une partie fixe qui est un espace requis pour stocker certaines données et variables (c’est-à-dire les variables et constantes simples, la taille du programme, etc.), qui ne dépendent pas de la taille du problème.
Une partie variable est un espace requis par les variables, dont la taille dépend totalement de la taille du problème. Par exemple, l’espace de la pile de récursion, l’allocation de mémoire dynamique, etc.
La complexité spatiale S(p) de tout algorithme p est S(p) = A + Sp(I) Où A est traité comme la partie fixe et S(I) est traité comme la partie variable de l’algorithme qui dépend de la caractéristique d’instance I. Voici un exemple simple qui tente d’expliquer le concept
Algorithme
SUM(P, Q)Step 1 - STARTStep 2 - R ← P + Q + 10Step 3 - Stop
Ici nous avons trois variables P, Q et R et une constante. Par conséquent, S(p) = 1+3. Maintenant, l’espace dépend des types de données des types constants et variables donnés et il sera multiplié en conséquence.
Complexité temporelle
La complexité temporelle d’un algorithme est la représentation de la quantité de temps nécessaire à l’algorithme pour s’exécuter jusqu’à la fin. Les besoins en temps peuvent être dénotés ou définis comme une fonction numérique t(N), où t(N) peut être mesuré comme le nombre d’étapes, à condition que chaque étape prenne un temps constant.
Par exemple, dans le cas de l’addition de deux entiers de n bits, N étapes sont effectuées. Par conséquent, le temps de calcul total est t(N) = c*n, où c est le temps consommé pour l’addition de deux bits. Ici, on observe que t(N) croît linéairement lorsque la taille de l’entrée augmente.
.