Como escrever códigos mais rápidos e escaláveis
Me deparei com essa pergunta um dia e pensei: Por que não escrever um artigo a respeito disso?
Dentro da matemática, existe uma notação chamada Big-O. Essa função descreve o comportamento limitante de uma função, quando o argumento tende a um valor particular ou ao infinito. Ficou confuso? Deixa que eu te explico!
Essa notação, quando trazida para a programação, é uma forma de classificar o quão escalável é o seu código.
Como você pode observar, existe diferentes cores dentro do gráfico. Nós podemos interpretar essas cores como diferentes tipos de códigos escritos e o seu tempo de execução de acordo com a quantidade de inputs (dados colocados para rodar no seu código)
Logo, se você escreve um código e provê 100 milhões de dados para ele processar, e a complexidade do seu código é a vermelha (O(n²)), então seu código é muuuito lento e nenhum um pouco escalável.
O que as cores representam e como classificar um algoritmo no gráfico
Agora que vimos o gráfico e entender como a base da Big-O Notation funciona, vamos entender como funciona cada uma dessas notações/corzinhas e o que elas representam.
O(1) ou Cor Verde
O(1) ou complexidade de tempo constante. Essa é a mais simples de todas. Basicamente, não importa quantos dados você prover, 1 milhão ou 1, o algoritmo sempre levará o mesmo tempo para executar. Como você pode observar no gráfico, é a complexidade mais rápida e mais escalável de todos os outros.
E quais tipos de algoritmos são representados pelo O(1)?
Operações simples. Soma, multiplicação, divisão, subtração de valores, criar variáveis, retornar valores de uma map…
O(log N) ou Cor Amarela
A partir daqui, tudo vai depender da quantidade de inputs inseridos. Vamos entender!
Digamos que nós tenhamos uma lista de 0 a 10 já ordenada e queiramos procurar pelo número 8 dentro dessa lista. Oras, é simples, vamos rodar um for e checar se o número atual é o número que estamos procurando, vai funcionar!
Sim, vai funcionar, mas, a complexidade desse código será O(n), pois ele precisará passar por todos os inputs até chegar no valor que ele quer. Parece bobeira quando falamos de 0 a 10, mas, e se trocássemos para 0 a 2 milhões e quiséssemos o número 1.525.733? Passar por cada um dos números agora parece uma má ideia, não?
Para evitarmos esse gasto de desempenho a toa, podemos utilizar um algoritmo que se chama binary search e tem como o objetivo obter o número que desejamos em complexidade O(log N).
O binary search funciona de forma muito simples. Suponhamos que temos 0–10 em uma lista e estamos querendo o número 7. Ao invés de buscar o número 7 por cada elemento da lista, ele irá buscar pelo valor do meio da lista, que é o 5. Como sabemos que a lista está ordenada, então nós podemos descartar todos os valores anteriores ao cinco, dividindo a lista em 5 pra cima. Depois, pegamos o valor do meio e repartimos a lista ao meio novamente utilizando as mesmas regras anteriores. E, quando não houver mais nada para dividir ou não houver mais intervalos, então significa que encontramos o número 7.
O(n) ou Cor Azul
A velocidade do algoritmo é baseada na quantidade de dados inserido pelo usuário, simples. Quanto menos, mais rápido ele irá rodar, quanto mais dados, pior o desempenho.
Ou seja, o O(n) é uma curva linear, que aumenta o tempo de execução conforme a quantidade de dados.
E quais tipos de algoritmos são representados pelo O(n)?
Passar pelos elementos de uma lista, comparar duas strings…
Esse algoritmo é O(n), porque esse for executará até acabar todos os elementos da lista. Como temos 6 elementos, o código irá executar rapidamente. Entretanto, 1 milhão de elementos, faria com que demorasse muito mais tempo.
O(n²) ou Cor Vermelha
As coisas começam a ficar perigosas aqui. O n² é o a quantidade dos seus inputs elevada ao quadrado, n * n.
Ou seja, uma vez que você inserir uma array com 8 elementos, por exemplo, ela virará 64. Isso é ruim, muito ruim. Porque, se inserirmos 1 milhão de inputs, então virará 1 BILHÃO de inputs para processar.
E quais tipos de algoritmos são representados pelo O(n²)?
Bubble Sort, Insertion Sort, Selection Sort, passar por uma uma lista 2D… Vejamos um exemplo de código que busca pelo elemento repetido dentro da lista:
O segundo for irá rodar 8x para cada elemento do primeiro for, que também possuí 8 elementos, fazendo com que esse código passe por 64 elementos ao total.
A recomendação é que você evite códigos assim a qualquer custo, pois podem trazer um grande problema para a sua aplicação no futuro.
E sobre as outras notações?
Sim, existe outras, como a n!, n log n e 2^n. Mas acho que é bacana comentar sobre eles em outra oportunidade em um artigo mais aprofundado. A ideia nesse aqui é só passar uma visão geral sobre como a Big O Notation funciona.
Acho que chegamos ao fim de mais um artigo, espero que eu tenha conseguido te ajudar a entender um pouco mais sobre como funciona as notações e que agora você tenha um norte sobre complexidade de tempo de um código.
Nesse artigo, eu também citei alguns tipos de algoritmos de busca e de ordenamento conhecidos como o Linear Search, Bubble Sort… Mas acabei por não entrar a fundo, que tal em outra oportunidade? O que você acha?
Vou ficando por aqui, a gente se vê em breve. Até!
