Taxas de Crescimento, Não Custos Absolutos
Big O: Medindo Como O Custo Cresce Rapidamente
A notação Big O mede a taxa de crescimento do custo do algoritmo - não o custo absoluto.
A pergunta que a Big O responde: ao dobro do tamanho do input N, o trabalho é dobrado? Quadruplicado? Ficou plano?
A 'O' significa 'ordem de grandeza'. A expressão dentro do parênteses descreve a forma da curva de crescimento.
Classes de complexidade chave:
- O(1) — constante: o custo não cresce. Exemplo: procurar um valor por índice em um array. Independentemente de o array ter 10 itens ou 10 milhões, uma consulta é uma consulta.
- O(N) — linear: o custo cresce com o input. Exemplo: ler todos os itens em uma lista uma vez. Duplique a lista, duplique as leituras.
- O(N²) — quadrática: o custo cresce como o quadrado do input. Exemplo: comparar todos os itens com todos os outros itens. Duplique N, quadrifique o trabalho.
Tabela de comparação de crescimento:
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
Aos N=10 a diferença parece pequena. Aos N=1.000 o vão se torna enorme.
Compare O(N) com O(N²)
Use a tabela de comparação de crescimento acima.
Aos N=1.000: O(N) requer 1.000 operações. O(N²) requer 1.000.000 operações.
Como a Estrutura do Código Revela Complexidade
Como Identificar Big O a Partir do Código
Big O esconde na forma da sua código. Quatro padrões cobrem a maioria dos casos:
Laço único sobre N itens: O(N)
# O(N): uma passagem pela lista
for item in list_of_n_items:
process(item)Laços aninhados, cada um com N itens: O(N²)
# O(N²): cada item sendo parado com cada outro item
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Consulta de tempo constante: O(1)
Acesso a índice de array, consulta em tabela hash — um passo independente do tamanho.
Dividir e vencer (cortar o problema pela metade a cada etapa): O(log N)
Busca binária: cada verificação reduz a metade dos itens restantes.
---
Big O escondido: uma lista dentro de um laço
# Isso parece O(N) mas na verdade é O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # escaneia todos os elementos de visited: O(N)
visited.append(item) # o todo o loop: O(N²)A linha if item not in visited escaneia todos os elementos de visited em cada iteração. Um escaneamento de lista custa O(N). Um laço que corre N vezes, cada um fazendo O(N) de trabalho: O(N) × O(N) = O(N²).
Este padrão aparece em 1.000+ projetos de código aberto. A solução leva apenas um caractere: substitua visited = [] por visited = set(). A verificação de membro de conjunto custa O(1), não O(N). Uma mudança. 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)Teoria Encontra a Prática
Big O no Bairro
Big O não é apenas teoria. Ele separa programas que concluem em segundos de programas que levam 17 minutos - no mesmo trabalho exato.
Exemplo real: detecção de ciclo de dependência em um sistema de compilação.
Quando você instala software, seu computador resolve um gráfico de dependências: o pacote A precisa de B, B precisa de C e assim por diante. Um sistema de compilação verifica esse gráfico para detectar ciclos.
Um algoritmo de detecção de ciclo O(N²) funciona bem com N=100 pacotes. Com N=50.000 pacotes (um projeto real): leva 17 minutos. A correção O(N): 10 segundos.
Este defeito exato existe no GHC (compilador de Haskell), pip (gerenciador de pacotes Python), Maven (sistema de compilação Java), Cargo (gerenciador de pacotes Rust) e em mais de 1.000 outros projetos.
Não porque seus autores eram descuidados. visited = [] foi escrito quando N era pequeno. O código se calcificou. N cresceu. Ninguém percebeu até o build levar meia hora.
Big O é a linguagem que permite nomear o que aconteceu - e corrigi-lo.
---
Quer ir mais fundo? Nosso curso não-Hamming inclui um capítulo completo sobre Big O, MOAD-0001 (um defeito O(N²) realmente encontrado em 1.000 projetos de código aberto), e por que nomear um padrão permite que você o encontre em todos os lugares. Confira [O Capítulo Faltante: Complexidade Algorítmica](/en/un/unhamming_algorithmic_complexity).
Adivinhe os Tempos de Compilação
Um sistema de compilação usa detecção de ciclo O(N²).
Tempos de compilação medidos:
- N=100 pacotes: 0,01 segundos
- N=1.000 pacotes: 1 segundo
Para O(N²): o tempo aumenta proporcionalmente a (N_new / N_old)².
Para O(N): o tempo aumenta proporcionalmente a (N_new / N_old).