Importância da análise de complexidade de algoritmos

Presumindo que todos os contatos já estejam em ordem alfabética, vamos ao trabalho!

Busca linear

Para facilitar e evitar erros, vamos apenas percorrer a lista em busca de um contato. Vamos supor que foi solicitado o contato da Wanessa:

Percebemos que percorremos toda a lista até achá-la. Até aqui sem problemas, certo? A solução atual funciona perfeitamente e com um desempenho aceitável. Agora imagine que nossa solução foi vendida para uma empresa multinacional que tenha milhares ou até milhões de contatos.

Para achar o Rodrigo agora, tivemos que percorrer milhões de contatos! O que não parece ter um bom desempenho, não é?

Busca Binária

Então vamos pensar numa solução melhor. Sabemos que a lista já está em ordem alfabética, então que tal dividi-la? Podemos comparar o contato que procuramos com o contato do meio, verificar a direção que precisamos tomar e eliminar o restante da lista. Portanto, seguiremos os passos descritos para achar o contato da Paula:

Selecionamos o contato do meio, Nico, para comparar com o contato que buscamos, Paula, e descartamos a metade da lista na qual temos certeza que não estará a pessoa procurada.

Já nesta iteração, mais uma vez escolhemos o contato do meio da lista, Rodrigo, e verificamos em qual direção temos que ir, descartando a outra metade. Assim achamos Paula.

E qual seria a diferença entre as duas soluções?

Perceba que na primeira solução, independentemente do tamanho da lista, devemos percorrer todos os contatos até acharmos aquele que desejamos. Se tivermos sorte, o contato que procuramos pode ser o primeiro de todos. Porém, se não tivermos essa sorte e procurarmos pelo último contato, teremos que percorrer toda a lista, o que seria o pior caso para o algoritmo. Pensando assim, podemos determinar que nossa primeira solução executa uma função que cresce de forma linear ao tamanho da lista de contatos.

Já na segunda solução, percebemos que a cada iteração eliminamos metade da lista, fazendo com que não seja necessário percorrê-la por completo. Dessa forma otimizamos a busca. Essa solução executa uma função que cresce em taxa logarítmica considerando o tamanho da lista de contatos.

Vamos visualizar a diferença entre as taxas de crescimento de algoritmo?

Agora fica claro que a solução logarítmica tem um desempenho extremamente mais eficiente que a solução linear, e podemos confirmar através do gráfico acima, onde o eixo da quantidade de operações executadas pelas duas funções é bastante desigual.

Aprofundando mais um pouco, em uma lista com 1 milhão de contatos é necessário realizar apenas 20 operações de comparação até encontrar o contato desejado. Com isso podemos começar a entender o quão importante é a análise da complexidade de algoritmos.

Utilizamos um exemplo bem simples agora, mas imagine ter que desenvolver uma feature de busca de alunos da Alura para que seja possível realizar a autenticação no site ou app. Qual solução você usaria?

Gostou do tema? Temos uma série de novos artigos explicando mais sobre análise da complexidade de algoritmos. Nos próximos abordaremos a implementação dos algoritmos de busca explicados anteriormente.