Acesse nossa Plataforma

Meu 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.

Caso você nunca tenha ouvido falar sobre Big O Notation, recomendo você ler um dos meus artigos anteriores, onde abordo o tema de uma maneira introdutória e simplificada. Isto pode te auxiliar a entender o porquê disto que vou te apresentar neste artigo.

Estarei exemplificando como calcular a complexidade de um algoritmo, de uma maneira simples e que n√£o te assuste ; )

Calculando um algoritmo

Primeiramente quero te mostrar o algoritmo que vamos usar de exemplo para nossa discuss√£o:

Calculando a Complexidade de um Algoritmo

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 deixo o resultado dessa conta:

Complexidade de um Algoritmo - Resultado do n√ļmero de linhas executado
‚Äú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 armazendo 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 parametro e a soma com 1 representa a √ļtima 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 5 posi√ß√Ķes.

Para exemplificar, temos uma tabelinha que vai nos ajudar a contar esse n√ļmero de vezes que passamos pela linha 7:

Image for post

Você deve estar se perguntando, por quê 20?… Deixa eu te mostrar qual foi o raciocínio usado para chegar a este valor.

Caso estejamos na primeria 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:

Complexidade de um algoritmo - progressão aritmiética

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:

Complexidade de um algoritmo - Execu√ß√Ķes

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:

Complexidade de um algoritmo - Somatória

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:

Algoritmo - Adaptação
Algoritmo - Adaptação final

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 estavamos fazendo n√£o ocorre. Logo nosso valor fica representado pela f√≥rmula:
Image for post
  • 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:

Image for post
Image for post
Image for post
Image for post
Image for post

Logo, no pior dos casos nosso algoritmo é O(n²). Tendo um comportamento exponencial, como exemplificado no gráfico abaixo:

Big O Notion

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 fazermos análises profundas, para entendermos o comportamento do nosso algoritmo e comprovarmos se é realmente escalável.

Se você não entendeu 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á ter necessidade de usar esta técnica se estiver lidando com problemas grandes, com milhares de entradas de dados por dia, onde cada milissegundo possa fazer a diferenç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 Serverless, 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 se preocupe caso voc√™ n√£o tenha se tornado o mestre matem√°tico das fun√ß√Ķes ap√≥s ler este artigo. Meu objetivo aqui era te trazer uma vis√£o mais profunda do assunto, fazendo com que sua maneira de analisar e escrever c√≥digo melhore um pouco.

Espero que tenha gostado!

Aproveite para aumentar seu conhecimento e leia o artigo sobre O que é realmente um algoritmo recursivo.

Agende uma conversa e saiba como podemos te ajudar