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

• ▶ Estruturas de Dados e Algoritmos no YouTube
• ✍🏻 Esboços de Estruturas de Dados

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