Dicas de algoritmos e estrutura de dados parte – 1

Olá tudo bem, hoje vamos falar sobre algoritmos e estrutura de dados básicos, para iniciarmos vamos para o seguinte cenário, temos uma lista de nomes não repetidos e temos que implementar um algoritmo que pesquise um determinado nome caso encontre retorne-o:

Valor
Angelica
Pedro
Paulo
Almeida
Bruna

Poderíamos implementar o seguinte passos de um algorítimo para resolver o problema:

      1.  Recebemos o nome para realizar a pesquisa.
      2.  Percorremos cada elemento da lista e comparamos se é igual ao nome da  pesquisa  informada.
      3. Se o nome for idênticos, paramos de percorrer a lista e retornamos o nome.

 

Esses passos funcionaria eficientemente com uma lista de poucos elementos, agora imagine que essa mesma lista chegue a ter 1 milhão de registros, creio que não seria prudente utilizar os mesmos passos informados, pois imagine a quantidade de tempo que esse algoritmo levaria para achar um nome no meio dessa lista, então podemos dizer que a nossa solução é ineficiente para esse problema.

Além do problema com o os passos informados podemos observar um outro problema, o problema com a nossa estrutura de dados pois ela armazena apenas o valor.

A solução para esse problema seria utilizarmos outra estrutura de dados contendo chave e valor.

Chave Valor
1 Angelica
2 Pedro
3 Paulo
4 Almeida
5 Bruna

Para essa nova estrutura de dados vamos fazer algumas modificações nos passos que utilizamos em nossa primeira solução:

      1. Recebemos o valor para realizar a pesquisa
      2. Convertemos o valor da pesquisa em um numero
      3. Pegamos esse numero gerado e pesquisamos pela chave da estrutura
      4. Caso a chave exista retornaríamos o valor encontrado

Com essas modificações, não precisaríamos percorrer a nossa estrutura para localizarmos o valor pois teríamos a chave do valor informado, nos exemplos que abordei falamos apenas de pesquisa, porém no próximo post  iremos desenvolver toda as operações para pesquisar,adicionar e  excluir os elementos na lista.

Conclusão: Muitas vezes o problema não está na nossa implementação e sim na estrutura que estamos utilizando. Uma frase do Linus Torvalds que cabe perfeitamente nesse post “Maus programadores se preocupam com o código. Bons programadores se preocupam com a estrutura dos dados e seus relacionamentos.”

LEAVE A COMMENT