Python - Analyse des algorithmes

Analyse d'algorithme

L'efficacité d'un algorithme peut être analysée à deux étapes différentes, avant et après la mise en œuvre. Ce sont les suivants -

• A Priori Analysis- 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 l'implémentation.

• A Posterior Analysis- Il s'agit d'une analyse empirique d'un algorithme. L'algorithme sélectionné est implémenté en utilisant le langage de programmation. Ceci est ensuite exécuté sur la machine informatique cible. Dans cette analyse, des statistiques réelles telles que le temps de fonctionnement et l'espace requis sont collectées.

Complexité de l'algorithme

Supposer X est un algorithme et n est 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écident de l'efficacité de X.

• Time Factor - Le temps est mesuré en comptant le nombre d'opérations clés telles que des comparaisons dans l'algorithme de tri.

• Space Factor - L'espace est mesuré en comptant l'espace mémoire maximal requis par l'algorithme.

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

Complexité spatiale

La complexité spatiale d'un algorithme représente la quantité d'espace mémoire requise par l'algorithme dans son cycle de vie. L'espace requis par un algorithme est égal à la somme des deux composantes suivantes -

• Une partie fixe qui est un espace nécessaire pour stocker certaines données et variables, qui sont indépendantes de la taille du problème. Par exemple, les variables simples et les constantes utilisées, la taille du programme, etc.

• Une partie variable est un espace requis par des variables, dont la taille dépend de la taille du problème. Par exemple, allocation de mémoire dynamique, espace de pile de récursivité, etc.

La complexité spatiale S (P) de tout algorithme P est S (P) = C + SP (I), où C est la partie fixe et S (I) est la partie variable de l'algorithme, qui dépend de la caractéristique d'instance I. est un exemple simple qui tente d'expliquer le concept -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Ici, nous avons trois variables A, B et C et une constante. D'où S (P) = 1 + 3. Maintenant, l'espace dépend des types de données des variables données et des types de constantes et il sera multiplié en conséquence.

Complexité temporelle

La complexité temporelle d'un algorithme représente le temps nécessaire à l'algorithme pour s'exécuter jusqu'à son terme. Les exigences de temps peuvent être définies comme une fonction numérique T (n), où T (n) peut être mesurée comme le nombre d'étapes, à condition que chaque étape consomme un temps constant.

Par exemple, l'addition de deux entiers de n bits prend npas. Par conséquent, le temps de calcul total est T (n) = c ∗ n, où c est le temps pris pour l'addition de deux bits. Ici, nous observons que T (n) croît linéairement à mesure que la taille d'entrée augmente.