DataStructure And Algo
1.0.0
Les structures de données sont un moyen spécialisé d'organiser et de stocker des données dans les ordinateurs de telle manière que nous pouvons effectuer des opérations sur les données stockées plus efficacement. Les structures de données ont une portée large et diversifiée d'utilisation dans les domaines de l'informatique et du génie logiciel. Les structures de données sont utilisées dans presque tous les programmes ou systèmes logiciels qui ont été développés. De plus, les structures de données relèvent des principes fondamentaux de l'informatique et du génie logiciel. C'est un sujet clé en ce qui concerne les questions d'entrevue en génie logiciel. Par conséquent, en tant que développeurs, nous devons avoir une bonne connaissance des structures de données.
Un tableau est une structure de taille fixe, qui peut contenir des éléments du même type de données. Il peut s'agir d'un tableau d'entiers, d'un tableau de nombres à virgule flottante, d'un tableau de chaînes ou même d'un tableau de tableaux (tels que des tableaux bidimensionnels). Les tableaux sont indexés, ce qui signifie que l'accès aléatoire est possible.
L'insertion d'éléments d'un tableau et la suppression des éléments d'un tableau ne peut pas être effectué immédiatement car les tableaux sont fixés en taille. Si vous souhaitez insérer un élément sur un tableau, vous devrez d'abord créer un nouveau tableau avec une taille accrue (taille actuelle + 1), copiez les éléments existants et ajoutez le nouvel élément. Il en va de même pour la suppression avec un nouveau tableau de taille réduite.
Une liste liée est une structure séquentielle qui se compose d'une séquence d'éléments dans l'ordre linéaire qui sont liés les uns aux autres. Par conséquent, vous devez accéder aux données séquentiellement et un accès aléatoire n'est pas possible. Les listes liées fournissent une représentation simple et flexible des ensembles dynamiques.
Une pile est une structure LIFO (dernier dans la première sortie - l'élément placé en dernier est accessible au début) qui peut être couramment trouvé dans de nombreux langages de programmation. Cette structure est nommée «pile» car elle ressemble à une pile réelle - une pile de plaques.
Utilisé pour l'évaluation de l'expression (par exemple: un algorithme de shunting yard pour l'analyse et l'évaluation des expressions mathématiques). Utilisé pour implémenter les appels de fonction dans la programmation de récursivité.
Une file d'attente est une structure FIFO (premier dans la première sortie - l'élément placé au début peut être accessible au début) qui peut être couramment trouvé dans de nombreux langages de programmation. Cette structure est nommée «file d'attente» car elle ressemble à une file d'attente du monde réel - les gens qui attendent dans une file d'attente.
Utilisé pour gérer les threads en multithreading. Utilisé pour implémenter les systèmes de file d'attente (par exemple: files d'attente prioritaires).
Une table de hachage est une structure de données qui stocke les valeurs qui ont des clés associées à chacune d'elles. De plus, il prend en charge efficacement la recherche si nous connaissons la clé associée à la valeur. Par conséquent, il est très efficace dans l'insertion et la recherche, quelle que soit la taille des données.
L'adressage direct utilise le mappage individuel entre les valeurs et les touches lors du stockage dans un tableau. Cependant, il y a un problème avec cette approche lorsqu'il existe un grand nombre de paires de valeurs clés. Le tableau sera énorme avec autant de disques et peut être peu pratique ou même impossible à stocker, étant donné la mémoire disponible sur un ordinateur typique. Pour éviter ce problème, nous utilisons des tables de hachage .
Une fonction spéciale nommée la fonction de hachage (H) est utilisée pour surmonter le problème susmentionné dans l'adressage direct. Dans l'accès direct, une valeur avec la clé K est stockée dans l'emplacement k. En utilisant la fonction de hachage, nous calculons l'index de la table (emplacement) à laquelle se déroule chaque valeur. La valeur calculée à l'aide de la fonction de hachage pour une clé donnée est appelée valeur de hachage qui indique l'index de la table à laquelle la valeur est mappée.
Un arbre est une structure hiérarchique où les données sont organisées de manière hiérarchique et sont liées ensemble. Cette structure est différente d'une liste liée tandis que, dans une liste liée, les éléments sont liés dans un ordre linéaire. Divers types d'arbres ont été développés au cours des dernières décennies, afin de convenir à certaines applications et de respecter certaines contraintes. Quelques exemples sont l'arbre de recherche binaire, l'arbre B, la treap, l'arbre-noir rouge, l'arbre évasé, l'arbre AVL et l'arbre n-ary.
Un arbre de recherche binaire (BST), comme son nom l'indique, est un arbre binaire où les données sont organisées dans une structure hiérarchique. Cette structure de données stocke les valeurs dans l'ordre trié. Chaque nœud dans un arbre de recherche binaire comprend les attributs suivants.
Un arbre de recherche binaire présente une propriété unique qui la distingue des autres arbres. Cette propriété est connue sous le nom de Propriété ** Binary-Search-Tree **.
Un tas est un cas particulier d'un arbre binaire où les nœuds parents sont comparés à leurs enfants avec leurs valeurs et sont disposés en conséquence.
Les tas peuvent être de 2 types.
Un graphique se compose d'un ensemble fini de sommets ou de nœuds et d'un ensemble de bords reliant ces sommets.
L'ordre d'un graphique est le nombre de sommets dans le graphique. La taille d'un graphique est le nombre d'arêtes dans le graphique.
On dit que deux nœuds sont adjacents s'ils sont connectés les uns aux autres par le même bord.
Un graphique G est un graphique dirigé si tous ses bords ont une direction indiquant quel est le sommet de début et quel est le sommet final . Nous disons que (u, v) est un incident de ou quitte le sommet u et est incident ou entre en vertex v. Roucles auto-boucles: bords d'un sommet à lui-même.
Un graphique G est un graphique non dirigé si tous ses bords n'ont pas de direction. Il peut aller dans les deux sens entre les deux sommets.
Si un sommet n'est connecté à aucun autre nœud dans le graphique, il est considéré comme isolé .
Un trie est une structure de données de récupération d'informations en forme d'arbre dont les nœuds stockent les lettres d'un alphabet. Il est également connu comme un arbre numérique ou un arbre radix ou un arbre préfixe.
Trie est une structure de données efficace de recherche d'informations. À l'aide de Trie, les complexités de recherche peuvent être amenées à une limite optimale (longueur de clé). Si nous stockons les clés dans l'arbre de recherche binaire, un BST bien équilibré aura besoin de temps proportionnel à m * log n, où m est une longueur de chaîne maximale et n est un nombre de clés dans l'arbre. En utilisant Trie, nous pouvons rechercher la clé en temps o (m) .
1. TRIE STANDARD : Il s'agit d'un arbre ordonné comme la structure des données.
2. Trie comprimée : il est utilisé pour obtenir une optimisation de l'espace. Un trie compressée est une version avancée du Trie standard.
3. Suffix Trie : A Sufhel Trie est une version avancée du Trie compressé.
Avec Trie, nous pouvons insérer et trouver des chaînes en temps o (l) où l représente la longueur d'un seul mot. C'est évidemment plus rapide que BST. Ceci est également plus rapide que le hachage en raison de la façon dont il est mis en œuvre. Nous n'avons pas besoin de calculer aucune fonction de hachage. Un autre avantage de Trie est que nous pouvons facilement imprimer tous les mots dans l'ordre alphabétique qui n'est pas facilement possible avec le hachage.
La programmation dynamique est une technique qui divise les problèmes en sous-problèmes et enregistre le résultat à des fins futures afin que nous n'ayons plus besoin de calculer le résultat. Les sous-problèmes sont optimisés pour optimiser la solution globale est connue sous le nom de propriété de substructure optimale. L'utilisation principale de la programmation dynamique est de résoudre des problèmes d'optimisation. Ici, les problèmes d'optimisation signifient que lorsque nous essayons de découvrir la solution minimale ou maximale d'un problème. La programmation dynamique garantit pour trouver la solution optimale d'un problème si la solution existe.
Algorithme de complexité temporelle o (1) Recherche d'un élément spécifique dans un tableau, comme celui-ci, par exemple: imprimer (my_array [97]), quelle que soit la taille du tableau, un élément peut être recherché directement, il nécessite simplement une opération. (Ce n'est pas vraiment un algorithme, mais cela peut nous aider à comprendre comment fonctionne la complexité du temps.)
O (n) trouver la valeur la plus basse. L'algorithme doit effectuer des opérations dans un tableau avec n valeurs N pour trouver la valeur la plus basse, car l'algorithme doit comparer chaque valeur une fois.
O (n 2) le tri des bulles, le tri de sélection et le tri d'insertion sont des algorithmes avec cette complexité temporelle. La raison de leur complexité temporelle est expliquée sur les pages de ces algorithmes.
De grands ensembles de données ralentissent considérablement ces algorithmes. Avec juste une augmentation de N de 100 à 200 valeurs, le nombre d'opérations peut augmenter jusqu'à 30000!
O (n log n) L'algorithme QuickSort est plus rapide en moyenne que les trois algorithmes de tri mentionnés ci-dessus, O (n log n) étant la moyenne et non le pire des cas. Le pire des cas pour Quicksort est également O (n 2), mais c'est le temps moyen qui rend Quicksort si intéressant. Nous apprendrons Quicksort plus tard.
La référence est tirée de ce lien - Sourav Saini?
