Skip to content

Latest commit

 

History

History
298 lines (257 loc) · 21.2 KB

README.it-IT.md

File metadata and controls

298 lines (257 loc) · 21.2 KB

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, Bahasa Indonesia, Українська, Arabic

☝ 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.jse 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.

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