javascript-algorithms

Estrutura de Dados e Algoritmos em JavaScript

CI codecov

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

Cada algoritmo e estrutura de dado 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

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 dados valores, as relações entre eles e as funções ou operações que podem ser aplicadas a os dados.

B - Iniciante, A - Avançado

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

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.

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'

Parque infantil

Você pode brincar com estruturas de dados e algoritmos em ./src/playground/playground.js arquivar 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

Notação Big O

Ordem de crescimento dos algoritmos especificados em 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

Array Sorting Algorithms Complexity

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 o espaço de pilha O O(log(n)) stack space
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