Complexidade de Algoritmos

Um algoritmo que ordena 10 números em 1 milissegundo pode levar 16 minutos para ordenar 1 milhão de números — se tiver o algoritmo errado. Outro algoritmo pode fazer o mesmo em menos de 1 segundo. Essa diferença não vem do hardware, mas da matemática por trás de como o tempo de execução cresce com o tamanho da entrada.

Para entradas pequenas, qualquer algoritmo parece rápido. O computador moderno é tão veloz que as diferenças são imperceptíveis. O problema aparece em escala: bases de dados com bilhões de registros, imagens com milhões de pixels, redes sociais com centenas de milhões de usuários. Nesses contextos, escolher o algoritmo errado pode tornar um produto inutilizável.

A análise de complexidade dá uma linguagem matemática para comparar algoritmos independentemente do hardware. Em vez de medir segundos (que variam com o processador), medimos como o número de operações cresce em relação ao tamanho n da entrada.

Big-O é uma notação matemática que descreve o comportamento de crescimento de uma função. O(f(n)) significa 'o tempo de execução cresce proporcionalmente a f(n) no pior caso, ignorando constantes e termos menores'.

Por que ignorar constantes? Porque o que importa é a tendência de crescimento. Um algoritmo que faz 100n operações e outro que faz 5n operações têm a mesma classe de complexidade O(n). Para n = 1 milhão, ambos fazem entre 5 e 100 milhões de operações — a diferença é um fator constante, não uma diferença de escala.

Big-O descreve o pior caso. A busca linear em uma lista de n elementos pode encontrar o elemento na primeira posição (1 operação) ou na última (n operações). Big-O se preocupa com o pior caso: O(n).

O(1) — constante: o tempo de execução não depende do tamanho da entrada. Acessar um elemento de um array pelo índice é O(1): notas[42] sempre leva o mesmo tempo, seja o array de 10 ou de 10 milhões de elementos. É a melhor complexidade possível.

O(n) — linear: o tempo cresce proporcionalmente ao tamanho da entrada. A busca linear (percorrer todos os elementos até encontrar o buscado) é O(n). Se n dobra, o tempo máximo dobra. Para n = 1 milhão, até 1 milhão de comparações.

O(n²) — quadrático: comum em algoritmos com dois laços aninhados. O Bubble Sort é O(n²): para cada um dos n elementos, faz até n comparações. Se n dobra, o tempo quadruplica. Para n = 10.000, até 100 milhões de operações — começa a ficar lento.

O(log n) — logarítmica: o tempo cresce muito devagar. A busca binária em uma lista ordenada é O(log n): a cada passo, elimina metade dos elementos restantes. Para n = 1 bilhão, são necessárias apenas 30 comparações (log₂ de 1.000.000.000 ≈ 30). É praticamente constante na prática.

A busca linear verifica cada elemento do início ao fim. É O(n) e funciona em qualquer lista, ordenada ou não. A busca binária exige que a lista esteja ordenada, mas é muito mais eficiente: O(log n).

Como funciona a busca binária? Pegue o elemento do meio da lista. Se for o buscado, acabou. Se for maior que o buscado, descarte a metade direita e repita na metade esquerda. Se for menor, descarte a metade esquerda e repita na metade direita. A cada passo, o espaço de busca é cortado pela metade.

Comparação prática: buscar um nome em uma lista de 1 milhão de pessoas ordenada alfabeticamente. Busca linear: até 1.000.000 comparações. Busca binária: até 20 comparações. Essa diferença dramática explica por que bancos de dados ordenam seus índices e por que a ordenação é tão importante.

No dia a dia do desenvolvimento, o conhecimento de complexidade guia escolhas de estrutura de dados. Hashtables (dicionários) oferecem inserção e busca O(1) em média — é por isso que são onipresentes. Árvores binárias balanceadas oferecem O(log n) para busca, inserção e remoção — usadas em bancos de dados e sistemas de arquivos.

Um erro comum é chamar uma função O(n) dentro de um laço O(n), criando inadvertidamente um algoritmo O(n²). Isso pode passar despercebido em testes com poucos dados e só aparecer em produção, com dados reais.

Otimização prematura é um problema real: não tente otimizar antes de identificar gargalos. Mas conhecer a complexidade dos algoritmos que você usa é diferente de otimizar prematuramente — é fazer escolhas informadas desde o início do design.