Big-O Notation: como entender complexidade de algoritmos (com exemplos)

Big-O Notation é uma forma padronizada de descrever o crescimento do tempo (e/ou memória) de um algoritmo conforme o tamanho da entrada aumenta. Em vez de medir milissegundos (que variam por máquina, linguagem e carga), Big-O foca no comportamento assintótico: o que acontece quando n fica grande.

Por que Big-O importa (na prática)

Porque muitas vezes o gargalo não está em “micro-otimização”, e sim em complexidade. Trocar um algoritmo O(n^2) por um O(n log n) costuma ser um ganho enorme e visível, enquanto trocar um for por um truque de linguagem pode nem aparecer no gráfico.

O que o Big-O ignora (e o que ele captura)

Big-O ignora constantes e detalhes de implementação. Por exemplo, O(2n) vira O(n). Isso não significa que constantes não importam; significa apenas que, para entradas grandes, o termo dominante é o que define o crescimento.

Classes comuns de complexidade

• O(1): tempo constante, independe de n.
• O(log n): cresce devagar; típico de busca binária.
• O(n): proporcional ao tamanho da entrada; um loop simples.
• O(n log n): comum em algoritmos eficientes de ordenação.
• O(n^2): loops aninhados; fica caro rápido.
• O(2^n) e O(n!): explosivos; normalmente inviáveis para n moderado.

Exemplos em código (tempo)

O(1): acesso por índice

// Pseudocodigo
valor = lista[10]  // independe do tamanho da lista

O(n): procurar um item

// Pseudocodigo
function contem(lista, alvo):
  for item in lista:
    if item == alvo:
      return true
  return false

Se a lista tem n elementos, no pior caso você percorre todos: O(n).

O(log n): busca binária (lista ordenada)

// Pseudocodigo
function buscaBinaria(listaOrdenada, alvo):
  ini = 0
  fim = listaOrdenada.tamanho - 1
  while ini <= fim:
    meio = (ini + fim) // 2
    if listaOrdenada[meio] == alvo: return meio
    if listaOrdenada[meio] < alvo: ini = meio + 1
    else: fim = meio - 1
  return -1

A cada iteração você corta o problema pela metade: isso é O(log n).

Comparação real: código não otimizado vs otimizado

Um erro muito comum em sistemas é fazer consultas repetidas (ou buscas repetidas) dentro de um loop. Isso cria complexidade quadrática sem perceber.

Caso 1: verificar se IDs existem (ruim: O(n*m))

Suponha que você tenha uma lista de pedidos e uma lista de IDs bloqueados, e quer marcar quais pedidos estão bloqueados.

// RUIM: para cada pedido, varre a lista de bloqueados
function marcaBloqueados(pedidos, idsBloqueados):
  for p in pedidos:               // n
    p.bloqueado = false
    for id in idsBloqueados:      // m
      if p.id == id:
        p.bloqueado = true
        break

Se n e m forem grandes, isso escala mal.

Caso 1 otimizado: usar conjunto/hash (bom: O(n + m))

// BOM: transforma a lista de bloqueados em conjunto para lookup O(1) medio
function marcaBloqueados(pedidos, idsBloqueados):
  bloqueados = set(idsBloqueados)  // m
  for p in pedidos:                // n
    p.bloqueado = (p.id in bloqueados)

Agora você paga O(m) para construir o conjunto e O(n) para marcar: O(n + m). Na prática, costuma ser um salto enorme de performance.

Ordenação e o famoso O(n log n)

Quando você precisa ordenar, algoritmos como mergesort/heapsort/quicksort (médio) ficam em torno de O(n log n). Isso é muito melhor do que ordenações simples (como bubble sort) em O(n^2).

// Exemplo conceitual: ordenar e depois buscar por busca binaria
ordenados = sort(lista)           // ~ O(n log n)
pos = buscaBinaria(ordenados, x)  // O(log n)

Às vezes “ordenar antes” parece mais caro, mas pode ser vantajoso se você vai fazer muitas buscas depois.

Big-O de memória (space complexity)

Nem tudo é tempo. Algumas otimizações trocam memória por velocidade. No exemplo do conjunto/hash, você usa memória extra para evitar loops aninhados. Isso costuma ser uma troca muito boa, desde que você controle o tamanho e o ciclo de vida dessas estruturas.

Armadilhas comuns

• Confundir média com pior caso: estruturas hash são O(1) em média, mas podem degradar em cenários patológicos.
• Micro-otimizar cedo: prefira melhorar a classe de complexidade primeiro, depois otimize detalhes.
• Ignorar I/O: query no banco dentro de loop geralmente é o pior gargalo (N+1).
• Strings e concatenação: concatenar em loop pode virar O(n^2) dependendo da linguagem.

Como usar Big-O no dia a dia

1. Identifique o tamanho dominante da entrada (o que é n?).
2. Conte loops e operações caras dentro deles (incluindo chamadas externas).
3. Busque estruturas adequadas: set/map para lookup, heap para top-k, etc.
4. Meça com dados reais (profiling) para validar a teoria.

Conclusão

Big-O é uma bússola para tomar decisões melhores de performance e manutenção. Ele não substitui testes e profiling, mas te ajuda a evitar armadilhas clássicas (como loops aninhados desnecessários) e a escolher estruturas de dados que fazem o sistema escalar com previsibilidade.