Complexidade de algoritmos (e de problemas)
Não é novidade que as empresas têm enfrentado um volume de tráfego de informações cada vez mais alto (e só tende a aumentar a cada dia que passa). Para lidar com esse volume, alternativas como arquitetura de micro-serviços, escalabilidade horizontal, adesão a cloud, containerização, entre outros, estão vindo à tona e estão sendo amplamente discutidos. No entanto, outro assunto com caráter mais teórico que tem sido muito discutido é o desempenho dos algoritmos em si.
Análise de algoritmos
Existe uma vasta literatura que discute análise de algoritmos com mais detalhes. Basicamente, muitas delas descrevem análise de algoritmos como o estudo da corretude e desempenho de algoritmos, o que é verdade. Porém, particularmente, eu gosto de pensar na análise de algoritmos como o estudo dos problemas que temos que resolver.
Por exemplo, considere o seguinte problema:
problema: ache o maior elemento dentro de um array de númerosentrada: [4, 23, 6, 7, 12, 2, 6, 100, 1, 0, 2, 4, 14, 20, 7]saída: 100
A primeira vista, o problema acima é fácil de ser resolvido. Discutimos abaixo 2 formas de resolve-lo:
- Ordenar o array e retornar o último elemento
- Iterar sobre o array e armazenar o maior de todos a cada iteração
Ambas resolvem o problema de forma correta e, para a dada entrada que é um array com 15 elementos, não há muitas diferenças quanto ao desempenho na prática. Porém, se tivermos arrays com um número grande de elementos, as soluções possuem uma diferença considerável quanto ao desempenho.
Antes de mais nada, vamos pensar sobre o problema em si, e esquecer um pouco as soluções propostas. O problema que temos é achar o maior elemento de um array de números. Para achar de fato o maior elemento, precisamos, necessariamente, checar cada elemento pelo menos uma vez. Isso traz a tona a noção de que o problema em si possui uma complexidade mínima para ser resolvido de forma correta, chamamos isso de complexidade do problema.
Voltando novamente ao problema dado, a complexidade mínima para resolve-lo de forma correta é de percorrer cada elemento do array pelo menos uma vez, caso contrário, se deixarmos de checar um único elemento, podemos deixar de fora o valor máximo e nosso algoritmo pode responder um valor errado.
Algoritmo ótimo
Dizemos que um algoritmo é ótimo quando: a complexidade do pior caso da solução é igual a complexidade mínima do problema.
Dado essa definição, a solução 2 é uma solução ótima para esse problema pois no pior caso, ela resolve checando cada elemento apenas uma única vez (a notação usada para isso é O(n) onde n é o tamanho do array). É importante frisar que podem existir mais de uma solução ótima para um mesmo problema, por exemplo, podemos resolver o problema acima iterando do início ao fim do array quanto do fim para o início e ambas as soluções são ótimas porque possuem complexidade no pior caso igual a complexidade mínima do problema.
Já a solução 1, apesar de correta e fácil de ser implementada, não é ótima. A complexidade da ordenação de um array é O(n * log (n)), o que é maior que O(n). Para entradas pequenas como o exemplo dado, as 2 soluções não divergem tanto quanto ao desempenho (ambos respondem em milisegundos), no entanto, quando temos arrays grandes, a solução 1 começa a demorar consideravelmente para responder se comparado com a solução 2.
Conclusão
Analisar algoritmos é uma skill que requer prática. Existe um amplo acervo na literatura que discute análise de algoritmos e minhas referencias favoritas são: The algorithm design manual e Introduction to Algorithms. No entanto, é preciso fazer um exercício diário para tentar analisar os problema que temos que resolver no dia-a-dia antes de pensarmos em qualquer solução. Entender o problema em si e a sua complexidade mínima é a base para escolhermos estruturas de dados e estratégias que desenham soluções eficientes. Não é a toa que empresas procuram cada vez mais desenvolvedores com esse perfil hoje em dia.
A medida que aprendemos as complexidades de muitos problemas começamos a enxergar os limites computacionais para resolver cada um deles. Perguntas como "da pra melhorar?" começam a serem mais fáceis de serem respondidas dado que cada problema tem um limite mínimo que devemos respeitar se queremos responder de forma correta (existem problemas onde aproximações da resposta correta é também aceitável).
