Ao longo da minha leitura do Entendendo Algoritmos, eu tenho revisitado muitos conceitos e técnicas que eu já havia me esquecido que existiam e algumas que eu nunca consegui entender (até agora haha). Dentro desse post (e em mais alguns outros q vão vir ao longo da minha leitura) eu vou trazer esses conceitos sob uma análise de estudos pessoais.
O que é um algoritmo?
O mais simples possível é que:
"Um algoritmo é um conjunto de instruções que realizam uma tarefa."
Os algortmos são utilizados para facilitar o processo de resolver um problema.
Dado que, em um contexto de programação, um problema pode se repetir várias vezes em diferentes partes do seu sistema (ou da sua jornada técnica), ter uma solução (ou um meio para chegar na sua solução) já pré-definido aceleraria e facilitaria mais o processo, correto?
Bem, é ai que os algoritmos entram. Contudo, eles não se limitam à isso.
"Cada trecho de código poderia ser chamado de um algoritmo."
Porquê algoritmos são importantes?
Antes de partirmos para a prática, vamos entender porque é importante entendermos como os algoritmos funcionam.
Vamos imaginar um problema onde eu precise verificar se (a + b) é par.
Com certeza, deve ter várias maneiras de implementar uma solução para esse problema. Mas como eu sei se uma solução é melhor que outra?
Ainda que ambas retornem o resultado correto, uma pode ser mais rápida, a outra pode gastar menos memória.
A partir do estudo de algoritmos, podemos aprender diversas técnicas de análise que nos permitam comparar soluções e definir qual delas faz mais sentido para resolver o problema.
Ex: Ao precisar verificar se (a +b) é par. Se eu adicionar que preciso do resultado em até 2ms. De todos as soluções existentes, quais delas ainda solucionaria o meu problema?
Por isso é importante nos aprofundarmos além do que o algoritmo faz, e levar em conta também, como ele funciona.
Solucionando problemas com Algoritmos
Agora sim, vamos para prática! O primeiro algoritmo que vamos dar uma analisada é o de Pesquisa Binária. Ele facilita o processo de busca em listas ordenadas.
Pesquisa Binária
Vamos introduzir com um exemplo que o livro trás:
Você está procurando um nome (Mabel) em uma agenda com 100 contatos. Você poderia começar da letra A e ir descendo até chegar na letra M. Mas, é mais provável que você comece ali pela metade da lista, porquê é mais perto de onde a letra M fica.
Bem.. vamos destrinchar:
Problema: Achar um nome na minha agenda de contatos.
Solução: Começar da metade da lista para achar o resultado mais rápido.
Isso tem nome e é Pesquisa Binária.
"Pesquisa Binária é um algoritmo de busca que recebe uma lista ordenada de elementos e retorna a localização do item que você está buscando, caso ele esteja na lista."
Então...
Ex: Se entre 1 e 10, eu quero saber onde está o número 5, ele vai me retornar a posição dele da lista. E se eu quiser saber onde está o número 21, ele não vai me retornar nada.
Porquê Pesquisa Binária e não Pesquisa Simples?
Lembra do exemplo das diversas soluções para verificar se (a + b) é par? Então, mesmo conceito. Ao comparar ambas, a Pesquisa Binária vai resolver meu problema da agenda de contatos muito mais rápido.
Mas... como eu sei que isso é verdade?
Na Pesquisa Simples, o que pode acontecer é:
Ex 1: Eu querer o nome Aaron e o algoritmo ir la num pulo e me devolver que é o primeiro contato da lista.
Ex 2: Eu querer o nome Zakarias, o último contato.
E é ai (Ex 2) que as coisas complicam...
Na Pesquisa Simples, meu algoritmo vai ir la, de um em um, até o fim da lista para poder me falar, que Zakarias ta lá na última posição, levando mais tempo.
Já na Pesquisa Binária, começando pelo meio, se o nosso chute não for a resposta, é só verificar se ta mais para cima ou para baixo, eliminar a outra metade e partir do meio novamente.
Ex: Eu ainda quero o contato de Zakarias (100). Se começarmos do contato 50, vemos que o 100 ta mais pra cima. Então agora, eu busco entre 50 e 100, e minha nova metade é 75. E assim sucessivamente até que o resultado seja exibido.
Então, enquanto na Pesquisa Simples, foi preciso 99 etapas. Na Pesquisa Binária, foi preciso somente 7. Uma baita diferença né?!
Obs: O número de etapas de uma Pesquisa Simples é igual ao tamanho da lista (n). Enquanto o número de etapas de uma Pesquisa Binária é log2(n).
Como implementar um algoritmo de Pesquisa Binária?
O exemplo abaixo foi originalmente implementado no livro. A única coisa alterada é a sintaxe, pois abaixo está em #Dart.
Top comments (5)
Eu discordo um pouco do algoritmo de pesquisa binária ser muito mais rápido que a pesquisa simples. Na verdade, isso é válido para a maioria dos casos, mas não todos. Imagine uma lista com muitos itens, o algoritmo de pesquisa binária tende a fazer algo em torno de
log2 ncomparações até encontrar a resposta, já a pesquisa simples pode fazer aténcomparações, mas só para os últimos elementos, os elementos do meio tende a sern/2comparações, e para os primeiros itens ele tende a fazer algumas poucas comparações, então para os primeiroslog2 nitens da lista, a pesquisa simples pode fazer menos comparações que a pesquisa binária, portanto ser mais rápido. Isso pode ser melhor observado quando se separa a complexidade em três: melhor caso, pior caso e caso médio (ou caso esperado), isso com entradas construídas especialmente para que o algoritmo rode o mais rápido possível, o mais demorado possível... e isso para cada algoritmo.Esse post ficou bom demais, parabéns! Vai ser massa participar dessa leitura.
Ótimo artigo, Mabel!
Comprei o livro sem saber nada, estou com medo de começar a ler e não conseguir entender nada, pois não sei nada de programação e comprei o livro para começar a estudar de verdade a programação e ano que vem começarei a faculdade de ADS, quero saber se vale a pena eu começar a ler o livro hoje?
É um livro muito tranquilo de ler, mesmo se você está no começo. Se acabar surgindo dúvidas, vai conversando com a comunidade e usa de oportunidade para aprender coisas novas. Acredito que só tem vantagens!!