Uma Introdução a Algoritmos e Estruturas de Dados (Javascript Edition)

Introdução

Compreender algoritmos e estruturas de dados é crucial para melhorar seu desempenho 10 vezes mais do que seus colegas que não o fazem. Isso ocorre porque você analisa os problemas de forma crítica e elabora os melhores meios para resolvê-los. Isso pode significar acelerar os tempos de solicitação do servidor ou encontrar a melhor maneira de armazenar grandes conjuntos de dados com o mínimo de espaço em disco.

Este artigo visa ajudá-lo a entender os conceitos básicos de algoritmos e estruturas de dados e como implementá-los usando JavaScript.

O que é um algoritmo? Um algoritmo é um conjunto passo a passo de instruções para realizar uma tarefa. Suponha que você tenha problemas para acordar cedo e continue perdendo prazos. Como voce resolve isso? Ah! Definir alarmes. É assim que um algoritmo se parece.

As estruturas de dados, por outro lado, são formas de armazenar dados de forma eficiente.

Estruturas de dados e algoritmos (DSA) são tão vitais que são críticos para o desempenho geral de um computador. O algoritmo que você escolher determinará seu tempo de execução (Big O Notation) ou sua eficiência. Alguns DSAs populares são pesquisa binária, recursão, classificação, matrizes, listas encadeadas e tabelas de hash.

O que é pesquisa binária?

Suponha que você esteja procurando um nome no diretório de um país; começa com um J. Você pode começar no início (dos países "A") e continuar folheando as páginas até chegar à lista de países "J" (esses países são classificados em ordem alfabética). Se o país começar com um "Z", continue folheando até o final do diretório. Isso é conhecido como um algoritmo de pesquisa simples. Mas imagine se fosse um diretório de lista telefônica com mais de 100.000 números de telefone, isso é inimaginavelmente difícil. Como você otimiza isso? Pesquisa binária para o resgate.

O algoritmo de pesquisa binária recebe uma lista classificada de elementos como entrada e, se o elemento que você está procurando estiver na lista, a pesquisa binária retorna a posição em que está localizado, caso contrário, retorna nulo. Em vez de ir passo a passo para chegar ao Japão, a pesquisa binária divide essa matriz em várias partes e pesquisa cada uma delas de acordo.

Dessa forma, a busca é rápida.

Matrizes

Eles são uma coleção de elementos indexados por uma chave. Os elementos da matriz são armazenados sequencialmente, com a chave servindo como um identificador na coleção. Seus índices começam com 0.

Eles são super úteis porque recuperar ou classificar qualquer elemento leva um tempo constante O(1). ele também pode ser usado para implementar muitas outras estruturas de dados que colocam restrições adicionais sobre como os dados são manipulados. Uma string, por exemplo, pode ser implementada como um array de caracteres.

Aqui está uma implementação de arrays e pesquisa binária em JavaScript.

 function binary_search(list, item) { let guess = list.find(element => element == item); if (guess) { return guess + "\ncountry index no: " + list.findIndex(country => country === guess); } return null + ": element is not in the array" } console.log(binary_search(country_list, 'Japan')); // Japan | country index no: 109 console.log(binary_search(country_list, 'Cookie')); // null: element is not in the array

Algoritmo de Ordenação

A classificação raramente é usada por programadores. A maioria já é manipulada pela linguagem ou pelas bibliotecas em que eles codificam. A linguagem JavaScript, por exemplo, classifica arrays usando classificação por inserção, classificação por heap ou classificação rápida.

Heapsort é semelhante ao método de filtro de matriz Javascript. Ele divide a entrada em uma região classificada e uma região não classificada e move iterativamente os elementos para a região classificada. Aqui está um exemplo;

lista encadeada

Uma lista vinculada é uma estrutura de dados em que cada elemento contém dados e um ponteiro para o próximo elemento da lista. Uma característica distintiva de uma lista encadeada é que seus itens podem ser espalhados em qualquer lugar da memória. Isso não é verdade para matrizes. Veja alguns exemplos abaixo;

O que são Tabelas Hash?

Tabelas de hash são listas de elementos arbitrários em uma matriz. O elemento a ser armazenado ou sua chave é usado como um índice na matriz. Aqui está um exemplo:

A função hash converte a chave dos elementos a serem colocados em um hash e, em seguida, mapeia os elementos hash para um local especificado na tabela. Cada um desses elementos também pode ser uma submatriz de elementos arbitrários na tabela.

Recursão

A recursão é uma técnica de codificação usada em muitos outros algoritmos. É um atalho para código longo e pode não oferecer nenhum ganho de desempenho, exceto para o programador.

Suponha que você encontrou uma mala de tesouro. Para desbloquear esta caixa, você precisa pegar uma chave de uma caixa com outras caixas menores, que ainda podem conter outras caixas.

Uma abordagem é fazer uma lista de caixas para pesquisar e, em seguida, examinar cada uma dessas caixas. Se você encontrar uma chave, ótimo! Caso contrário, adicione a nova caixa vazia à lista de pilha para pesquisar mais tarde.

A recursão remove a etapa em que você adiciona a nova caixa vazia encontrada a uma lista de pesquisa. Ele chama o método de pesquisa imediatamente na nova caixa encontrada vazia. Aqui está um exemplo em Javascript;

 const suitCase = new Map(); suitCase.set('box-0', '') .set('box-1', '') .set('box-2', '') .set('box-3', '') .set('box-4', 'key') .set('box-5', '') .set('box-6', ''); function search (suit) { for (let [key, value] of suit) { if (value === 'key') { console.log(`Found ${value} at ${key}!`); } } } search(suitCase); // prints Found key at box-4!

Você encontrou a chave, Tada!

Em resumo, o DSA é uma ótima maneira de pensar de maneira eficaz como programador. Dá-lhe ferramentas para resolver problemas difíceis. Clique no link do repositório GitHub para baixar todos os trechos de código usados neste artigo. Hacking feliz!

Repositório de código GitHub