README.it-IT.md

Algoritmi e strutture dati JavaScript

Questo repository contiene esempi basati su JavaScript di molti algoritmi e strutture dati popolari.

Ogni algoritmo e struttura dati ha il suo README separato con spiegazioni e collegamenti correlati per ulteriori letture (comprese quelle ai video di YouTube).

Leggi questo in altre lingue: 简体中文, 繁體中文, 한국어, Polski, Français, Español, Português

☝ Si noti che questo progetto è pensato per essere utilizzato per scopi di apprendimento e ricerca solo e non è pensato per essere utilizzato per la produzione.

Strutture dati

Una struttura dati è un modo particolare di organizzare e archiviare i dati in un computer in modo che possa essere accessibili e modificati in modo efficiente. Più precisamente, una struttura dati è una raccolta di dati valori, le relazioni tra loro e le funzioni o le operazioni a cui è possibile applicare i dati.

B - Principiante, A - Avanzate

• B Lista collegata
• B Lista Doubly Linked
• B Coda
• B Pila
• B Tabella hash
• B Mucchio - max and min heap versions
• B Coda prioritaria
• A prova
• A Albero
  • A Albero di ricerca binario
  • A Albero AVL
  • A Albero rosso-nero
  • A Albero del segmento - with min/max/sum range queries examples
  • A Albero di Fenwick (Binary Indexed Tree)
• A Grafico (both directed and undirected)
• A Set disgiunto
• A Filtro Bloom

algoritmi

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

B - Principiante, A - Avanzate

Algoritmi per argomento

• Matematica
  • B Manipolazione bit - set/get/update/clear bits, multiplication/division by two, make negative etc.
  • B Fattoriale
  • B Numero di Fibonacci - classic and closed-form versions
  • B Test di primalità (trial division method)
  • B Algoritmo euclideo - calculate the Greatest Common Divisor (GCD)
  • B Minimo comune multiplo (LCM)
  • B Setaccio di Eratostene - finding all prime numbers up to any given limit
  • B È il potere di due - check if the number is power of two (naive and bitwise algorithms)
  • B Triangolo di Pascal
  • B Numero complesso - complex numbers and basic operations with them
  • B Radian & Degree - radians to degree and backwards conversion
  • B Alimentazione veloce
  • A Partizione intera
  • A Algoritmo di Liu Hui π - approximate π calculations based on N-gons
  • A Trasformata di Fourier discreta - decompose a function of time (a signal) into the frequencies that make it up
• Sets
  • B Prodotto cartesiano - product of multiple sets
  • B Fisher–Yates Shuffle - random permutation of a finite sequence
  • A Power Set - all subsets of a set (bitwise and backtracking solutions)
  • A permutazioni (with and without repetitions)
  • A combinazioni (with and without repetitions)
  • A La più lunga successiva in comune (LCS)
  • A Il più lungo aumento successivo
  • A Short Supersequence più breve (SCS)
  • A Problema dello zaino - "0/1" and "Unbound" ones
  • A Subarray massimo - "Brute Force" and "Dynamic Programming" (Kadane's) versions
  • A Somma combinata - find all combinations that form specific sum
• stringhe
  • B Hamming Distance - number of positions at which the symbols are different
  • A Levenshtein Distance - minimum edit distance between two sequences
  • A Algoritmo di Knuth-Morris-Pratt (KMP Algorithm) - substring search (pattern matching)
  • A Z Algoritmo - substring search (pattern matching)
  • A Rabin Karp Algoritmo - substring search
  • A La sottostringa comune più lunga
  • A Corrispondenza delle espressioni regolari
• ricerche
  • B Ricerca lineare
  • B Salta ricerca (or Block Search) - search in sorted array
  • B Ricerca binaria - search in sorted array
  • B Ricerca di interpolazione - search in uniformly distributed sorted array
• Ordinamento
  • B Bolla Ordinare
  • B Selezione Ordina
  • B Inserimento Ordina
  • B Ordinamento heap
  • B Unisci Ordina
  • B Quicksort - in-place and non-in-place implementations
  • B Shellsort
  • B Conteggio Sort
  • B Radix Sort
• Elenchi collegati
  • B Traversata diritta
  • B Inverso trasversale
• Alberi
  • B Depth-First Search (DFS)
  • B Larghezza prima ricerca (BFS)
• grafici
  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
  • B Algoritmo di Kruskal - finding Minimum Spanning Tree (MST) for weighted undirected graph
  • A Dijkstra Algoritmo - finding shortest paths to all graph vertices from single vertex
  • A Bellman-Ford Algoritmo - finding shortest paths to all graph vertices from single vertex
  • A Floyd-Warshall Algoritmo - find shortest paths between all pairs of vertices
  • A Rileva il ciclo - for both directed and undirected graphs (DFS and Disjoint Set based versions)
  • A Prim’s Algoritmo - finding Minimum Spanning Tree (MST) for weighted undirected graph
  • A Ordinamento topologico - DFS method
  • A Punti di articolazione - Tarjan's algorithm (DFS based)
  • A ponti - DFS based algorithm
  • A Sentiero Euleriano e Circuito Euleriano - Fleury's algorithm - Visit every edge exactly once
  • A Ciclo hamiltoniano - Visit every vertex exactly once
  • A Componenti fortemente connessi - Kosaraju's algorithm
  • A Problema del commesso viaggiatore - shortest possible route that visits each city and returns to the origin city
• Crittografia
  • B Hash polinomiale - rolling hash function based on polynomial
• Non categorizzato
  • B Torre di Hanoi
  • B Rotazione a matrice quadrata - in-place algorithm
  • B Salta il gioco - backtracking, dynamic programming (top-down + bottom-up) and greedy examples
  • B Percorsi unici - backtracking, dynamic programming and Pascal's Triangle based examples
  • B Terrazze di pioggia - trapping rain water problem (dynamic programming and brute force versions)
  • B Scala ricorsiva - count the number of ways to reach to the top (4 solutions)
  • A N-Queens Problem
  • A Knight's Tour

Algoritmi di Paradigm

Un paradigma algoritmico è un metodo o approccio generico alla base del design di una classe di algoritmi. È un'astrazione superiore alla nozione di algoritmo, proprio come a l'algoritmo è un'astrazione più alta di un programma per computer.

• Brute Force - guarda tutte le possibilità e seleziona la soluzione migliore
  • B Ricerca lineare
  • B Rain Terraces - intrappolando il problema dell'acqua piovana
  • B Scala ricorsiva - contare il numero di modi per raggiungere la cima
  • A Maximum Subarray
  • A Problema del commesso viaggiatore - il percorso più breve possibile che visita ciascuna città e ritorna alla città di origine
  • A Discrete Fourier Transform - decompone una funzione del tempo (un segnale) nelle frequenze che lo compongono
• Greedy - scegli l'opzione migliore al momento attuale, senza alcuna considerazione per il futuro
  • B Jump Game
  • A Problema dello zaino non legato
  • A Dijkstra Algoritmo - trovare il percorso più breve per tutti i vertici del grafico
  • A Prim’s Algoritmo - trovare Minimum Spanning Tree (MST) per il grafico ponderato non orientato
  • A Algoritmo di Kruskal - trovare Minimum Spanning Tree (MST) per il grafico ponderato non orientato
• Dividi e Conquista - dividi il problema in parti più piccole e poi risolvi quelle parti
  • B Ricerca binaria
  • B Torre di Hanoi
  • B Pascal's Triangle
  • B Algoritmo euclideo - calcola il più grande divisore comune (GCD)
  • B Merge Sort
  • B Quicksort
  • B Tree Depth-First Search (DFS)
  • B Graph Depth-First Search (DFS)
  • B Jump Game
  • B Fast Powering
  • A Permutazione (con e senza ripetizioni)
  • A Combinazioni (con e senza ripetizioni)
• Programmazione dinamica - crea una soluzione utilizzando sub-soluzioni trovate in precedenza
  • B numero di Fibonacci
  • B Jump Game
  • B Percorsi univoci
  • B Rain Terraces - intrappolando il problema dell'acqua piovana
  • B Scala ricorsiva - contare il numero di modi per raggiungere la cima
  • A Levenshtein Distance - distanza minima di modifica tra due sequenze
  • A Longest Common Subsequence (LCS)
  • A Longest Common Substring
  • A Longest Increasing Subsequence
  • A Supersequence comune più breve
  • A 0/1 Knapsack Problem
  • A Integer Partition
  • A Maximum Subarray
  • A Algoritmo Bellman-Ford - trovare il percorso più breve per tutti i vertici del grafico
  • A Floyd-Warshall Algoritmo - find shortest paths between all pairs of vertices
  • A Regular Expression Matching
• Backtracking - similmente alla forza bruta, prova a generare tutte le possibili soluzioni, ma ogni volta che generi la prossima soluzione prova se soddisfa tutte le condizioni, e solo allora continua a generare soluzioni successive. Altrimenti, torna indietro e vai su a percorso diverso per trovare una soluzione. Normalmente viene utilizzata la traversata DFS dello spazio degli stati.
  • B Jump Game
  • B Percorsi univoci
  • B Power Set - tutti i sottoinsiemi di un set
  • A Hamiltonian Cycle - Visita ogni vertice esattamente una volta
  • A N-Queens Problem
  • A Knight's Tour
  • A somma combinata - trova tutte le combinazioni che formano la somma specifica
• Branch & Bound - ricorda la soluzione più economica trovata in ogni fase del backtracking cerca e utilizza il costo della soluzione più economica trovata fino a un limite inferiore sul costo di una soluzione meno costosa al problema, al fine di scartare soluzioni parziali con costi maggiori del soluzione più economica trovata finora. Normalmente attraversamento di BFS in combinazione con attraversamento DFS di stato-spazio albero viene utilizzato.

Come utilizzare questo repository

Installa tutte le dipendenze

npm install

Esegui ESLint

Si consiglia di eseguirlo per verificare la qualità del codice.

npm run lint

Esegui tutti i test

npm test

Esegui test per nome

npm test -- 'LinkedList'

Playground

Puoi giocare con strutture dati e algoritmi nel file ./src/playground/playground.js e scrivere prova per questo in ./src/playground/__test__/playground.test.js.

Quindi basta semplicemente eseguire il seguente comando per verificare se il codice del tuo parco giochi funziona come previsto:

npm test -- 'playground'

Informazioni utili

Riferimenti

▶ Strutture dati e algoritmi su YouTube

Big O Notation

La notazione O grande viene utilizzata per classificare gli algoritmi in base a come il loro tempo di esecuzione oi requisiti di spazio aumentano con l'aumentare delle dimensioni di input. Nella tabella sottostante è possibile trovare gli ordini di crescita più comuni degli algoritmi specificati nella notazione Big O.

Fonte: Big O Cheat Sheet.

Di seguito è riportato l'elenco di alcune delle notazioni Big O più utilizzate e dei relativi confronti delle prestazioni rispetto a diverse dimensioni dei dati di input.

Big O Notation	Computations for 10 elements	Computations for 100 elements	Computations for 1000 elements
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

Data Structure Operations Complexity

Data Structure	Access	Search	Insertion	Deletion	Comments
Array	1	n	n	n
Stack	n	n	1	1
Queue	n	n	1	1
Linked List	n	n	1	1
Hash Table	-	n	n	n	In case of perfect hash function costs would be O(1)
Binary Search Tree	n	n	n	n	In case of balanced tree costs would be O(log(n))
B-Tree	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	False positives are possible while searching

Array Sorting Algorithms Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
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 is usually done in-place with O(log(n)) stack space
Shell sort	n log(n)	depends on gap sequence	n (log(n))2	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - biggest number in array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of longest key