Skip to content

Latest commit

 

History

History
303 lines (260 loc) · 22 KB

README.pt-BR.md

File metadata and controls

303 lines (260 loc) · 22 KB

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 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

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'

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 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