javascript-algorithms

Algoritmi e Strutture Dati in Javascript

CI codecov

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

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

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.

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

Grafi 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