1. "Funciona" não é a mesma coisa que "funciona bem"
Até aqui, nos módulos anteriores, o critério de sucesso de um algoritmo foi simples: ele chega na resposta certa? Esse critério continua valendo, mas a partir de agora entra um segundo critério, igualmente importante: quão rápido ele chega lá quando a quantidade de dados cresce.
Isso parece um detalhe de otimização prematura, mas não é. Um algoritmo que percorre uma lista de 100 itens em uma fração de milissegundo pode, com uma pequena mudança na forma como ele está escrito, levar minutos para processar uma lista de 1 milhão de itens — mesmo fazendo, essencialmente, "a mesma coisa". A diferença não está no que o algoritmo faz, está em como o número de operações cresce conforme a entrada cresce.
É exatamente isso que a complexidade de algoritmos mede, e a notação usada para expressar essa medida chama-se Big O (lê-se "ó grande" ou "big ó").
Isso não é exclusivo de nenhuma linguagem. Um loop em JavaScript, um loop em Python e um loop em C# têm exatamente a mesma complexidade se fazem a mesma coisa — a notação Big O descreve o algoritmo, não a linguagem em que ele foi escrito.
2. A ideia intuitiva por trás do Big O
Big O responde a uma pergunta específica: se eu dobrar (ou multiplicar por 10, ou por 1000) o tamanho da entrada, o que acontece com o número de operações que o algoritmo executa? Não interessa o tempo exato em segundos — isso depende do processador, da linguagem, de quantos outros programas estão rodando ao mesmo tempo. O que interessa é a taxa de crescimento.
Por convenção, chamamos o tamanho da entrada de n. A pergunta
"quantas operações esse algoritmo faz?" vira uma função de n, e o
Big O descreve o formato dominante dessa função quando n fica
muito grande — ignorando constantes e termos menores, porque eles perdem relevância diante
do crescimento.
Não é preciso contar operação por operação para usar Big O no dia a dia. A pergunta prática é: "para processar isso, eu preciso olhar cada item uma vez? Duas vezes por item? Comparar cada item com todos os outros?" A resposta a essa pergunta já entrega a complexidade.
3. O(1) — tempo constante
Um algoritmo é O(1) quando o número de operações não depende do tamanho da entrada. Não importa se a entrada tem 10 ou 10 milhões de itens: o algoritmo faz a mesma quantidade de trabalho.
FUNÇÃO primeiroItem(lista)
RETORNE lista[0]
FIM FUNÇÃOPegar o primeiro item de um vetor é O(1): é um acesso direto por posição, não importa o tamanho do vetor. Verificar se um número é par ou ímpar também é O(1) — é uma única operação, sempre.
4. O(n) — tempo linear
Um algoritmo é O(n) quando o número de operações cresce na mesma proporção que o tamanho da entrada. Dobrou a entrada, dobrou (aproximadamente) o trabalho. O caso mais comum de O(n) é um único laço que passa por cada item da entrada uma vez.
FUNÇÃO soma(vetor)
total ← 0
PARA CADA item EM vetor
total ← total + item
FIM PARA
RETORNE total
FIM FUNÇÃO
Se o vetor tem 10 itens, o laço roda 10 vezes. Se tem 1 milhão, roda 1 milhão de vezes. O
trabalho cresce linearmente junto com n.
5. O(n²) — tempo quadrático
Um algoritmo é O(n²) quando, para cada item da entrada, ele precisa olhar todos os outros itens de novo. O padrão mais comum é um laço dentro de outro laço, ambos percorrendo (aproximadamente) a mesma entrada.
FUNÇÃO temDuplicado(vetor)
PARA i DE 0 ATÉ tamanho(vetor) - 1
PARA j DE 0 ATÉ tamanho(vetor) - 1
SE i ≠ j E vetor[i] = vetor[j] ENTÃO
RETORNE VERDADEIRO
FIM SE
FIM PARA
FIM PARA
RETORNE FALSO
FIM FUNÇÃO
Para cada item (n possibilidades), o algoritmo compara com todos os outros itens (mais n
possibilidades). O total de comparações é aproximadamente
n × n = n². Com 10 itens, isso são 100 comparações no pior caso.
Com 1000 itens, já são 1 milhão.
Laços aninhados nem sempre significam O(n²) — só significam isso quando os dois laços
percorrem uma entrada de tamanho proporcional a n. Um laço que
roda n vezes dentro de outro que roda sempre 5 vezes, fixo, é
O(n), não O(n²) — o 5 é uma constante e desaparece na notação Big O.
6. O(log n) — tempo logarítmico
Um algoritmo é O(log n) quando, a cada passo, ele consegue descartar metade dos dados restantes em vez de olhar item por item. É uma das complexidades mais eficientes que existem para problemas em que "olhar tudo" pareceria inevitável.
A intuição: pense em procurar uma palavra num dicionário físico. Você não folheia página por página a partir da primeira. Você abre no meio, vê se a palavra vem antes ou depois, descarta a metade errada, e repete o processo na metade que sobrou. A cada passo o problema fica pela metade do tamanho — por isso o crescimento é logarítmico, não linear. O capítulo 3 detalha esse algoritmo (busca binária) com pseudocódigo completo.
O que importa reter agora é a escala: dobrar o tamanho da entrada em um algoritmo O(log n) adiciona só mais um passo ao processo, não o dobro de passos.
7. Comparando o crescimento na prática
A tabela abaixo mostra, para diferentes tamanhos de entrada, aproximadamente quantas operações cada classe de complexidade exige. Os números tornam concreto por que essa diferença importa tanto quando os dados crescem.
| Complexidade | n = 10 | n = 1.000 | n = 1.000.000 |
|---|---|---|---|
| O(1) — constante | 1 | 1 | 1 |
| O(log n) — logarítmica | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) — linear | 10 | 1.000 | 1.000.000 |
| O(n log n) — linearítmica | ≈ 33 | ≈ 10.000 | ≈ 20.000.000 |
| O(n²) — quadrática | 100 | 1.000.000 | 1.000.000.000.000 |
Repare no salto: com 1 milhão de itens, um algoritmo O(n) faz 1 milhão de operações — factível em uma fração de segundo. Um algoritmo O(n²) faria 1 trilhão de operações no mesmo cenário, o que pode significar horas de processamento. A mesma tarefa, resolvida de duas formas diferentes, pode ser a diferença entre "instantâneo" e "inviável".
Código que roda rápido em teste com 20 registros e roda em produção com 2 milhões de registros é uma das causas mais comuns de sistemas que "funcionavam bem" e começam a travar depois de meses em produção. Antes de escrever um laço aninhado sobre uma coleção que pode crescer, pergunte: existe uma forma de fazer isso com uma passada só?
8. Melhor caso, pior caso e caso médio
Um mesmo algoritmo pode ter comportamentos diferentes dependendo dos dados de entrada. Buscar um item numa lista pode encontrar o valor na primeira posição (melhor caso, O(1) nessa execução específica) ou só na última posição, ou nunca (pior caso, O(n)). Quando falamos da complexidade de um algoritmo sem qualificar, normalmente estamos nos referindo ao pior caso — é a garantia mais segura de se basear, porque é o teto do que pode acontecer.