Algoritmos Que Terminam No Prazo: Uma Verificação de Complexidade

Você escreve uma função, a executa nos dados de teste e funciona bem. Depois ela chega aos dados de produção — 500 mil linhas em vez de 500 — e a requisição trava. Isso acontece constantemente, e quase sempre é um problema de complexidade escondido atrás de código que parecia razoável em pequena escala.

Por que seu laptop mentiu para você

Um algoritmo O(n²) rodando em 100 itens faz 10 mil operações. Isso é instantâneo em qualquer máquina. Execute o mesmo algoritmo em 100 mil itens e você chega a 10 bilhões de operações — minutos ou horas em vez de milissegundos. O salto de n para n² não parece perigoso até n ficar grande, e é exatamente por isso que passa despercebido na revisão de código e nos testes locais.

Um exemplo clássico: verificar duplicatas com um loop aninhado.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Isso é O(n²). Troque por um conjunto:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Agora é O(n). Buscas em set são O(1) em média, então a função toda escala linearmente em vez de quadraticamente. Em 10 mil itens essa é a diferença entre aproximadamente 100 milhões de comparações e 10 mil.

Meça antes de otimizar

Não adivinhe. Use timeit para microbenchmarks:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

Para funções maiores, perfil com cProfile:

python -m cProfile -s cumulative myscript.py

Olhe a coluna cumtime. Se uma função consome 90% do tempo de execução, esse é seu alvo. Otimizar código que não é o gargalo desperdiça seu tempo e adiciona complexidade sem ganho.

Padrões comuns que ficam lentos sorrateiramente

Verificações repetidas de associação em listas. if x in my_list é O(n) para uma lista mas O(1) em média para um set ou dict. Se você está verificando associação dentro de um loop, aquele check O(n) dentro de um loop O(n) te dá O(n²) geral. Troque a lista por um set e você volta a O(n).

Concatenação de strings em um loop. Em Python, result += chunk dentro de um loop sobre strings é O(n²) no pior caso porque strings são imutáveis e cada concatenação copia tudo. Use ''.join(chunks) — constrói a string uma vez.

Ordenação quando você não precisa. sorted() é O(n log n). Se você está chamando ela dentro de um loop só para encontrar o máximo ou mínimo a cada iteração, use max()/min() (O(n)) ou melhor, um heap (heapq) se você precisa do extremo corrente repetidamente. heapq.nlargest(k, data) é O(n log k), muito mais barato que ordenar a lista inteira quando k é pequeno.

Funções recursivas sem memoização. Fibonacci recursivo ingênuo é O(2ⁿ) porque recomputa os mesmos subproblemas várias vezes. Adicione functools.lru_cache e cai para O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Lendo Big O direto do código, rápido

Conte loops aninhados sobre a mesma entrada — esse é geralmente seu expoente. Um loop único é O(n). Um loop dentro de um loop é O(n²) a menos que o intervalo do loop interno encolha (como na forma otimizada de bubble sort, ainda O(n²) pior caso mas menos comparações). Chamadas recursivas que dividem o problema na metade, como busca binária ou merge sort, apontam para O(log n) ou O(n log n). Chamadas recursivas que se ramificam em múltiplas chamadas por nível, como Fibonacci ingênuo, apontam para tempo exponencial — um sinal forte de que você precisa de memoização ou reescrita iterativa.

Um bom hábito: antes de escrever loops aninhados ou recursão sobre dados de usuários, pergunte qual poderia ser n realisticamente em produção, não em seu arquivo de teste. Se n pode chegar a centenas de milhares, uma solução O(n²) precisa de uma segunda olhada antes de fazer deploy.

Para mais sobre análise de complexidade, algoritmos de ordenação e ferramentas de profiling, confira os segmentos de Python e Computer Science em Korra Studio.