dsa.js data structures algorithms javascript
2.7.6
Il s'agit des implémentations de codage du livre DSA.js et du dépôt du package NPM.
Dans ce référentiel, vous pouvez retrouver l'implémentation d'algorithmes et de structures de données en JavaScript. Ce matériel peut être utilisé comme manuel de référence pour les développeurs, ou vous pouvez actualiser des sujets spécifiques avant un entretien. Vous pouvez également trouver des idées pour résoudre les problèmes plus efficacement.
Vous pouvez cloner le dépôt ou installer le code depuis NPM :
npm install dsa.jset ensuite vous pouvez l'importer dans vos programmes ou CLI
const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;Pour une liste de toutes les structures de données et algorithmes disponibles, consultez index.js.
Les algorithmes sont une boîte à outils essentielle pour tout programmeur.
Vous devrez faire attention à l'exécution des algorithmes lorsque vous devrez trier des données, rechercher une valeur dans un grand ensemble de données, transformer des données, adapter votre code à de nombreux utilisateurs, pour n'en nommer que quelques-uns. Les algorithmes ne sont que l'étape que vous suivez pour résoudre un problème, tandis que les structures de données sont l'endroit où vous stockez les données pour une manipulation ultérieure. Les deux combinés créent des programmes.
Algorithmes + Structures de données = Programmes.
La plupart des langages de programmation et des bibliothèques fournissent en effet des implémentations pour les structures de données et les algorithmes de base. Cependant, pour utiliser correctement les structures de données, vous devez connaître les compromis nécessaires pour choisir le meilleur outil pour le travail.
Ce matériel va vous apprendre à :
Tout le code et les explications sont disponibles sur ce dépôt. Vous pouvez parcourir les liens et les exemples de code du (dossier src). Cependant, les exemples de code en ligne ne sont pas développés (en raison des limitations asciidoc de Github), mais vous pouvez suivre le chemin et voir l'implémentation.
Remarque : Si vous préférez consommer les informations de manière plus linéaire, le format livre vous conviendrait mieux.
Les sujets sont divisés en quatre catégories principales, comme vous pouvez le voir ci-dessous :
Des pépites d’informatique sans tout le charabia. (Cliquez pour agrandir)
Des pépites d’informatique sans tout le charabia
Apprenez à calculer le temps d'exécution à partir d'exemples de code
Apprenez à comparer des algorithmes en utilisant la notation Big O. (Cliquez pour agrandir)
Apprenez à comparer des algorithmes en utilisant la notation Big O.
Comparaison d'algorithmes utilisant la notation Big O
Disons que vous souhaitez rechercher les doublons sur un tableau. En utilisant la notation Big O, nous pouvons comparer différentes solutions qui résolvent le même problème mais qui présentent une énorme différence dans le temps qu'il faut pour le faire.
- Solution optimale utilisant une carte
- Trouver des doublons dans un tableau (approche naïve)
8 exemples pour expliquer avec du code comment calculer la complexité temporelle. (Cliquez pour agrandir)
8 exemples pour expliquer avec du code comment calculer la complexité temporelle
Complexités temporelles les plus courantes
Graphique de complexité temporelle
Comprenez les tenants et les aboutissants des structures de données les plus courantes. (Cliquez pour agrandir)
Comprendre les tenants et les aboutissants des structures de données les plus courantes
Tableaux : intégrés dans la plupart des langages, ils ne sont donc pas implémentés ici. Complexité temporelle du tableau
Liste chaînée : chaque nœud de données a un lien vers le suivant (et le précédent). Codes | Complexité temporelle des listes liées
File d'attente : les données circulent selon le principe "premier entré, premier sorti" (FIFO). Codes | Complexité du temps d'attente
Pile : les données circulent selon le principe "dernier entré, premier sorti" (LIFO). Codes | Complexité du temps de pile
Quand utiliser un tableau ou une liste chaînée. Connaissez les compromis. (Cliquez pour agrandir)
Quand utiliser un tableau ou une liste chaînée. Connaître les compromis
Utilisez des tableaux lorsque…
- Vous devez accéder rapidement aux données dans un ordre aléatoire (à l’aide d’un index).
- Vos données sont multidimensionnelles (par exemple, matrice, tenseur).
Utilisez les listes liées lorsque :
- Vous accéderez à vos données de manière séquentielle.
- Vous souhaitez économiser de la mémoire et allouer de la mémoire uniquement selon vos besoins.
- Vous voulez un temps constant pour supprimer/ajouter des extrêmes de la liste.
- lorsque l'exigence de taille est inconnue - avantage de taille dynamique
Créez une liste, une pile et une file d'attente. (Cliquez pour agrandir)
Créez une liste, une pile et une file d'attente à partir de zéro
Créez l'une de ces structures de données à partir de zéro :
- Liste liée
- Empiler
- File d'attente
Comprenez l’une des structures de données les plus polyvalentes de toutes : les Hash Maps. (Cliquez pour agrandir)
Cartes de hachage
Découvrez comment mettre en œuvre différents types de cartes tels que :
- Carte de hachage
- ArbreCarte
Découvrez également la différence entre les différentes implémentations de Maps :
HashMapest plus efficace en termes de temps. UnTreeMapest plus économe en espace.- La complexité de la recherche
TreeMapest O(log n) , tandis qu'unHashMapoptimisé est O(1) en moyenne.- Les clés de
HashMapsont dans l'ordre d'insertion (ou aléatoires selon l'implémentation). Les clés deTreeMapsont toujours triées.TreeMappropose gratuitement des données statistiques telles que : obtenir le minimum, obtenir le maximum, la médiane, trouver des plages de clés.HashMapne le fait pas.TreeMapa toujours la garantie d'un O(log n) , tandis queHashMaps a un temps amorti de O(1) mais dans les rares cas de répétition, cela prendrait un O(n) .Connaître les propriétés des graphiques et des arbres. (Cliquez pour agrandir)
Connaître les propriétés des graphiques et des arbres
Graphiques
Connaissez toutes les propriétés des graphiques avec de nombreuses images et illustrations.
Graphiques : nœuds de données qui peuvent avoir une connexion ou un bord avec zéro ou plusieurs nœuds adjacents. Contrairement aux arbres, les nœuds peuvent avoir plusieurs parents, boucles. Codes | Complexité temporelle du graphique
Arbres
Apprenez toutes les différentes sortes d’arbres et leurs propriétés.
Arbres : les nœuds de données ont zéro ou plusieurs nœuds adjacents, c'est-à-dire des enfants. Chaque nœud ne peut avoir qu'un seul nœud parent, sinon il s'agit d'un graphique et non d'un arbre. Codes | Documents
Arbres binaires : identique à un arbre mais ne peut avoir que deux enfants au maximum. Codes | Documents
Arbres de recherche binaire (BST) : identique à un arbre binaire, mais la valeur des nœuds conserve cet ordre
left < parent < right. Codes | Complexité temporelle BSTArbres AVL : BST auto-équilibré pour maximiser le temps de recherche. Codes | Documents sur l'arborescence AVL | Documents sur l'auto-équilibrage et la rotation des arbres
Arbres rouge-noir : BST auto-équilibré plus lâche que AVL pour maximiser la vitesse d'insertion. Code
Implémentez un arbre de recherche binaire pour des recherches rapides.
Implémenter un arbre de recherche binaire pour des recherches rapides
Découvrez comment ajouter/supprimer/mettre à jour des valeurs dans une arborescence :
Comment équilibrer un arbre ?
Du BST déséquilibré au BST équilibré
1 2 / 2 => 1 3 3
Ne restez jamais coincé à résoudre un problème en 7 étapes simples. (Cliquez pour agrandir)
Ne restez jamais coincé à résoudre un problème en 8 étapes simples
- Comprendre le problème
- Créer un exemple simple (pas encore de cas extrêmes)
- Réfléchissez à des solutions (algorithme gourmand, Divide and Conquer, Backtracking, force brute)
- Testez votre réponse sur l'exemple simple (mentalement)
- Optimiser la solution
- Écrivez du code. Oui, vous pouvez désormais coder.
- Testez votre code écrit
- Analysez la complexité, à la fois spatiale et temporelle, et assurez-vous de l'optimiser davantage.
Tous les détails ici
Maîtrisez les algorithmes de tri les plus populaires (tri par fusion, tri rapide, etc.) (Cliquez pour agrandir)
Maîtrisez les algorithmes de tri les plus populaires
Nous allons explorer trois algorithmes de tri essentiels O(n^2), qui ont une faible surcharge :
Tri à bulles. Codes | Documents
Tri par insertion. Codes | Documents
Tri par sélection. Codes | Documents
puis discutez des algorithmes de tri efficaces O(n log n) tels que :
Fusionner le tri. Codes | Documents
Tri rapide. Codes | Documents
Apprenez différentes approches pour résoudre des problèmes tels que diviser pour régner, la programmation dynamique, les algorithmes gloutons et le retour en arrière. (Cliquez pour agrandir)
Apprenez différentes approches pour résoudre des problèmes algorithmiques
Nous allons discuter des techniques suivantes pour résoudre des problèmes d'algorithmes :
- Algorithmes gourmands : fait des choix gourmands en utilisant des heuristiques pour trouver la meilleure solution sans regarder en arrière.
- Programmation dynamique : une technique permettant d'accélérer les algorithmes récursifs lorsqu'il existe de nombreux sous-problèmes qui se chevauchent . Il utilise la mémorisation pour éviter la duplication du travail.
- Diviser et conquérir : divisez les problèmes en morceaux plus petits, résolvez chaque sous-problème, puis joignez les résultats.
- Backtracking : recherchez tous (ou certains) chemins possibles. Cependant, il s'arrête et revient dès que vous remarquez que la solution actuelle ne fonctionne pas.
- Brute Force : génère toutes les solutions possibles et les essaie toutes. (Utilisez-le en dernier recours ou comme point de départ).
En tant que programmeur, nous devons résoudre des problèmes chaque jour. Si vous souhaitez résoudre correctement les problèmes, il est bon de connaître un large éventail de solutions. Souvent, il est plus efficace de se renseigner sur les ressources existantes que de trouver la réponse par hasard. Plus vous disposez d’outils et de pratique, mieux c’est. Ce livre vous aide à comprendre les compromis entre les structures de données et les raisons des performances des algorithmes.
Il n’existe pas beaucoup de livres sur les algorithmes en JavaScript. Ce matériau comble le vide. C'est aussi une bonne pratique :)
Oui, ouvrez un ticket ou posez des questions sur la [chaîne Slack](https://dsajs-slackin.herokuapp.com).
Ce projet est également disponible dans un livre. Vous obtiendrez un PDF bien formaté avec plus de 180 pages + version ePub et Mobi.
Contactez-moi à l'un des endroits suivants !
@iAmAdrianMejiadsajs.slack.com 
