O nosso intuito nesse artigo é apresentar uma técnica muito interessante no mundo da computação, que pode te auxiliar, caso você esteja lidando com problemas de performance e as micro-otimizações sejam relevantes no seu projeto.
Exemplificaremos como calcular a complexidade de um algoritmo, de uma maneira simples e que não te assuste.
Calculando um algoritmo
Primeiramente queremos mostrar o algoritmo que vamos usar de exemplo para nossa discussão:
Logo, no pior dos casos nosso algoritmo é O(n²). Tendo um comportamento exponencial, como exemplificado no gráfico abaixo:
Como podemos ver, o objetivo desta função é nos retornar um array, que representa a média acumulada do nosso vetor como parâmetro.
A primeira coisa que devemos fazer, é começar a contar o número de vezes que cada linha será executada ao longo do processamento. Abaixo deixaremos o resultado dessa conta:
“n”representa o número de voltas que nosso loop irá rodar
Você deve estar se perguntando: “O que aconteceu aqui?”
Bem, vamos lá:
- Na linha 2, o número de vezes que ela é executada é apenas 1, pois durante nossa função não há nada que faça com que passamos por ela de novo. Apenas estamos armazenando um array vazio numa variável chamada M.
- Na linha 4, o número de vezes que vamos passar por ela, será n +1. Pois n representa o comprimento do nosso array como parâmetro e a soma com 1 representa a última validação que iremos fazer quando o valor de i for maior do que o valor de array.length. Perceba que não entramos dentro do loop, mas mesmo assim houve uma verificação, então ela é computada.
- Na linha 5, o número de vezes que será executada é igual ao total de vezes que entrarmos no loop. Logo seu valor é igual a n vezes.
- Agora na linha 7, a coisa começa a ficar mais interessante…
Na linha 7, sabemos que o número de vezes que ela será executada está totalmente ligado ao número de vezes que nosso primeiro loop irá executar. Então vamos imaginar que o valor do nosso parâmetro seja um vetor de 5posições.
Para exemplificar, temos uma tabelinha que vai nos ajudar a contar esse número de vezes que passamos pela linha 7:
Você deve estar se perguntando: por que 20? Vamos mostrar qual foi o raciocínio usado para chegar a este valor.
Caso estejamos na primeira volta do nosso primeiro loop, o valor de i será igual à 0. Ao chegarmos na linha do nosso segundo loop,declaramos uma variável j de valor inicial 0, então faremos a seguinte comparação, j ≤ i?
Se pararmos para pensar bem, o número de vezes que passaremos por essa linha será 2, pois na primeira j ≤ i é verdadeiro, mas na segunda, j ≤ i é falso,pois j passa a ter o valor de 1. Mas mesmo assim nós precisamos fazer a validação, logo passamos por essa linha 2 vezes, uma como verdadeira e entrando dentro do loop e outra como falsa em que não entramos dentro do loop, mas houve a validação. E assim por diante…
Beleza, agora que sabemos que o valor de vezes que passamos pela linha 7 é igual à 20, você deve estar se perguntando:
“O que 20 tem a ver com (n * (n + 1) / 2) + n ?”
O porquê dessa relação
Analisando esse comportamento, o que temos aqui é uma progressão aritmética. Para comprovar isto, precisamos aplicar nossos valores na seguinte fórmula abaixo:
Sendo 5 o número de execuções do nosso primeiro loop, 2 o primeiro número de execuções do segundo loop e 6 o último número de execuções do segundo loop. Teremos o seguinte resultado:
Sabemos então que o que temos aqui é uma somatória, pois a soma dos termos possui a mesma razão, e para isso utilizaremos a seguinte fórmula abaixo:
Mas se tentarmos aplicar nossos valores nessa fórmula o resultado não é o esperado, (que no caso seria 20), então precisamos realizar a seguinte adaptação:
E pronto,somando 5 finalmente chegamos ao valor esperado. Mas, por que?
Bem, essa soma não foi uma simples gambiarra, o motivo lógico dela está na tabela que montamos acima.
Se repararmos bem, podemos ver que à cada 1x que rodamos o primeiro loop rodamos 2x o segundo loop, tendo um acréscimo de 1 ao final da conta. Após todas as execuções veremos que temos 5 execuções a mais e são exatamente essas que estamos somando no final da fórmula.
- Na linha 8, o número de vezes agora não será afetado pelo acréscimo que sofremos na linha 7. Justamente porque a verificação a mais que estávamos fazendo não ocorre. Logo, nosso valor fica representado pela fórmula:
- Na linha 11, o número de vezes que será executada é igual ao total de vezes que entrarmos no primeiro loop. Logo seu valor é igual a n vezes.
- Na linha 14, apenas temos uma execução, onde retornamos o array montado.
Agora que finalizamos a contagem, temos o custo de execução de cada linha da nossa função, tendo como entrada um vetor de tamanho n. Qual será então o custo total do nosso algoritmo?
Para calcularmos isto é muito simples, basta apenas somarmos todos os valores que chegamos:
Conclusão sobre a complexidade de um algoritmo
Provavelmente você não irá realizar uma conta como esta em cada trecho de código que você estiver escrevendo no seu dia a dia. Este tipo de técnica serve para fazermosanálises profundas, para entendermos o comportamento do nosso algoritmo ecomprovarmos se é realmente escalável.
Se você nãoentendeu o motivo de tudo isso e acha uma coisa muito teórica que nunca você vai usar na vida, talvez você esteja certo.
Provavelmente você só irá ternecessidade de usar esta técnica se estiver lidando com problemas grandes, com milhares de entradas de dados por dia, onde cada milissegundo possa fazer adiferença no seu sistema. Caso contrário, realmente não haverá necessidade.
Outro ponto interessante, é como isto pode vir a se tornar muito mais relevante no seu dia a dia, num futuro onde trabalharemos com Server less, onde você é cobrado pelo seu provedor de cloud computing pelo tempo de execução da sua função. Mas isto é assunto para outro artigo.
Não sepreocupe caso você não tenha se tornado o mestre matemático das funções após ler este artigo. Nosso objetivo aqui era te trazer uma visão mais profunda doassunto, fazendo com que sua maneira de analisar e escrever código melhore um pouco.
Esperamos que tenha gostado!
Aproveite para aumentar seu conhecimento e leia o artigo sobre O que é realmente um algoritmo recursivo.
