Big O Notation
Imagine que esteja escrevendo uma nova função. Agora imagine que você existam várias
formas de implementar uma mesma função. Como determinar qual a melhor forma?
Por exemplo, para escrever uma função que recebe uma string e retorna uma cópia
da mesma de trás para frente. Existem várias abordagens e soluções diferentes.
Daí você pode pensar: “Quem se importa desde que funcione?”. Porém quando
estamos falando de grandes quantidades de dados ou softwares para dispositivos
IoT com menor poder de processamento, performance pode poupar tempo e melhorar a qualidade significativamente. Portanto, é importante possuirmos um vocabulário para comparar e
falar sobre a performance de nossos códigos. Outro ponto é que quando o nosso
código se torna lento ou quebra, saber identificar as partes do código que
podem ser ineficientes nos ajudam a resolver o problema.
Mas
então outra questão se apresenta: O que significa dizer que um código performa
melhor do que outro? Ser mais rápido? Ser mais legível? Ocupar menos memória?
No caso de pensarmos em medir o tempo, temos alguns problemas a considerar. Os
computadores são diferentes e possuem poder de processamento diferentes também.
Realizando testes de tempo até mesmo em uma mesma máquina irá apresentar
registros de tempo de processamento diferentes. Para algoritmos rápidos, as
medidas de tempo podem não ser precisas o suficiente. Mas se não o tempo, então
o quê? Bom, ao invés de contar o tempo de processamento, podemos contar a
quantidade de operações que o computador precisa realizar!
Para
exemplificar, suponha que queremos somar todos os números de zero até n. Uma
forma de fazer isso é utilizando um loop for e um totalizador. Neste caso, o
computador irá realizar uma operação de soma para cada valor de n. Não é
difícil perceber que conforme o valor de n seja maior, maior será também o
esforço computacional necessário para realizar a soma. Para esse algoritmo
dizemos que seja ‘da ordem de n iterações’ ou que possui BigO igual a n, ou
ainda O(n).
Outra forma de implementar essa
solução é através do algoritmo abaixo. Neste caso, não importa o valor de n. Se
n=10, n=100 ou n=1000, serão necessárias três operações apenas, possuindo uma
quantidade constante de operações ou O(1).
Loops aninhados são um exemplo de
O(n²). Para cada valor de i, n * j operações serão executadas.
Então o Big O notation nos
permite expressar e comparar o quanto o esforço computacional cresce conforme o
valor de entrada cresce. Não nos importamos aqui com detalhes, mas apenas a
tendência de crescimento. Imagine um O(n) comparado a um O(2n+5) com um O(n²).
Para n=1000:
- O(n) = 1000 iterações
- O(2n+5) = 2005 iterações
- O(n²) = 1000000 de iterações
- O(n) = 1000000 iterações
- O(2n+5) = 2000005 iterações
- O(n²) = 1000000000000 de iterações
Percebe como a
ordem de comparação não muda muito para O(n) e O(2n+5), mas muda muito para
O(n²)? Alguns dos tempo de execução mais comuns são:
- O(n²)
- O(n log n)
- O(n)
- O(log n)
- O(1)
O Big O mais difícil de
visualizar acredito que seja os que contém logaritmo. Um exemplo de algoritmo
que possui O(log n) é a busca binária. Leva este nome porque a cada iteração
dividimos o problema pela metade, como o algoritmo de procura de palavra no
dicionário que exemplifiquei no post sobre recursão. Junto à definição de Big
O, temos também a definição de Big Omega, que é a medida do melhor caso na
execução de um algoritmo. Por exemplo, na busca binária, podemos encontrar a
palavra no dicionário logo na primeira página que abrimos. Diz-se então que o
Big Omega da busca binária é Omega(1).
Acredito
que conhecer Big O e o Big Omega é fundamental para não apenas comparar, mas também para
pensar na eficiência dos códigos que escrevemos para que possamos escrever
códigos cada vez melhores e mais performáticos.
Referências
Big O Notation – Using not-boring
math to measure code’s efficiency
Disponível em:
Acesso em: 29/02/2020
Notação Big-O
Disponível em:
Acesso em: 29/02/2020
Algorithms – CS50x
Disponível em:
Acesso em: 29/02/2020
Comentários
Postar um comentário