dsa.js data structures algorithms javascript

Estruturas de dados e algoritmos em JavaScript

Estas são as implementações de codificação do livro DSA.js e o repositório do pacote NPM.

Neste repositório você encontra a implementação de algoritmos e estruturas de dados em JavaScript. Este material pode ser usado como manual de referência para desenvolvedores ou você pode atualizar tópicos específicos antes de uma entrevista. Além disso, você pode encontrar ideias para resolver problemas com mais eficiência.

Índice

• Instalação
• Características
• O que há dentro
  • ? Análise de Algoritmos
  • ? Estruturas de dados lineares
  • ? Estruturas de dados não lineares
  • ⚒ Técnicas de Algoritmos
• Livro
• Perguntas frequentes
• Apoiar
• Licença

Instalação

Você pode clonar o repositório ou instalar o código do NPM:

npm install dsa.js

e então você pode importá-lo para seus programas ou CLI

 const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;

Para obter uma lista de todas as estruturas de dados e algoritmos disponíveis, consulte index.js.

Características

Algoritmos são uma caixa de ferramentas essencial para todo programador.

Você precisará se preocupar com o tempo de execução dos algoritmos quando precisar classificar dados, pesquisar um valor em um grande conjunto de dados, transformar dados, dimensionar seu código para muitos usuários, para citar alguns. Os algoritmos são apenas o passo que você segue para resolver um problema, enquanto as estruturas de dados são onde você armazena os dados para manipulação posterior. Ambos combinados criam programas.

Algoritmos + Estruturas de Dados = Programas.

A maioria das linguagens de programação e bibliotecas realmente fornece implementações para estruturas de dados e algoritmos básicos. No entanto, para fazer uso adequado das estruturas de dados, é necessário conhecer as vantagens e desvantagens para escolher a melhor ferramenta para o trabalho.

Este material vai te ensinar a:

• ? Aplicar estratégias para resolver questões de algoritmos. Para nunca mais ficar preso. Aceite essas entrevistas!
• ✂️ Construa algoritmos eficientes. Aprenda como dividir os problemas em partes gerenciáveis.
• ? Melhore suas habilidades de resolução de problemas e torne-se um desenvolvedor completo, compreendendo os conceitos fundamentais da ciência da computação.
• ? Cubra tópicos essenciais, como big O time, estruturas de dados e algoritmos obrigatórios. Implemente mais de 10 estruturas de dados do zero.

O que há dentro

Todo o código e explicações estão disponíveis neste repositório. Você pode pesquisar os links e exemplos de código da (pasta src). No entanto, os exemplos de código embutido não são expandidos (devido às limitações do asciidoc do Github), mas você pode seguir o caminho e ver a implementação.

Nota: Se preferir consumir as informações de forma mais linear, então o formato livro seria mais adequado para você.

Os temas estão divididos em quatro categorias principais, como você pode conferir a seguir:

? Análise de Algoritmos

Pepitas de Ciência da Computação sem toda a bobagem. (Clique para expandir)

---

Pepitas de Ciência da Computação sem toda a bobagem

Aprenda a calcular o tempo de execução a partir de exemplos de código

---

Aprenda como comparar algoritmos usando a notação Big O. (Clique para expandir)

---

Aprenda como comparar algoritmos usando a notação Big O.

Comparando algoritmos usando notação Big O

Digamos que você queira encontrar duplicatas em um array. Usando a notação Big O, podemos comparar diferentes soluções que resolvem o mesmo problema, mas têm uma enorme diferença no tempo que levam para fazê-lo.

• Solução ideal usando um mapa
• Encontrar duplicatas em uma matriz (abordagem ingênua)

---

8 exemplos para explicar com código como calcular a complexidade do tempo. (Clique para expandir)

---

8 exemplos para explicar com código como calcular a complexidade do tempo

Complexidades de tempo mais comuns

Gráfico de complexidade de tempo

---

? Estruturas de dados lineares

Entenda os meandros das estruturas de dados mais comuns. (Clique para expandir)

---

Entenda os meandros das estruturas de dados mais comuns

• Matrizes: Integradas na maioria das linguagens, portanto não implementadas aqui. Complexidade de tempo da matriz

• Lista vinculada: cada nó de dados possui um link para o próximo (e anterior). Código | Complexidade de tempo da lista vinculada

• Fila: os dados fluem da maneira “primeiro a entrar, primeiro a sair” (FIFO). Código | Complexidade do tempo de fila

• Pilha: os dados fluem da maneira “último a entrar, primeiro a sair” (LIFO). Código | Complexidade do tempo de pilha

---

Quando usar uma matriz ou lista vinculada. Conheça as compensações. (Clique para expandir)

---

Quando usar uma matriz ou lista vinculada. Conheça as compensações

Use matrizes quando…

• Você precisa acessar os dados em ordem aleatória rapidamente (usando um índice).
• Seus dados são multidimensionais (por exemplo, matriz, tensor).

Use listas vinculadas quando:

• Você acessará seus dados sequencialmente.
• Você deseja economizar memória e alocar memória apenas conforme necessário.
• Você deseja um tempo constante para remover/adicionar extremos da lista.
• quando o requisito de tamanho é desconhecido - vantagem de tamanho dinâmico

---

Crie uma lista, uma pilha e uma fila. (Clique para expandir)

---

Crie uma lista, uma pilha e uma fila do zero

Crie qualquer uma destas estruturas de dados do zero:

• Lista vinculada
• Pilha
• Fila

---

? Estruturas de dados não lineares

Entenda uma das estruturas de dados mais versáteis de todas: Hash Maps. (Clique para expandir)

---

HashMaps

Aprenda como implementar diferentes tipos de mapas como:

• HashMap
• ÁrvoreMapa

Além disso, aprenda a diferença entre as diferentes implementações do Maps:

• HashMap é mais eficiente em termos de tempo. Um TreeMap é mais eficiente em termos de espaço.
• A complexidade da pesquisa TreeMap é O(log n) , enquanto um HashMap otimizado é O(1) em média.
• As chaves do HashMap estão em ordem de inserção (ou aleatórias dependendo da implementação). As chaves do TreeMap são sempre classificadas.
• TreeMap oferece alguns dados estatísticos gratuitamente, como: obter mínimo, obter máximo, mediana, encontrar intervalos de chaves. HashMap não.
• TreeMap tem uma garantia sempre de O(log n) , enquanto HashMap s tem um tempo amortizado de O(1) mas no caso raro de uma repetição, seria necessário um O(n) .

---

Conheça as propriedades de Gráficos e Árvores. (Clique para expandir)

---

Conheça as propriedades de gráficos e árvores

Gráficos

Conheça todas as propriedades dos gráficos com diversas imagens e ilustrações.

Gráficos : nós de dados que podem ter uma conexão ou borda com zero ou mais nós adjacentes. Ao contrário das árvores, os nós podem ter vários pais, loops. Código | Complexidade de tempo do gráfico

Árvores

Aprenda todos os diferentes tipos de árvores e suas propriedades.

• Árvores : os nós de dados têm zero ou mais nós adjacentes, também conhecidos como filhos. Cada nó pode ter apenas um nó pai, caso contrário, é um gráfico, não uma árvore. Código | Documentos

  • Árvores binárias : iguais a uma árvore, mas só podem ter no máximo dois filhos. Código | Documentos

  • Árvores de pesquisa binária (BST): iguais a uma árvore binária, mas os valores dos nós mantêm esta ordem left < parent < right . Código | Complexidade de tempo BST

  • Árvores AVL : BST autobalanceado para maximizar o tempo de pesquisa. Código | Documentos da árvore AVL | Documentos de autoequilíbrio e rotação de árvores

  • Árvores Vermelho-Pretas : BST autobalanceado mais solto que AVL para maximizar a velocidade de inserção. Código

---

Implemente uma árvore de pesquisa binária para pesquisas rápidas.

---

Implemente uma árvore de pesquisa binária para pesquisas rápidas

• Aprenda como adicionar/remover/atualizar valores em uma árvore:

• Como fazer uma árvore equilibrada?

Do BST desequilibrado ao BST balanceado

 1                           2
                         /   
   2        =>           1     3
    
     3

---

⚒ Caixa de ferramentas algorítmica

Nunca fique preso ao resolver um problema com 7 etapas simples. (Clique para expandir)

---

Nunca fique preso ao resolver um problema com 8 etapas simples

1. Entenda o problema
2. Crie um exemplo simples (sem casos extremos ainda)
3. Soluções de brainstorming (algoritmo ganancioso, Dividir e Conquistar, Backtracking, força bruta)
4. Teste sua resposta no exemplo simples (mentalmente)
5. Otimize a solução
6. Escreva o código. Sim, agora você pode codificar.
7. Teste seu código escrito
8. Analise a complexidade, tanto de espaço quanto de tempo, e certifique-se de otimizar ainda mais.

Detalhes completos aqui

---

Domine os algoritmos de classificação mais populares (classificação por mesclagem, classificação rápida, etc.) (clique para expandir)

---

Domine os algoritmos de classificação mais populares

Vamos explorar três algoritmos de classificação essenciais O(n^2), que possuem baixa sobrecarga:

• Classificação de bolha. Código | Documentos

• Classificação de inserção. Código | Documentos

• Classificação de seleção. Código | Documentos

e então discutir algoritmos de classificação eficientes O(n log n), como:

• Mesclar classificação. Código | Documentos

• Classificação rápida. Código | Documentos

---

Aprenda diferentes abordagens para resolver problemas como divisão e conquista, programação dinâmica, algoritmos gananciosos e retrocesso. (Clique para expandir)

---

Aprenda diferentes abordagens para resolver problemas algorítmicos

Discutiremos as seguintes técnicas para resolver problemas de algoritmos:

• Algoritmos gananciosos: faz escolhas gananciosas usando heurísticas para encontrar a melhor solução sem olhar para trás.
• Programação Dinâmica: uma técnica para acelerar algoritmos recursivos quando há muitos subproblemas sobrepostos . Ele usa memoização para evitar duplicação de trabalho.
• Dividir e Conquistar: divida os problemas em pedaços menores, conquiste cada subproblema e depois junte os resultados.
• Retrocesso: pesquise todos (ou alguns) caminhos possíveis. No entanto, ele para e volta assim que percebe que a solução atual não está funcionando.
• Força Bruta : gera todas as soluções possíveis e tenta todas elas. (Use-o como último recurso ou como ponto de partida).

---

Perguntas frequentes

Como eu aplicaria isso no meu trabalho diário? (Clique para expandir)

Como programadores, temos que resolver problemas todos os dias. Se você quer resolver bem os problemas, é bom conhecer uma ampla gama de soluções. Freqüentemente, é mais eficiente aprender os recursos existentes do que encontrar a resposta sozinho. Quanto mais ferramentas e prática você tiver, melhor. Este livro ajuda você a compreender as vantagens e desvantagens entre as estruturas de dados e a raciocinar sobre o desempenho dos algoritmos.

Por que você criou este repositório/livro?

Não existem muitos livros sobre algoritmos em JavaScript. Este material preenche a lacuna. Além disso, é uma boa prática :)

Há alguém com quem eu possa entrar em contato se tiver dúvidas sobre algo em particular?

Sim, abra um problema ou faça perguntas no [canal do Slack](https://dsajs-slackin.herokuapp.com).

Livro

Este projeto também está disponível em livro. Você receberá um PDF bem formatado com mais de 180 páginas + versão ePub e Mobi.

Apoiar

Entre em contato comigo em um dos seguintes lugares!

• Twitter em @iAmAdrianMejia
• Bate-papo em dsajs.slack.com

Licença