Big O Notation

Definição

Quando se estuda algoritmos, é comum ouvir dois termos, time complexity e space complexity. Eles se referem respectivamente à quantidade de tempo que um algoritmo leva para ser concluído e à quantidade de memória utilizada para concluir um algoritmo dado input de tamanho N.

Big O Notation é uma notação para analisarmos tanto a time complexity quanto a space complexity de um algoritmo, dentre muitas outras, geralmente considerando o pior cenário. É importante conhecer Big O para entendermos a performance de um algoritmo, quanto para melhorá-lo.

Complexidades Mais Comuns

Pense no valor dentro de parênteses como a quantidade de vezes em que seu algoritmo será executado a depender do tamanho do seu input.

Nesse caso, O (1) é tempo constante, sempre vai levar a mesma quantidade de tempo independente do input. Um exemplo de um algoritmo de tempo constante é uma simples operação matemática:

def sum(n): 
    return n * 2

Ou seja, O (log N) trata-se de um algoritmo que dado um input será executado literalmente log(N) vezes, o que é muito devagar, log(1000000) é cerca de apenas 20 execuções! Um algoritmo bem famoso que é O (log N) é a busca binária.

O (N) é um algoritmo de tempo linear, ou seja, cresce linearmente com o tamanho do input, um clássico for loop percorrendo um array de tamanho N por exemplo:

for i in n:
    print(i)

O (K log N) é um algoritmo que vai ser executado K * log (N), por exemplo, fazer K buscas binárias.

O (N^2) é uma complexidade de tempo quadrática, ou seja, para o input N, será executado Nˆ2 vezes.

for i in range(1, N + 1):
  for j in range(1, N + 1):
    print(i, j)

O (2^N) é um algoritmo, literalmente, exponencial, cresce insanamente rápido.

def Fib(n):
  if n == 0 or n == 1:
    return 1
  return Fib(n - 1) + Fib(n - 2)

O (N!) cresce ainda insanamente mais rápido do que um complexidade de tempo exponencial.