Structures de données - Principes de base des algorithmes

L'algorithme est une procédure étape par étape, qui définit un ensemble d'instructions à exécuter dans un certain ordre pour obtenir la sortie souhaitée. Les algorithmes sont généralement créés indépendamment des langages sous-jacents, c'est-à-dire qu'un algorithme peut être implémenté dans plus d'un langage de programmation.

Du point de vue de la structure des données, voici quelques catégories importantes d'algorithmes -

Search - Algorithme pour rechercher un élément dans une structure de données.
Sort - Algorithme pour trier les éléments dans un certain ordre.
Insert - Algorithme pour insérer un élément dans une structure de données.
Update - Algorithme pour mettre à jour un élément existant dans une structure de données.
Delete - Algorithme pour supprimer un élément existant d'une structure de données.

Caractéristiques d'un algorithme

Toutes les procédures ne peuvent pas être appelées un algorithme. Un algorithme doit avoir les caractéristiques suivantes -

Unambiguous- L'algorithme doit être clair et sans ambiguïté. Chacune de ses étapes (ou phases) et leurs entrées / sorties doivent être claires et ne doivent conduire qu'à une seule signification.
Input - Un algorithme doit avoir 0 ou plus d'entrées bien définies.
Output - Un algorithme doit avoir une ou plusieurs sorties bien définies et doit correspondre à la sortie souhaitée.
Finiteness - Les algorithmes doivent se terminer après un nombre fini d'étapes.
Feasibility - Doit être réalisable avec les ressources disponibles.
Independent - Un algorithme devrait avoir des directions pas à pas, qui devraient être indépendantes de tout code de programmation.

Comment écrire un algorithme?

Il n'y a pas de normes bien définies pour l'écriture d'algorithmes. Il dépend plutôt du problème et des ressources. Les algorithmes ne sont jamais écrits pour prendre en charge un code de programmation particulier.

Comme nous savons que tous les langages de programmation partagent des constructions de code de base comme des boucles (do, for, while), flow-control (if-else), etc. Ces constructions communes peuvent être utilisées pour écrire un algorithme.

Nous écrivons des algorithmes étape par étape, mais ce n'est pas toujours le cas. L'écriture d'algorithme est un processus et est exécutée une fois que le domaine du problème est bien défini. Autrement dit, nous devons connaître le domaine du problème, pour lequel nous concevons une solution.

Exemple

Essayons d'apprendre l'écriture d'algorithmes en utilisant un exemple.

Problem - Concevez un algorithme pour ajouter deux nombres et afficher le résultat.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

Les algorithmes indiquent aux programmeurs comment coder le programme. Alternativement, l'algorithme peut être écrit comme -

Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Dans la conception et l'analyse d'algorithmes, la deuxième méthode est généralement utilisée pour décrire un algorithme. Cela permet à l'analyste d'analyser facilement l'algorithme en ignorant toutes les définitions indésirables. Il peut observer quelles opérations sont utilisées et comment le processus se déroule.

L'écriture step numbers, est facultatif.

Nous concevons un algorithme pour obtenir une solution à un problème donné. Un problème peut être résolu de plusieurs manières.

Par conséquent, de nombreux algorithmes de solution peuvent être dérivés pour un problème donné. L'étape suivante consiste à analyser les algorithmes de solution proposés et à mettre en œuvre la meilleure solution appropriée.

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.

Nous apprendrons l' analyse d'algorithme a priori . L'analyse des algorithmes traite de l'exécution ou du temps d'exécution des diverses 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

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, l'allocation de mémoire dynamique, l'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.