Complexidade de algoritmos sem susto: entendendo o Big-O de verdade

A notação Big-O tem uma reputação injusta. Para muita gente ela é um ritual de entrevista técnica — algo que se decora na véspera, se cospe no quadro branco e se esquece assim que o emprego está garantido. Essa visão é uma pena, porque por trás do símbolo assustador mora uma das ideias mais úteis e práticas da computação: uma forma de prever como o seu programa vai se comportar quando a quantidade de dados crescer, sem precisar rodá-lo com um milhão de registros para descobrir.

O ponto que quase ninguém explica direito é que Big-O não é sobre velocidade em segundos. É sobre taxa de crescimento. A pergunta que ele responde não é "quão rápido esse código roda", e sim "o que acontece com o tempo quando eu dobro a entrada?". Essa mudança de foco é o que torna a análise tão poderosa: você consegue comparar dois algoritmos no papel, antes de escrever uma linha, e saber qual vai continuar de pé quando os dados saírem de mil para dez milhões. Este artigo desmonta o Big-O com calma, priorizando a intuição sobre a matemática, para que ele deixe de ser um susto e vire uma ferramenta que você usa sem perceber.

O que o Big-O mede (e o que não mede)#

Imagine que você tem uma função e quer descrever seu custo. Você poderia cronometrá-la, mas o resultado dependeria da máquina, da linguagem, do humor do sistema operacional naquele instante. Big-O abstrai tudo isso e pergunta só uma coisa: à medida que a entrada n cresce, como o número de operações cresce junto?

Ele descreve o crescimento, não o tempo absoluto. Um algoritmo O(n) faz um número de passos proporcional ao tamanho da entrada. Se n dobra, o trabalho dobra. Um algoritmo O(n²) faz um trabalho proporcional ao quadrado: dobrar n quadruplica o esforço. Não importa se cada passo leva um nanossegundo ou um milissegundo — o que o Big-O captura é o formato da curva, e é o formato que decide quem sobrevive à escala.

Ele ignora constantes e termos menores. Um algoritmo que faz 3n + 50 operações é O(n), não O(3n + 50). Isso choca quem está começando: "mas 50 operações a mais importam!". Importam para um n pequeno, mas o Big-O olha para o comportamento quando n tende ao infinito, e lá as constantes desaparecem na frente do termo dominante. n² acaba engolindo qualquer n linear que o acompanhe, então n² + 1000n é simplesmente O(n²). Essa simplificação é intencional: ela isola o que realmente governa a escala.

Ele geralmente descreve o pior caso. Quando dizemos que a busca em uma lista é O(n), estamos pensando no cenário em que o elemento procurado está no fim, ou não existe. O pior caso é o mais usado porque é a garantia que você pode dar: "não importa o quão azarado seja o input, não passa disso". Existem também o caso médio e o melhor caso, úteis em contextos específicos, mas quando alguém cita um Big-O sem qualificar, quase sempre é o pior caso.

As classes que você vai encontrar#

Na prática, quase todo código que você escreve cai em um punhado de classes de complexidade. Conhecê-las de cor, com uma imagem mental para cada uma, resolve a maior parte das análises do dia a dia.

O(1) — tempo constante. O custo não depende do tamanho da entrada. Acessar o terceiro item de um array, ler o valor de uma chave em um dicionário, empilhar um elemento — tudo isso leva o mesmo tempo com dez ou com dez milhões de itens. É a analogia de olhar um número específico de casa numa rua: você vai direto, não percorre a rua inteira. É o melhor cenário possível e o alvo quando a operação é chamada o tempo todo.

O(log n) — tempo logarítmico. A cada passo, você descarta metade do que sobrou. É a busca binária: para achar uma palavra num dicionário físico, você não lê da primeira à última página; abre no meio, decide se sua palavra está antes ou depois, e repete. Um milhão de itens se resolve em cerca de vinte passos; um bilhão, em cerca de trinta. O logaritmo cresce tão devagar que, para efeitos práticos, é quase tão bom quanto constante. Toda vez que um problema é resolvido "dividindo pela metade", o log aparece.

O(n) — tempo linear. Você toca cada elemento uma vez. Somar todos os valores de uma lista, procurar um nome numa lista não ordenada, imprimir cada linha de um arquivo. Dobrou a entrada, dobrou o trabalho — uma relação honesta e previsível. É o custo mínimo inevitável de qualquer operação que precise olhar todos os dados pelo menos uma vez.

O(n log n) — o território dos bons algoritmos de ordenação. É o custo do merge sort, do quicksort no caso típico, e de muitos algoritmos eficientes que precisam organizar dados. Você pode lê-lo como "faço um trabalho linear, um número logarítmico de vezes". É notavelmente mais lento que O(n), mas ainda muito escalável — é o melhor que se consegue para ordenação por comparação, e por isso é o piso prático de tantos problemas.

O(n²) — tempo quadrático. Para cada elemento, você percorre todos os outros. Comparar cada item com cada item, os laços aninhados clássicos, o bubble sort. Com cem elementos são dez mil operações; com dez mil elementos, cem milhões. O quadrático funciona bem em protótipos e entradas pequenas e desmorona silenciosamente quando os dados crescem — é a causa número um de código que "funcionava na minha máquina" e trava em produção.

O(2^n) e O(n!) — o abismo exponencial. Aqui o custo explode de forma que nenhuma máquina acompanha. Calcular Fibonacci pela recursão ingênua, gerar todos os subconjuntos, testar todas as permutações de um caixeiro viajante por força bruta. Adicionar um único elemento pode dobrar o tempo. Um n de 50 já é inviável. Quando você se encontra numa dessas classes, o recado é claro: precisa de uma abordagem completamente diferente, não de um computador mais rápido.

Tempo não é a única conta: complexidade de espaço#

Toda essa conversa foi sobre tempo, mas memória obedece à mesma notação e importa tanto quanto. A complexidade de espaço mede quanta memória extra o algoritmo consome em função da entrada.

Há um trade-off constante entre tempo e espaço. Muitas vezes você acelera um algoritmo gastando memória — guardando resultados já calculados para não recalculá-los. O Fibonacci exponencial vira linear no tempo quando você memoriza os valores intermediários, ao custo de O(n) de espaço. Essa troca é uma das decisões mais recorrentes de engenharia: uma tabela de cache que transforma uma operação O(n) repetida em O(1) está literalmente comprando velocidade com memória.

Espaço demais tem consequências próprias. Um algoritmo que copia a entrada inteira a cada passo pode ser rápido no papel e ainda assim inviável, porque estoura a memória disponível ou porque o custo de alocar e mover tanto dado domina o relógio. Recursão profunda, além disso, consome pilha — e uma recursão O(n) de profundidade pode derrubar o programa com stack overflow muito antes de o tempo virar problema. Analisar só o tempo e ignorar o espaço é ver metade do quadro.

Quando o n é pequeno, a teoria mente#

Aqui vem a parte que os cursos costumam omitir e que separa quem decorou de quem entendeu: o Big-O descreve o comportamento assintótico, quando n é grande. Para n pequeno, ele pode enganar redondamente.

As constantes que ignoramos voltam a mandar. Um algoritmo O(n) com uma constante enorme pode ser mais lento que um O(n²) com constante minúscula, desde que n seja pequeno o bastante. É exatamente por isso que implementações reais de ordenação trocam para o simples insertion sort — teoricamente O(n²) — quando o sub-array a ordenar tem poucos elementos: nesse regime, o algoritmo "pior" ganha do "melhor" porque não paga o overhead de recursão e alocação.

O hardware moderno premia a localidade. A teoria trata todo acesso à memória como igual, mas o processador real é muito mais rápido lendo dados contíguos, que já estão no cache, do que perseguindo ponteiros espalhados pela RAM. Um array percorrido em sequência pode humilhar uma estrutura teoricamente superior que salta de um lugar para outro, porque o Big-O não vê o cache. A lição prática: use o Big-O para escolher a classe certa, mas meça antes de otimizar constantes, porque nesse nível a intuição teórica falha.

Análise amortizada: o custo diluído#

Algumas operações são baratas quase sempre e caras de vez em quando, e olhar só para o pior caso pontual dá uma impressão pessimista e errada. A análise amortizada calcula o custo médio por operação ao longo de muitas operações.

O array que dobra é o exemplo perfeito. Adicionar um elemento ao fim de um array dinâmico costuma ser O(1). Mas quando ele enche, o sistema aloca um array maior — normalmente o dobro — e copia tudo, um passo O(n). Parece que inserir é O(n) no pior caso, e é. Só que esse passo caro acontece raramente, e a duplicação garante que ele fica cada vez mais espaçado. Somando o custo de milhões de inserções e dividindo pelo número delas, cada uma custa, em média, O(1). Esse é o custo amortizado, e é por ele que confiamos em listas dinâmicas para adicionar itens sem medo, apesar da cópia ocasional cara.

Lendo a complexidade de um código#

A boa notícia é que estimar o Big-O de um trecho raramente exige matemática pesada. Com alguns hábitos de leitura, você acerta a classe na maioria dos casos só olhando a estrutura.

Laços em sequência somam; laços aninhados multiplicam. Dois laços um depois do outro, cada um sobre n, dão O(n) + O(n) = O(n). Um laço dentro do outro, cada um sobre n, dão O(n × n) = O(n²). A regra é quase literal: conte quantos níveis de laço aninhado percorrem a entrada e você tem o expoente.

```python # O(n): um passe pela lista for item in lista: processar(item)

# O(n^2): para cada item, percorro a lista de novo for a in lista: for b in lista: comparar(a, b) ```

Dividir a entrada pela metade a cada passo é o sinal do logaritmo. Se, a cada iteração, o espaço que resta cai pela metade, você está em O(log n). Combine isso com um laço externo linear e chega em O(n log n) — a assinatura de muitos algoritmos de ordenação e de busca eficientes.

Na recursão, some o custo de cada chamada. Uma função que se chama duas vezes por nível, dobrando o número de chamadas a cada passo, tende ao exponencial. Uma que se chama uma vez sobre metade da entrada tende ao logarítmico. Desenhar a árvore de chamadas — quantos ramos, com que profundidade — revela o custo total sem fórmula fechada. Cuidado com o gasto escondido dentro do laço: um for que a cada volta chama uma busca O(n) numa lista é, no fim, O(n²), mesmo que só apareça um laço explícito no código.

Fechando#

O Big-O deixa de assustar quando você para de tratá-lo como fórmula e passa a lê-lo como intuição: é a resposta para "o que acontece quando os dados crescem?". Guarde a hierarquia — constante, logarítmico, linear, n log n, quadrático, exponencial — como um mapa de sobrevivência à escala, e reconheça-a nos laços e nas recursões que você escreve todo dia. Lembre que a teoria manda quando n é grande, e que para dados pequenos as constantes e o hardware têm a palavra final, então meça antes de otimizar demais. Você não precisa provar teoremas; precisa saber, antes de apertar o botão, se o seu código vai continuar de pé quando o sucesso multiplicar seus usuários por mil.