Um algoritmo é um conjunto de instruções que realizam uma tarefa. Cada trecho de código poderia ser chamado de um algoritmo, mas este livro trata dos trechos mais interessantes.
Aditya Y. Bhargava
Caso você esteja chegando no rolê de paraquedas, eu sugiro que inicie por este texto: Entendendo Algoritmos-introdução. No texto eu te dou um breve caminho das pedras amarelas para te ajudar a chegar ao tão sonhado entendimento de algoritmos.
Primeiro capítulo - introdução a algoritmos
Estamos iniciando este novo livro e logo de cara já te aviso que não, este não vai ser um resumo. Este livro já resumido demais. Diferente do livro do Código limpo, este livro é uma versão simplificada de todo o assunto envolvendo algoritmos. Porém, como sou uma mulher difícil (HAHAHAHA) vou dificultar um pouco as coisas, disponibilizando para quem preferir se aprofundar mais um material mais detalhado sobre o algoritmo estudado, sua complexidade e o cálculo.
No primeiro capítulo, o Bhargava nos apresenta conceitos introdutórios como big O notation, cálculo de logarítmo, e o primeiro algoritmo do livro, a busca binária.
Antes de falarmos da busca binária em si, vamos focar na busca. O ato de percorrer uma estrutura de dados procurando um valor dentre vários. O que chamamos de busca sequencial, a busca binária nada mais é que uma busca onde tentamos diminuir a quantidade de interações que o código vai ter.
Tá mas que interações são essas? vamos ao código:
def busca_seq(lista, p):
for i in lista:
if(i == p):
return i;
return 0
Vamos analisar o código. Ele é um código pequeno, uma busca simples em uma lista, retornando o primeiro que encontrar que possua o valor p. Para um código de execução normal, ele é consideravelmente pequeno, para um código que vai receber um trilhão de entradas, este código é custoso. Imagine se o p for encontrado no último valor da lista? teríamos feito um trilhão de interações para encontrar apenas um valor.
A busca binária nos dá o poder de diminuir a quantidade de interações por log(n). Compare os valores de crescimento dos dos gráficos:
As duas pesquisas são bastante utilizadas, porém o pulo do gato é saber quando você pode utilizar uma e quando pode utilizar outra. Normalmente, esta é uma das questões de várias sobre algoritmos que você vai se deparar em um desafio técnico ou entrevista técnica. Caso você queira aprofundar o conhecimento sobre os dois algoritmos:
Segundo capítulo - Ordenação por seleção
Neste capítulo, temos a introdução de dois tipos de estruturas de dados que são um pouco generalizadas para os novos programadores. O que de fato acontece é que poucos de nós tivemos o contato com as formas de listas e arrays da maneira que o livro apresenta.
Hoje na maioria das linguagens de programação, não existe o conceito de arrays com o tamanho fixo. O array acabou se tornando um híbrido de uma lista encadeada, ao qual sabemos o tamanho do array no momento em que o último objeto foi adicionado, adicionamos elementos de maneira que o seu tamanho se expande, e acessamos valores através do seu índice. Hoje linguagens como Javascript já possuem métodos como o Array.from() que nos entrega uma nova lista a partir de uma comparação ou na adição de um novo elemento no meio da lista.
O que parece muito bom para as nossas vidas de reles programadores de software é um pesadelo em questões de desempenho. Nem sempre as linguagens utilizam métodos de arrays (ou listas) que proporcionam o custo-benefício para o seu produto. Algumas consultas para inserção ou deleção podem custar O(n^2) para uma operação que em uma estrutura de dados "arcaica" seria O(1) ou talvez O(n). Daí vem a necessidade de se aprender a utilizar tipos brutos de estruturas de listas encadeadas ou arrays, para melhor desempenho.
Um exercício muito bom para fixação do conceito de array e lista encadeada é tentar fazer uma estrutura de dado híbrida entre as duas estruturas e calcular seu possível custo computacional em big O.
Para estudar mais sobre listas encadeadas e arrays e suas problemáticas, acesse este material:
Constantemente ligado a listas encadeadas e arrays, temos outro conceito que foi pouco abordado no livro. O conceito de filas e pilhas.
Fila é uma estrutura de dados que possui regras de inserção e processamento. O chamado FIFO, first in first out ou o primeiro que chega é o primeiro a sair, nos dita uma regra de inserção de dados nesta estrutura vai ser dada sempre ao final da estrutura, enquanto a sua remoção será sempre o primeiro elemento.
Para saber mais sobre a fila, acesse aqui
Já as pilhas, vai funcionar com a regra de inserção e processamento que chamamos de LIFO, last in first out, diferente das filas, a pilha não vai trabalhar com localização, e sim com o conceito espacial de Topo e Base. Como uma pilha de prato, quando você adiciona um prato a pilha, sempre vai ser adicionada ao Topo. No momento de lavar, também. Sempre vai sair o primeiro da fila.
Para saber mais da pilha, acesse aqui
Tá, agora vocês me perguntam o porquê de falar sobre estas estruturas? Para saber mais sobre o processamento de dados em um sistema operacional e acesso a memória.
Existe toda uma arquitetura de dados e acesso de informações que o sistema operacional utiliza, a utilização de filas e pilhas em memória é um dos assuntos que em algum momento da sua carreira vai te dar uma baita dor de cabeça (ou não, se você ficar limitado ao CRUD). Para saber mais sobre, acesse este material para processos e threads e este para saber mais sobre memória virtual e alocação.
Logo após o assunto de arrays e lista encadeada, o autor nos apresenta o algoritmo de ordenação mais utilizado e conhecido por todos os desenvolvedores, o algoritmo de seleção.
Mesmo sendo o mais conhecido, o selection sort não é o mais performático. Ele faz parte do conjunto de algoritmos de ordenação da base O(n^2) e fica problemático de executar se o número de itens for muito grande, podendo ocorrer estouro de memória.
Além do selection sort, temos dois outros algoritmos fáceis de aprender mas que o seu custo deve ser ponderado, o Bubble sort e o insertion sort. Caso queiram saber mais:
E para finalizar, a tia deixa uma dica. Sempre que possível, tente exercitar os conceitos em paralelo. Por exemplo, a ordenação sempre é necessária para que uma busca binária seja efetuada. Que tal criar um algoritmo que receba uma lista e ordene os seus itens para então fazer a busca de um item? Ou talvez você deseje adicionar a uma lista encadeada, itens de forma decrescente, onde o seu primeiro item será o maior valor. Você pode ordenar um array e utilizar métodos de pilha para remover e adicionar a uma lista encadeada como uma fila.
São exercícios assim que fixarão o conteúdo do livro a sua cachola. Além de tornar bem mais legal a implementação, fugindo do copy and paste infinito.
Bom, se vemos na próxima semana, onde irei problematizar mais uma parte deste livro "facinho". Se possível, reaja ao post, compartilhe e me deixe um comentário, falando sobre o que achou!
Top comments (8)
Vou repetir o comentário do Gabriel, mas é bom ressaltar, você tem um talento muito grande em tornar o assunto fluído e de fácil absorção. Na minha carreira, conheci poucos devs que conheciam bem estrutura de dados, para mim essa é a coluna principal da performance, conhecer o dado e assim saber percorre-lo da melhor maneira, não é um bicho de sete cabeças, mas existem tantos detalhes no processo.
Parabéns pelo texto, e obrigado pela gigantesca contribuição para a comunidade dev.
obrigada! eu tento muito simplificar as coisas pq sei o quanto é difícil entender um assunto desses de primeira se todos falarem somente o cientifiquês.
Gostei muito da abordagem, usando palavras simples pra tentar resumir áreas complexas de estudo, parabéns!
Obrigaada! Eu tento simplificar sempre
Parabéns você é top!!!
Obrigada 💙
Estudar algoritmos utilizando a notação Big-O pode fazer uma grande diferença, inclusive já fiz um teste onde adicionar uma linha reduziu o tempo de execução de quase 3 segundos para 0,1 segundos, só me baseando na análise feita com Big-O.
Mas eu discordo sobre o que você falou que o algoritmo de ordenação por seleção pode estourar a memória. Sim, pode ocorrer, porém algoritmos dados como mais eficientes teriam problemas primeiro. Para entender isso é necessário primeiro saber que um algoritmo tem uma complexidade de tempo de execução e outra complexidade de espaço (o quanto ele usará de memória), e essas complexidades podem ser diferentes, devendo ser analisadas separadamente. Dado isso, ao se analisar a ordenação por seleção, no quesito de memória, uma implementação otimizada terá apenas algumas variáveis de controle dos laços de repetição e uma variável auxiliar para realizar a troca dos valores, ou seja, uma quantidade fixa de memória que não irá variar conforme o tamanho da entrada do problema. Já algoritmos como mergesort criarão cópias em memória de partes, as vezes do mesmo tamanho, da lista que será ordenada, ou a quantidade de memória alocada depende de quantas chamadas recursivas, por exemplo numa possível implementação de quicksort recursiva. Isso faz com que esses outros algoritmos usem mais memória para tratar problemas maiores do que a ordenação por seleção. Se quiser dar uma olhada, eu tenho um texto que discute o assunto, mas com outros algoritmos.
Bravo, como sempre! 👏🏻