Como a Estrutura do Código Revela Complexidade

Como Identificar Big O a partir do Código

Big O está escondido na forma do seu código. Quatro padrões cobrem a maioria dos casos:

Loop único sobre N itens: O(N)

# O(N): uma passagem pela lista
for item in list_of_n_items:
    process(item)

Loops aninhados, cada um sobre N itens: O(N²)

# O(N²): cada item emparelhado com todos os outros itens
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Busca com tempo constante: O(1)

Acesso por índice de array, busca em tabela hash — uma etapa independentemente do tamanho.

Dividir e conquistar (corte o problema pela metade a cada etapa): O(log N)

Busca binária: cada verificação reduz pela metade os itens restantes.

---

O(N²) escondido: uma lista dentro de um loop

# Parece O(N) mas na verdade é O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scans all of visited: O(N)
        visited.append(item)  # o loop todo: O(N²)

A linha if item not in visited examina cada elemento de visited a cada iteração. Uma varredura de lista custa O(N). Um loop que executa N vezes, cada um fazendo trabalho O(N): O(N) × O(N) = O(N²).

Este padrão aparece em mais de 1.000 projetos de código aberto. A correção leva um caractere: substitua visited = [] por visited = set(). Testes de pertencimento de conjunto custam O(1), não O(N). Uma mudança. Os mesmos resultados. 1.000× mais rápido em N=1.000.

Classifique e Corrija Este Código

Leia este código:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

A Teoria Encontra a Prática

Big O na Prática

Big O não é apenas teoria. Ele separa programas que terminam em segundos de programas que levam 17 minutos — na exata mesma tarefa.

Exemplo real: detecção de ciclo de dependência em um sistema de construção.

Quando você instala software, seu computador resolve um gráfico de dependências: o pacote A precisa de B, B precisa de C, & assim por diante. Um sistema de construção verifica este gráfico para ciclos.

Um algoritmo de detecção de ciclos O(N²) funciona bem em N=100 pacotes. Em N=50.000 pacotes (um projeto real): leva 17 minutos. A correção O(N): 10 segundos.

Este defeito exato existe em GHC (compilador Haskell), pip (gerenciador de pacotes Python), Maven (sistema de construção Java), Cargo (gerenciador de pacotes Rust), & mais de 1.000 outros projetos.

Não porque seus autores foram descuidados. visited = [] foi escrito quando N era pequeno. O código calcificou. N cresceu. Ninguém notou até que a construção levasse meia hora.

Big O é o vocabulário que permite nomear o que aconteceu — & corrigi-lo.

---

Quer explorar mais profundamente? Nosso curso unhamming inclui um capítulo completo sobre Big O, MOAD-0001 (um defeito real O(N²) encontrado em mais de 1.000 projetos de código aberto), & por que nomear um padrão permite encontrá-lo em todos os lugares. Veja O Capítulo Perdido: Complexidade Algorítmica.

Preveja os Tempos de Construção

Um sistema de construção usa detecção de ciclos O(N²).

Tempos de construção medidos:

- N=100 pacotes: 0,01 segundos

- N=1.000 pacotes: 1 segundo

Para O(N²): o tempo se dimensiona como (N_novo / N_antigo)².

Para O(N): o tempo se dimensiona como (N_novo / N_antigo).