Conheça a notação de Big-O

Se você trabalha, ou sonha em trabalhar, com programação, a notação de Big-O, ou também conhecida como grande ó, ou Ózão pelos mais íntimos.

Ela é uma notação criada para facilitar a explicação da demora de um algoritmo, ou seja, ele explora quanto tempo demoraria para rodar um algoritmo.

Se fossemos comparar um algoritmo como o abaixo em dois computadores com hardwares diferentes, o que aconteceria?

def fatorial(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return fatorial(n - 1) * n

a) Eles rodariam no mesmo tempo

b) Eles rodariam em tempos diferentes

c) Não sabemos a resposta

A resposta C é a mais correta, já que não temos nenhuma informação sobre os hardwares que estão sendo usados para rodar este programa de cálculo de fatorial.

Tá, mas pra que raios eu uso o Big-O?

A notação de Big-O define os melhores, piores e médios cenários para um código. Ela não mede tempo de execução, logo, ela independe de hardware, arquitetura ou sistema operacional.

Resultado de imagem para big o
Nesta imagem, vemos a notação Big-O em ação! Algoritmos com a notação O(n!) são os piores a terem seu resultado, já os de

Usando o código acima, vemos que temos dois casos que o output sempre será o próprio número: os casos de input de 0 ou 1. Logo, para computar isso, basta apenas usarmos fazermos o if.

def fatorial(n):
    if n == 0:       O(1)
        return 0     O(1)
    if n == 1:       O(1)
        return 1     O(1)

Como a saída é fixa e sempre sabemos qual será seu resultado, não importando se é 0 ou 1, o cenário de execução para este caso será sempre o mesmo, o melhor. Ou seja, O(1).

Já a segunda parte desta função depende do seu número de iterações que devem ser feitas.

    if n > 1:                             O(1)
        return fatorial(n - 1) * n        O(n)

Pelo return ter chamado a função N vezes, e ela ser processada estas N vezes, o algoritmo tem um cenário de execução O(N) para o pior caso.

f(6) → f(5) → f(4) → f(3) → f(2) → f(1) → f(0)
f(6) → f(5) → f(4) → f(3) → f(2) → f(1)
f(6) → f(5) → f(4) → f(3) → f(2)
f(6) → f(5) → f(4) → f(3)
f(6) → f(5) → f(4)
f(6) → f(5)
f(6)

Alguns casos da notação são:

  • O(1) – quando o resultado é fixo, ou seja, o processamento é constante, não importa o valor que seja colocado no algoritmo como input. Por exemplo um hashmap (estrutura base do dicionário do python) é O(1).
  • O(N) – Um for simples (sem outro encadeado) é O(N), já que ele itera dentro de um iterável.
  • O(N^2) – ele ocorre quando acontecem 2 iterações encadeadas, ou seja um for dentro de for, por exemplo.

E você, gostou deste post? Se sim, compartilhe com seus amigos e família!

Autor: Vinicius Mesel

Ex-desenvolvedor de sistemas para bancos de investimentos. Trabalhou com mesas de investimentos e áreas de atendimento a grandes riquezas automatizando processos com Python. Também atuou como pesquisador de bioinformática no Instituto Butantan e hoje é CEO da RecrutaDev.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *