Estrutura de Dados e Algoritmos em JavaScript

Este repositório contém exemplos baseados em JavaScript de muitos algoritmos e estruturas de dados populares.

Cada algoritmo e estrutura de dados possui seu próprio README com explicações relacionadas e links para leitura adicional (incluindo vídeos para YouTube)

Leia isto em outros idiomas: English 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Русский, Türk, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch, Uzbek עברית

Estrutura de Dados

Uma estrutura de dados é uma maneira particular de organizar e armazenar dados em um computador para que ele possa ser acessado e modificado de forma eficiente. Mais precisamente, uma estrutura de dados é uma coleção de valores de dados, as relações entre eles e as funções ou operações que podem ser aplicadas aos dados.

B - Iniciante, A - Avançado

B Lista Encadeada (Linked List)
B Lista Duplamente Ligada (Doubly Linked List)
B Fila (Queue)
B Pilha (Stack)
B Tabela de Hash (Hash Table)
B Heap - versões de heap máximo e mínimo
B Fila de Prioridade (Priority Queue)
A Árvore de Prefixos (Trie)
A Árvore (Tree)
- A Árvore de Pesquisa Binária (Binary Search Tree)
- A Árvore AVL (AVL Tree)
- A Árvore Rubro-Negra (Red-Black Tree)
- A Árvore de Segmento (Segment Tree) - com exemplos de consultas min / max / sum range
- A Árvore Fenwick (Fenwick Tree) (Árvore indexada binária)
A Grafo (Graph) (ambos dirigidos e não direcionados)
A Conjunto Disjunto (Disjoint Set)
A Filtro Bloom (Bloom Filter)

Algoritmos

Um algoritmo é uma especificação inequívoca de como resolver uma classe de problemas. Isto é um conjunto de regras que define precisamente uma sequência de operações.

B - Iniciante, A - Avançado

Algoritmos por Tópico

Matemática
- B Manipulação Bit - set/get/update/clear bits, multiplicação / divisão por dois, tornar negativo etc.
- B Fatorial
- B Número de Fibonacci
- B Teste de Primalidade (método de divisão experimental)
- B Algoritmo Euclidiano - Calcular o Máximo Divisor Comum (MDC)
- B Mínimo Múltiplo Comum Calcular o Mínimo Múltiplo Comum (MMC)
- B Peneira de Eratóstenes - Encontrar todos os números primos até um determinado limite
- B Potência de Dois - Verifique se o número é a potência de dois (algoritmos ingênuos e bit a bit)
- B Triângulo de Pascal
- B Número Complexo - Números complexos e operações básicas com eles
- A Partição Inteira
- A Algoritmo Liu Hui π - Cálculos aproximados de π baseados em N-gons
Conjuntos
- B Produto Cartesiano - Produto de vários conjuntos
- B Permutações de Fisher–Yates - Permutação aleatória de uma sequência finita
- A Potência e Conjunto - Todos os subconjuntos de um conjunto
- A Permutações (com e sem repetições)
- A Combinações (com e sem repetições)
- A Mais Longa Subsequência Comum (LCS)
- A Maior Subsequência Crescente
- A Supersequência Comum Mais Curta (SCS)
- A Problema da Mochila - "0/1" e "Não consolidado"
- A Subarray Máximo - "Força bruta" e "Programação Dinâmica", versões de Kadane
- A Soma de Combinação - Encontre todas as combinações que formam uma soma específica
Cadeia de Caracteres
- B Distância de Hamming - Número de posições em que os símbolos são diferentes
- B Palíndromos - Verifique se a cadeia de caracteres (string) é a mesma ao contrário
- A Distância Levenshtein - Distância mínima de edição entre duas sequências
- A Algoritmo Knuth–Morris–Pratt (Algoritmo KMP) - Pesquisa de substring (correspondência de padrão)
- A Z Algorithm - Pesquisa de substring (correspondência de padrão)
- A Algoritmo de Rabin Karp - Pesquisa de substring
- A Substring Comum Mais Longa
- A Expressões Regulares Correspondentes
Buscas
- B Busca Linear (Linear Search)
- B Busca por Saltos (Jump Search) - Pesquisa em matriz ordenada
- B Busca Binária (Binary Search) - Pesquisa em matriz ordenada
- B Busca por Interpolação (Interpolation Search) - Pesquisa em matriz classificada uniformemente distribuída
Classificação
- B Bubble Sort
- B Selection Sort
- B Insertion Sort
- B Heap Sort
- B Merge Sort
- B Quicksort - Implementações local e não local
- B Shellsort
- B Counting Sort
- B Radix Sort
Árvores
- B Busca em Profundidade (Depth-First Search) (DFS)
- B Busca em Largura (Breadth-First Search) (BFS)
Grafos
- B Busca em Profundidade (Depth-First Search) (DFS)
- B Busca em Largura (Breadth-First Search) (BFS)
- B Algoritmo de Kruskal - Encontrando Árvore Mínima de Abrangência (MST) para grafo conexo com pesos
- A Algoritmo de Dijkstra - Encontrar caminhos mais curtos para todos os vértices do grafo a partir de um único vértice
- A Algoritmo de Bellman-Ford - Encontrar caminhos mais curtos para todos os vértices do grafo a partir de um único vértice
- A Algoritmo de Floyd-Warshall - Encontrar caminhos mais curtos entre todos os pares de vértices
- A Detectar Ciclo - Para grafos direcionados e não direcionados (versões baseadas em DFS e Conjunto Disjuntivo)
- A Algoritmo de Prim - Encontrando Árvore Mínima de Abrangência (MST) para grafo não direcionado ponderado
- A Ordenação Topológica - Métodos DFS
- A Pontos de Articulação - O algoritmo de Tarjan (baseado em DFS)
- A Pontes - Algoritmo baseado em DFS
- A Caminho e Circuito Euleriano - Algoritmo de Fleury - Visite todas as bordas exatamente uma vez
- A Ciclo Hamiltoniano - Visite todas as bordas exatamente uma vez
- A Componentes Fortemente Conectados - Algoritmo de Kosaraju
- A Problema do Caixeiro Viajante - Rota mais curta possível que visita cada cidade e retorna à cidade de origem
Criptografia
- B Hash Polinomial - Função de hash de rolagem baseada em polinômio
Sem categoria
- B Torre de Hanoi
- B Rotação de Matriz Quadrada - Algoritmo no local
- B Jogo do Salto - Backtracking, programação dinâmica (top-down + bottom-up) e exemplos gananciosos
- B Caminhos Únicos - Backtracking, programação dinâmica e exemplos baseados no triângulo de Pascal
- B Terraços de Chuva - Problema de retenção da água da chuva (programação dinâmica e versões de força bruta)
- A Problema das N-Rainhas
- A Passeio do Cavaleiro

Algoritmos por Paradigma

Um paradigma algorítmico é um método ou abordagem genérica subjacente ao design de uma classe de algoritmos. É uma abstração maior do que a noção de um algoritmo, assim como algoritmo é uma abstração maior que um programa de computador.

Força bruta - Pense em todas as possibilidades e escolha a melhor solução
- B Busca Linear (Linear Search)
- B Terraços de Chuva - Problema de retenção de água da chuva (programação dinâmica e versões de força bruta)
- A Subarray Máximo
- A Problema do Caixeiro Viajante - Rota mais curta possível que visita cada cidade e retorna à cidade de origem
Ganância - Escolha a melhor opção no momento, sem qualquer consideração pelo futuro
- B Jogo do Salto
- A Problema da Mochila
- A Algoritmo de Dijkstra - Encontrar caminhos mais curtos para todos os vértices do grafo a partir de um único vértice
- A Algoritmo de Prim - Encontrando Árvore Mínima de Abrangência (MST) para grafo não direcionado ponderado
- A Algoritmo de Kruskal - Encontrando Árvore Mínima de Abrangência (MST) para grafo conexo com pesos
Dividir e Conquistar - Dividir o problema em partes menores e então resolver essas partes
- B Busca Binária (Binary Search)
- B Torre de Hanoi
- B Triângulo de Pascal
- B Algoritmo Euclidiano - Calcular o Máximo Divisor Comum (MDC)
- B Merge Sort
- B Quicksort
- B Busca em Profundidade (Depth-First Search) (DFS)
- B Busca em Largura (Breadth-First Search) (BFS)
- B Jogo do Salto
- A Permutações (com e sem repetições)
- A Combinações (com e sem repetições)
Programação Dinâmica - Criar uma solução usando sub-soluções encontradas anteriormente
- B Número de Fibonacci
- B Jogo do Salto
- B Caminhos Únicos
- B Terraços de Chuva - Trapping problema da água da chuva
- A Distância Levenshtein - Distância mínima de edição entre duas sequências
- A Mais Longa Subsequência Comum (LCS)
- A Substring Comum Mais Longa
- A Maior Subsequência Crescente
- A Supersequência Comum Mais Curta
- A Problema da Mochila
- A Partição Inteira
- A Subarray Máximo
- A Algoritmo de Bellman-Ford - Encontrar caminhos mais curtos para todos os vértices do grafo a partir de um único vértice
- A Algoritmo de Floyd-Warshall - Encontrar caminhos mais curtos entre todos os pares de vértices
- A Expressões Regulares Correspondentes
Backtracking - Da mesma forma que a força bruta, tente gerar todas as soluções possíveis, mas, cada vez que você gerar a próxima solução será necessário testar se a mesma satisfaz todas as condições, e só então continuará a gerar as soluções subsequentes. Caso contrário, volte atrás e siga um caminho diferente para encontrar uma solução. Normalmente, a passagem DFS do espaço de estados está sendo usada.
- B Jogo do Salto
- B Caminhos Únicos
- A Ciclo Hamiltoniano - Visite todos os vértices exatamente uma vez
- A Problema das N-Rainhas
- A Passeio do Cavaleiro
- A Soma de Combinação - Encontre todas as combinações que formam uma soma específica
Branch & Bound - Lembre-se da solução de menor custo encontrada em cada etapa do retrocesso, pesquisar e usar o custo da solução de menor custo encontrada até o limite inferior do custo de solução de menor custo para o problema, a fim de descartar soluções parciais com custos maiores que o solução de menor custo encontrada até o momento. Normalmente, a travessia BFS em combinação com a passagem DFS do espaço de estados árvore está sendo usada

Como usar este repositório

Instalar todas as dependências

npm install

Executar o ESLint

Você pode querer executá-lo para verificar a qualidade do código.

npm run lint

Execute todos os testes

npm test

Executar testes por nome

npm test -- 'LinkedList'

Solução de problemas

Caso o linting ou o teste estejam falhando, tente excluir a pasta node_modules e reinstalar os pacotes npm:

rm -rf ./node_modules
npm i

Verifique também se você está usando uma versão correta do Node (>=14.16.0). Se você estiver usando nvm para gerenciamento de versão do Node, você pode executar nvm use a partir da pasta raiz do projeto e a versão correta será escolhida.

Playground

Você pode brincar com estruturas de dados e algoritmos no arquivo ./src/playground/playground.js e escrever testes para isso em ./src/playground/__test__/playground.test.js.

Em seguida, basta executar o seguinte comando para testar se o código do seu playground funciona conforme o esperado:

npm test -- 'playground'

Informação útil

Referências

Notação Big O

A notação Big O é usada para classificar algoritmos de acordo com a forma como seu tempo de execução ou requisitos de espaço crescem à medida que o tamanho da entrada aumenta. No gráfico abaixo você pode encontrar as ordens mais comuns de crescimento de algoritmos especificados na notação Big O.

Fonte: Notação Big-O Dicas.

Abaixo está a lista de algumas das notações Big O mais usadas e suas comparações de desempenho em relação aos diferentes tamanhos dos dados de entrada.

Notação Big-O	Cálculos para 10 elementos	Cálculos para 100 elementos	Cálculos para 1000 elementos
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

Complexidade de operações de estrutura de dados

Estrutura de dados	Acesso	Busca	Inserção	Eliminação	Comentários
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	Em caso de uma função hash perfeita, os custos seriam O(1)
Binary Search Tree	n	n	n	n	No caso de custos de árvore equilibrados seria 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	-	Falsos positivos são possíveis durante a pesquisa

Complexidade dos Algoritmos de Ordenação de Matrizes

Nome	Melhor	Média	Pior	Mémoria	Estável	Comentários
Bubble sort	n	n<sup>2</sup>	n<sup>2</sup>	1	Sim
Insertion sort	n	n<sup>2</sup>	n<sup>2</sup>	1	Sim
Selection sort	n<sup>2</sup>	n<sup>2</sup>	n<sup>2</sup>	1	Não
Heap sort	n log(n)	n log(n)	n log(n)	1	Não
Merge sort	n log(n)	n log(n)	n log(n)	n	Sim
Quick sort	n log(n)	n log(n)	n<sup>2</sup>	log(n)	Não	O Quicksort geralmente é feito no local com espaço de pilha O(log(n))
Shell sort	n log(n)	depende da sequência de lacunas	n (log(n))<sup>2</sup>	1	Não
Counting sort	n + r	n + r	n + r	n + r	Sim	r - maior número na matriz
Radix sort	n * k	n * k	n * k	n + k	Sim	k - comprimento da chave mais longa

ℹ️ Outros projetos e artigos sobre JavaScript e algoritmos em trekhleb.dev