O que é notação Big-O?

gurinho

Você já se perguntou por que um programa que você escreveu demorou tanto para ser executado? Talvez você queira saber se pode tornar seu código mais eficiente. Compreender como o código é executado pode levar seu código para o próximo nível. A notação Big-O é uma ferramenta útil para calcular o quão eficiente seu código realmente é.

O que é notação Big-O?

A notação Big-O fornece uma maneira de calcular quanto tempo levará para executar seu código. Você pode cronometrar fisicamente quanto tempo seu código leva para ser executado, mas com esse método, é difícil captar pequenas diferenças de tempo. Por exemplo, o tempo que leva entre a execução de 20 e 50 linhas de código é muito pequeno. No entanto, em um programa grande, essas ineficiências podem aumentar.

A notação Big-O conta quantas etapas um algoritmo deve executar para medir sua eficiência. Abordar seu código dessa maneira pode ser muito eficaz se você precisar ajustá-lo para aumentar a eficiência. A notação Big-O permitirá que você meça diferentes algoritmos pelo número de etapas necessárias para executar e compare objetivamente a eficiência dos algoritmos.

Como você calcula a notação Big-O

Vamos considerar duas funções que contam quantas meias individuais há em uma gaveta. Cada função pega o número de pares de meias e retorna o número de meias individuais. O código é escrito em Python, mas isso não afeta como contaríamos o número de etapas.

Algoritmo 1:

 def sockCounter(numberOfPairs):
 individualSocks = 0
 for x in range(numberOfPairs):
 individualSocks = individualSocks + 2
 return individualSocks

Algoritmo 2:

 def sockCounter(numberOfPairs):
 return numberOfPairs * 2

Este é um exemplo bobo e você deve saber facilmente qual algoritmo é mais eficiente. Mas para praticar, vamos examinar cada um.

RELACIONADO: O que é uma função na programação?

O Algoritmo 1 tem muitas etapas:

  1. Ele atribui um valor de zero à variável individualSocks.
  2. Ele atribui o valor um à variável i.
  3. Ele compara o valor de i com numberOfPairs.
  4. Ele adiciona dois a individualSocks.
  5. Ele atribui o valor aumentado de individualSocks a si mesmo.
  6. Ele aumenta i em um.
  7. Em seguida, ele retorna pelas etapas 3 a 6 pelo mesmo número de vezes que (individualSocks – 1).

O número de etapas que temos que completar para o algoritmo um pode ser expresso como:

 4n + 2

Existem quatro etapas que devemos concluir n vezes. Nesse caso, n seria igual ao valor de numberOfPairs. Existem também 2 etapas que são concluídas uma vez.

Em comparação, o algoritmo 2 tem apenas uma etapa. O valor de numberOfPairs é multiplicado por dois. Nós expressaríamos isso como:

 1

Se ainda não estava aparente, agora podemos ver facilmente que o algoritmo 2 é um pouco mais eficiente.

Análise Big-O

Geralmente, quando você está interessado na notação Big-O de um algoritmo, está mais interessado na eficiência geral e menos na análise de granulação fina do número de etapas. Para simplificar a notação, podemos apenas declarar a magnitude da eficiência.

Nos exemplos acima, o algoritmo 2 seria expresso como um:

 O(1)

Mas o algoritmo 1 seria simplificado como:

 O(n)

Este instantâneo rápido nos diz como a eficiência do algoritmo um está ligada ao valor de n. Quanto maior o número, mais etapas o algoritmo precisará concluir.

Código Linear

Como não sabemos o valor de n, é mais útil pensar sobre como o valor de n afeta a quantidade de código que precisa ser executada. No algoritmo 1, podemos dizer que a relação é linear. Se você plotar o número de etapas versus o valor de n, obterá uma linha reta que sobe.

Código Quadrático

Nem todos os relacionamentos são tão simples quanto o exemplo linear. Imagine que você tenha um array 2D e gostaria de pesquisar um valor no array. Você pode criar um algoritmo como este:

 def searchForValue(targetValue, arraySearched):
 foundTarget = False
 for x in arraySearched:
 for y in x:
 if(y == targetValue):
 foundTarget = True
 return foundTarget

Neste exemplo, o número de etapas depende do número de arrays em arraySearched e do número de valores em cada array. Portanto, o número simplificado de etapas seria n * n ou n².

Esta relação é quadrática, o que significa que o número de passos em nosso algoritmo cresce exponencialmente com n. Na notação Big-O, você escreveria como:

 O(n²)

RELACIONADO: Ferramentas úteis para verificar, limpar e otimizar arquivos CSS

Código Logarítmico

Embora existam muitos outros relacionamentos, o último relacionamento que veremos são os relacionamentos logarítmicos. Para refrescar sua memória, o log de um número é o valor expoente necessário para alcançar um número dado uma base. Por exemplo:

 log 2 (8) = 3

O log é igual a três porque se nossa base fosse 2, precisaríamos de um valor de expoente de 3 para chegar ao número 8.

Portanto, o relacionamento de uma função logarítmica é o oposto de um relacionamento exponencial. À medida que n aumenta, menos novas etapas são necessárias para executar o algoritmo.

À primeira vista, isso parece contra-intuitivo. Como as etapas de um algoritmo podem ficar mais lentas do que n? Um bom exemplo disso são as pesquisas binárias. Vamos considerar um algoritmo para pesquisar um número em uma matriz de valores únicos.

  • Começaremos com uma matriz de pesquisa da ordem do menor para o maior.
  • A seguir, verificaremos o valor no meio do array.
  • Se o seu número for maior, excluiremos os números menores em nossa pesquisa e se o número for menor, excluiremos os números maiores.
  • Agora, veremos o número do meio dos números restantes.
  • Novamente, excluiremos metade dos números com base no fato de nosso valor alvo ser maior ou menor do que o valor médio.
  • Continuaremos esse processo até encontrarmos nosso alvo ou determinarmos que ele não está na lista.

Como você pode ver, como as pesquisas binárias eliminam metade dos valores possíveis a cada passagem, à medida que n fica maior, o efeito no número de vezes que verificamos o array quase não é afetado. Para expressar isso na notação Big-O, escreveríamos:

 O(log(n))

A importância da notação Big-O

A nação Big-O oferece uma maneira rápida e fácil de comunicar a eficiência de um algoritmo. Isso torna mais fácil decidir entre diferentes algoritmos. Isso pode ser particularmente útil se você estiver usando um algoritmo de uma biblioteca e não souber necessariamente a aparência do código.

Quando você aprende a codificar pela primeira vez, começa com funções lineares. Como você pode ver no gráfico acima, isso o levará muito longe. Mas, à medida que você se torna mais experiente e começa a construir códigos mais complexos, a eficiência começa a se tornar um problema. Uma compreensão de como quantificar a eficiência de seu código fornecerá as ferramentas necessárias para começar a ajustá-lo para eficiência e pesar os prós e os contras dos algoritmos.