javascript-algorithms

Algoritmi e Strutture Dati in Javascript

Questa repository contiene esempi in Javascript dei più popolari algoritmi e strutture dati .

Ogni algortimo e struttura dati ha il suo README separato e la relative spiegazioni e i link per ulteriori approfondimenti (compresi quelli su YouTube).

Leggilo in altre lingue: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk

☝ Si noti che questo progetto è destinato ad essere utilizzato solo per l’apprendimento e la ricerca e non è destinato ad essere utilizzato per il commercio.

Strutture Dati

Una struttura dati è un particolare modo di organizzare e memorizzare i dati in un computer che permeta di accedervi e modificarli in modo efficiente. Più precisamente, una struttura dati è una raccolta di dati, le relazioni tra di essi e le funzioni o operazioni che possono essere applicate ai dati.

P - Principiante, A - Avanzato

• P Lista Concatenata
• P Doppia Lista Concatenata
• P Coda
• P Pila
• P Hash Table
• P Heap - versione massimo e minimo heap
• P Coda di priorità
• A Trie
• A Albero
  • A Albero binario di ricerca
  • A Albero AVL
  • A RB Albero
  • A Albero Segmentato - con min/max/sum esempi di query
  • A Albero di Fenwick (Albero binario indicizzato)
• A Grafo (direzionale e unidirezionale)
• A Set Disgiunto
• A Filtro Bloom

Algoritmi

Un algoritmo è una specifica univoca per risolvere una classe di problemi. È un insieme di regole che definiscono con precisione una sequenza di operazioni.

P - Principiante, A - Avanzato

Algoritmi per Topic

• Matematica
  • P Manipolazione dei Bit - set/get/update/clear bits, moltiplicazione/divisione per due, gestire numeri negativi etc.
  • P Fattoriale
  • P Numeri di Fibonacci - classico e forma chiusa
  • P Test di Primalità (metodo del divisore)
  • P Algoritmo di Euclide - trova il massimo comune divisore (MCD)
  • P Minimo Comune Multiplo (MCM)
  • P Crivello di Eratostene - trova i numeri i primi fino al limite indicato
  • P Potenza di due - controlla se il numero è una potenza di due
  • P Triangolo di Pascal
  • P Numeri Complessi - numeri complessi e operazioni
  • P Radiante & Gradi - conversione da radiante a gradi e viceversa
  • P Potenza di un Numero
  • A Partizione di un Intero
  • A Radice Quadrata - Metodo di Newton
  • A Algoritmo di Liu Hui π - calcolare π usando un poligono
  • A Trasformata Discreta di Fourier -decomporre una funzione di tempo (un segnale) nelle frequenze che lo compongono
• Set
  • P Prodotto Cartesiano - moltiplicazione multipla di set
  • P Fisher–Yates Shuffle - permutazione casuale di un sequenza finita
  • A Power Set - tutti i sottoinsiemi di un set (soluzioni bitwise e backtracking)
  • A Permutazioni (con e senza ripetizioni)
  • A Combinazioni (con e senza ripetizioni)
  • A Massima Sottosequenza Comune (LCS)
  • A Massima Sottosequenza Crescente
  • A Minima Sottosequenza Diffusa (SCS)
  • A Problema dello Zaino di Knapsack - “0/1” e “Senza Restrizioni”
  • A Massimo SubArray - “Brute Force” e “Programmazione Dinamica” versione Kadane
  • A Somma di Combinazioni - ricerca di tutte le combinazioni di una somma
• String
  • P Distanza di Hamming - numero di posizioni in cui i caratteri sono diversi
  • A Distanza di Levenshtein - numero minimo di modifiche per rendere uguali due stringhe
  • A Algoritmo di Knuth-Morris-Pratt (KMP) - ricerca nella sottostringa (pattern matching)
  • A Algoritmo Z - ricerca nella sottostringa (pattern matching)
  • A Algoritmo di Rabin Karp - ricerca nella sottostringa
  • A Sottostringa Comune più lunga
  • A Espressioni Regolari
• Searches
  • P Ricerca Sequenziale
  • P Ricerca a Salti (o Ricerca a Blocchi) - per la ricerca in array ordinati
  • P Ricerca Binari - per la ricerca in array ordinati
  • P Ricerca Interpolata - per la ricerca in un array ordinato uniformemente distibuito
• Sorting
  • P Bubble Sort
  • P Selection Sort
  • P Insertion Sort
  • P Heap Sort
  • P Merge Sort
  • P Quicksort - con e senza allocazione di ulteriore memoria
  • P Shellsort
  • P Counting Sort
  • P Radix Sort
• Lista Concatenatas
  • P Attraversamento Lista Concatenata
  • P Attraversamento Lista Concatenata nel senso Contrario
• Alberi
  • P Ricerca in Profondità su Alberi (DFS)
  • P Ricerca in Ampiezza su Alberi (BFS)
• Grafi
  • P Ricerca in Profondità su Grafi (DFS)
  • P Breadth-First Search su Grafi (BFS)
  • P Algoritmo di Kruskal - ricerca dell’Albero con Minima Distanza (MST) per grafi pesati unidirezionali
  • A Algoritmo di Dijkstra - ricerca dei percorsi più breve per raggiungere tutti i vertici del grafo da un singolo vertice
  • A Algoritmo di Bellman-Ford - ricerca dei percorsi più breve per raggiungere tutti i vertici del grafo da un singolo vertice
  • A Algoritmo di Floyd-Warshall - ricerca dei percorsi più brevi tra tutte le coppie di vertici
  • A Rivelamento dei Cicli - per grafici diretti e non diretti (basate su partizioni DFS e Disjoint Set)
  • A Algoritmo di Prim - ricerca dell’Albero Ricoprente Minimo (MST) per grafi unidirezionali pesati
  • A Ordinamento Topologico - metodo DFS
  • A Punti di Articolazione - Algoritmo di Tarjan (basato su DFS)
  • A Bridges - basato su DFS
  • A Cammino Euleriano e Circuito Euleriano - Algoritmo di Fleury - Visita ogni margine esattamente una volta
  • A Ciclo di Hamiltonian - Visita ad ogni vertice solo una volta
  • A Componenti Fortemente Connessa - algoritmo di Kosaraju
  • A Problema del Commesso Viaggiatore - il percorso più breve che visita ogni città e ritorna alla città iniziale
• Crittografia
  • P Hash Polinomiale - Una funzione hash di rolling basata sul polinomio
• Senza categoria
  • P Torre di Hanoi
  • P Rotazione Matrice Quadrata - algoritmo in memoria
  • P Jump Game - backtracking, programmazione dinamica (top-down + bottom-up) ed esempre di greeedy
  • P Percorsi Unici - backtracking, programmazione dinamica and l’esempio del Triangolo di Pascal
  • P Rain Terraces - problema dell’acqua piovana in trappola(versione con programmazione dinamica e brute force)
  • P Recursive Staircase - contare il numero di percorsi per arrivare in vetta(4 soluzioni)
  • A Rompicapo delle Otto Regine
  • A Percorso del Cavallo

Modelli di Algoritmi

Un modello di algoritmo è un generico metodo o approcio che sta alla base della progettazione di una classe di algoritmi. Si tratta di un’astrazione ancora più alta di un algoritmo, proprio come un algoritmo è un’astrazione di un programma del computer.

• Brute Force - controlla tutte le possibilità e seleziona la migliore
  • P Ricerca Lineare
  • P Rain Terraces - problema dell’acqua piovana in trappola
  • P Recursive Staircase - contare il numero di percorsi per arrivare in vetta
  • A Massimo SubArray
  • A Problema del commesso viaggiatore - il percorso più breve che visita ogni città e ritorna alla città iniziale
  • A Trasformata Discreta di Fourier - scomporre la funzione (segnale) del tempo in frequenze che la compongono
• Greedy - scegliere l’opzione migliore al momento d’eleborazione dell’algoritmo, senza alcuna considerazione per il futuro
  • P Jump Game
  • A Problema dello Zaino di Knapsack
  • A Algoritmo di Dijkstra - ricerca del percorso più breve tra tutti i vertici del grafo
  • A Algoritmo di Prim - ricerca del Minimo Albero Ricoprente per grafi pesati e unidirezionali
  • A Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
• Divide e Conquista - divide il problema in piccole parti e risolve ogni parte
  • P Ricerca Binaria
  • P Torre di Hanoi
  • P Triangolo di Pascal
  • P Algoritmo di Euclide - calculate the Greatest Common Divisor (GCD)
  • P Merge Sort
  • P Quicksort
  • P Albero per Ricerca in Profondità (DFS)
  • P Grafo per Ricerca in Profondità (DFS)
  • P Jump Game
  • P Algoritmo di Elevamento a Potenza
  • A Permutazioni (con o senza ripetizioni)
  • A Combinazioni (con o senza ripetizioni)
• Programmazione Dinamica - creare una soluzione utilizzando le sub-solution trovate in precedenza
  • P Numero di Fibonacci
  • P Jump Game
  • P Percorsi Unici
  • P Rain Terraces - problema dell’acqua piovana in trappola
  • P Recursive Staircase - contare il numero di percorsi per arrivare in vetta
  • A Distanza di Levenshtein - minima variazione tra due sequenze
  • A La Più Lunga Frequente SottoSequenza (LCS)
  • A La Più Lunga Frequente SubString
  • A La Più Lunga SottoSequenza Crescente
  • A La Più Corta e Frequente SuperSequenza
  • A Problema dello zaino
  • A Partizione di un Intero
  • A Massimo SubArray
  • A Algoritmo di Bellman-Ford - ricerca del percorso più breve per tutti i vertici del grafo
  • A Algoritmo di Floyd-Warshall - ricerca del percorso più breve tra tutte le coppie di vertici
  • A Espressioni Regolari
• Backtracking - come la brute force, provate a generare tutte le soluzioni possibili, ma ogni volta che generate la prossima soluzione testate se soddisfa tutte le condizioni e solo allora continuare a generare soluzioni successive. Altrimenti, fate marcia indietro, e andate su un percorso diverso per trovare una soluzione. Normalmente si utilizza l’algoritmo DFS.
  • P Jump Game
  • P Percorsi Unici
  • P Power Set - tutti i subset di un set
  • A Ciclo di Hamiltonian - visita di tutti i vertici solamente una volta
  • A Problema di N-Queens
  • A Knight’s Tour
  • A Combinazioni di una Somma - trovare tutte le combinazioni che compongono una somma
• Branch & Bound - ricordatevi che la soluzione meno costosa trovata ad ogni step durante il backtracking e il costo di usare la soluzione meno costosa trovata fino al limite inferiore al costo minimo della soluzione al problema, al fine di scartare soluzioni parziali con costi maggiori della soluzione meno costosa trovata . Di solito si usa BFS trasversale in combinazione con DFS trasversale .

Come usare questa repository

Installare tutte le dipendenze

npm install

Eseguire ESLint

Potresti usarlo per controllare la qualità del codice.

npm run lint

Eseguire tutti i test

npm test

Eseguire un test tramite il nome

npm test -- 'LinkedList'

Playground

Se vuoi puoi giocare le strutture dati e gli algoritmi nel file ./src/playground/playground.js e scrivere test nel file ./src/playground/test/playground.test.js`.

Poi puoi semplicemente eseguire il seguente comando per testare quello che hai scritto :

npm test -- 'playground'

Informazioni Utili

Bibliografia

▶ Data Structures and Algorithms on YouTube

Notazione Big O

• La notazione Big O* è usata per classificare algoritmi in base al tempo di esecuzione o ai requisiti di spazio che crescono in base alla crescita dell’input . Nella grafico qua sotto puoi trovare gli ordini di crescita più comuni degli algoritmi usando la notazione Big O.

Riferimento: Big O Cheat Sheet.

Nella tabella qua sotto ci sono riportate la lista delle notazioni Big O più usate e delle loro prestazioni comparate tra differenti grandezze d’input .

Notazione Big O	Computazione con 10 elementi	Computazione con 100 elementi	Computazione con 1000 elementi
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

Complessità delle Operazion sulle Strutture Dati

Struttura Dati	Accesso	Ricerca	Inserimento	Rimozione	Commenti
Array	1	n	n	n
Pila	n	n	1	1
Coda	n	n	1	1
Lista Concatenata	n	n	1	n
Tabella Hash	-	n	n	n	Nel caso di una funzione di hashing perfetta il costo sarebbe O(1)
Binary Search Tree	n	n	n	n	Nel caso di albero bilanciato il costo sarebbe O(log(n))
B-Tree	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
Albero AVL	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	Falsi positivi sono possibili durante la ricerca

Complessità degli Algoritmi di Ordinamento di Array

Nome	Milgiore	Media	Perggiore	Memoria	Stabile	Commenti
Bubble sort	n	n2	n2	1	Yes
Insertion sort	n	n2	n2	1	Yes
Selection sort	n2	n2	n2	1	No
Heap sort	n log(n)	n log(n)	n log(n)	1	No
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes
Quick sort	n log(n)	n log(n)	n2	log(n)	No	Quicksort viene eseguito in memoria solitamente con una pila di O(log(n))
Shell sort	n log(n)	dipende dagli spazi vuoti nella sequenza	n (log(n))2	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - numero più grande nell’array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - lunghezza della chiave più grande

This site is open source. Improve this page.