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.

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²	n²	1	Sim
Insertion sort	n	n²	n²	1	Sim
Selection sort	n²	n²	n²	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²	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))²	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