structures de données – bases des algorithmes

L’algorithme est une procédure étape par étape, qui définit un ensemble de 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 plusieurs langages de programmation.,

du point de vue de la structure de données, voici quelques catégories importantes d’algorithmes −

• Search − algorithme pour rechercher un élément dans une structure de données.

• Tri − Algorithme pour trier les éléments dans un certain ordre.

• Insérez − 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.

• Supprimer − Algorithme pour supprimer un élément à partir d’une structure de données.

Caractéristiques d’un Algorithme

toutes les procédures peuvent être appelés un algorithme., Un algorithme doit avoir les caractéristiques suivantes −

• sans Ambiguïté − l’Algorithme doit être clair et sans ambiguïté. Chacune de ses étapes (ou phases), et leurs entrées/sorties doivent être claires et doivent conduire à une seule signification.

• Input − un algorithme doit avoir 0 entrées ou plus bien définies.

• sortie − un algorithme doit avoir au moins 1 sortie bien définie et doit correspondre à la sortie souhaitée.

• Finitude − Algorithmes doivent se terminer après un nombre fini d’étapes.,

• faisabilité − devrait être réalisable avec les ressources disponibles.

• indépendant − un algorithme doit avoir des directions étape par étape, qui doivent être indépendantes de tout code de programmation.

Comment Écrire un Algorithme?

Il n’existe pas de normes bien définies pour l’écriture d’algorithmes. Au contraire, c’est un problème et une ressource dépendante. 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 les boucles (do, for, while), le contrôle de flux (if-else), etc., Ces structures peuvent être utilisées pour écrire un algorithme.

nous écrivons des algorithmes pas à pas, mais ce n’est pas toujours le cas. L’écriture de l’algorithme est un processus et est exécutée après que le domaine du problème soit bien défini. Autrement dit, nous devrions 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.

problème-concevez un algorithme pour ajouter deux nombres et afficher le résultat.

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

Les algorithmes indiquent aux programmeurs comment coder le programme., Sinon, l’algorithme peut être écrite comme suit:

Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP

Dans la conception et l’analyse d’algorithmes, généralement la deuxième méthode est utilisée pour décrire un algorithme. Il 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 des numéros d’étape est facultative.

Nous concevons un algorithme pour obtenir une solution d’un problème donné. Un problème peut être résolu en plus de l’une des 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 solution la mieux adaptée.

analyse D’algorithme

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

• 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 l’implémentation.

• Un Postérieur de l’Analyse − C’est une analyse empirique d’un algorithme. L’algorithme sélectionné est implémenté à l’aide du langage de programmation. Ceci est ensuite exécuté sur la machine de l’ordinateur cible. Dans cette analyse, des statistiques réelles telles que le temps d’exécution et l’espace requis sont collectées.

Nous allons en apprendre davantage sur l’analyse des algorithmes a priori., L’analyse d’algorithme traite de l’exécution ou du temps d’exécution de diverses opérations impliquées. La durée d’exécution d’une opération peut être définie comme le nombre d’instructions informatiques exécutées par opération.

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,

• Facteur D’Espace − 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 d’exécution et/ou l’espace de stockage requis par l’algorithme en termes de n par la taille des données d’entrée.

complexité de L’espace

la complexité de l’espace 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 composants suivants −

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

• Une partie variable est un espace requis par les 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.,

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. voici un exemple simple qui tente d’expliquer le concept −

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

nous avons ici 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 constants et il sera multiplié en conséquence.,

complexité temporelle

la complexité temporelle d’un algorithme représente le temps requis par l’algorithme pour s’exécuter jusqu’à son achèvement. Les besoins en temps peuvent être définis comme une fonction numérique T (n), Où T(n) peut être mesuré comme le nombre d’étapes, à condition que chaque étape consomme un temps constant.

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