javascript-algorithms

Algorithmes et Structures de Données en JavaScript

CI codecov

Ce dépôt contient des exemples d’implémentation en JavaScript de plusieurs algorithmes et structures de données populaires.

Chaque algorithme et structure de donnée possède son propre README contenant les explications détaillées et liens (incluant aussi des vidéos Youtube) pour complément d’informations.

Lisez ceci dans d’autres langues: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Español, Português, Русский, Türk, Italiana

Data Structures

Une structure de données est une manière spéciale d’organiser et de stocker des données dans un ordinateur de manière à ce que l’on puisse accéder à cette information et la modifier de manière efficiente. De manière plus spécifique, une structure de données est un ensemble composé d’une collection de valeurs, des relations entre ces valeurs ainsi que d’un ensemble de fonctions ou d’opérations pouvant être appliquées sur ces données.

B - Débutant, A - Avancé

Algorithmes

Un algorithme est une démarche non ambigüe expliquant comment résoudre une classe de problèmes. C’est un ensemble de règles décrivant de manière précise une séquence d’opérations.

B - Débutant, A - Avancé

Algorithmes par topic

Algorithmes par Paradigme

Un paradigme algorithmique est une méthode générique ou une approche qui sous-tend la conception d’une classe d’algorithmes. C’est une abstraction au-dessus de la notion d’algorithme, tout comme l’algorithme est une abstraction supérieure à un programme informatique.

Comment utiliser ce dépôt

Installer toutes les dépendances

npm install

Exécuter ESLint

Vous pouvez l’installer pour tester la qualité du code.

npm run lint

Exécuter tous les tests

npm test

Exécuter les tests par nom

npm test -- 'LinkedList'

Tests personnalisés

Vous pouvez manipuler les structures de données et algorithmes présents dans ce dépôt avec le fichier ./src/playground/playground.js et écrire vos propres tests dans file ./src/playground/__test__/playground.test.js.

Vous pourrez alors simplement exécuter la commande suivante afin de tester si votre code fonctionne comme escompté

npm test -- 'playground'

Informations Utiles

Références

▶ Structures de Données et Algorithmes sur YouTube

Notation Grand O

Comparaison de la performance d’algorithmes en notation Grand O.

Big O graphs

Source: Big O Cheat Sheet.

Voici la liste de certaines des notations Grand O les plus utilisées et de leurs comparaisons de performance suivant différentes tailles pour les données d’entrée.

Notation Grand O Opérations pour 10 éléments Opérations pour 100 éléments Opérations pour 1000 éléments
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

Complexité des Opérations suivant les Structures de Données

Structure de donnée Accès Recherche Insertion Suppression Commentaires
Liste 1 n n n  
Pile n n 1 1  
Queue n n 1 1  
Liste Liée n n 1 1  
Table de Hachage - n n n Dans le cas des fonctions de hachage parfaites, les couts seraient de O(1)
Arbre de Recherche Binaire n n n n Dans le cas des arbre équilibrés, les coûts seraient de O(log(n))
Arbre B log(n) log(n) log(n) log(n)  
Arbre Red-Black log(n) log(n) log(n) log(n)  
Arbre AVL log(n) log(n) log(n) log(n)  
Filtre de Bloom - 1 1 - Les faux positifs sont possibles lors de la recherche

Complexité des Algorithmes de Tri de Liste

Nom Meilleur Moyenne Pire Mémoire Stable Commentaires
Tri Bulle n n2 n2 1 Oui  
Tri Insertion n n2 n2 1 Oui  
Tri Sélection n2 n2 n2 1 Non  
Tri par Tas n log(n) n log(n) n log(n) 1 Non  
Merge sort n log(n) n log(n) n log(n) n Oui  
Tri Rapide n log(n) n log(n) n2 log(n) Non le Tri Rapide est généralement effectué in-place avec une pile de taille O(log(n))
Tri Shell n log(n) dépend du gap séquence n (log(n))2 1 Non  
Tri Comptage n + r n + r n + r n + r Oui r - le plus grand nombre dans la liste
Tri Radix n * k n * k n * k n + k Non k - longueur du plus long index