complexity-cuts — Reduzir Big-O em Código Existente

lemmaly impede complexidade ruim antes que o código seja escrito. complexity-cuts corrige isso depois do fato: o código já existe, funciona, mas sua complexidade de tempo ou espaço é pior do que o necessário.

Violar a letra destas regras é violar o espírito da habilidade. Adaptar "só um pouquinho" é como um refatoramento mais rápido-mas-errado é entregue.

Quando Usar Esta Habilidade

Use complexity-cuts ao refatorar código existente que tenha Big-O ruim:

• Loops aninhados, O(n²) ou piores varreduras, trabalho repetido, alocações redundantes, memória estourada.
• Sintomas declarados: "isso é lento em entradas grandes", "tempo esgotado", "OOM" (Out Of Memory), "muita memória", "reduzir complexidade", "otimizar este algoritmo".
• Padrões de consulta N+1 em ORMs (Prisma, Drizzle, SQLAlchemy, Django, ActiveRecord).
• await dentro de for sobre itens independentes causando latência serial.

Para prevenir complexidade ruim antes que o código seja escrito, use lemmaly. Para otimizações de nível matemático (Bloom, HLL, FFT, projeção JL), escale para mathguard.

A Lei de Ferro

NO TRANSFORMATION WITHOUT EXISTING TESTS GREEN BEFORE AND AFTER

Se o código não tem testes, escreva um teste de caracterização primeiro (entrada de referência → saída atual). Depois, transforme. E verifique se o teste ainda passa. Se você pular isso, a otimização pode quebrar silenciosamente os chamadores — e mais rápido-mas-errado é pior do que lento-e-certo.

Regras Inegociáveis

1. Declare o Big-O atual e o alvo antes de tocar no código. Em uma linha:

   • Atual: time = O(?), space = O(?)
   • Alvo: time = O(?), space = O(?)
   • Dimensão de entrada dominante (n = o quê, quão grande na prática)

   Se você não consegue declarar o Big-O atual, você ainda não entende o código. Leia mais.

2. Identifique o gargalo, não adivinhe. Aponte para a(s) linha(s) exata(s) responsável(is) pelo termo dominante. Loop aninhado? Varredura linear repetida? Recálculo? Alocação dentro de um loop quente? A correção está lá, não em outro lugar.

3. Uma transformação de cada vez, com um loop de verificar-reverter-parar. O loop é:

   1. Aplique exatamente uma transformação do playbook.
   2. Execute a suíte de testes existente (ou o teste de caracterização que você escreveu de acordo com a Lei de Ferro).
   3. Se algum teste quebrar: reverta imediatamente. Não corrija o teste. Não corrija em torno da falha. Reverter.
   4. Conte as reversões nesta peça de código. Se 3 reversões seguidas, PARE de otimizar. O gargalo está errado, a transformação está errada, ou o código tem invariantes que você não modelou. Escalar para invariant-guard e escreva o contrato ausente — não tente uma quarta transformação.
   5. Somente após uma transformação passar com sucesso: escolha a próxima.

   Mudanças empilhadas escondem regressões. Testes corrigidos escondem regressões mais alto.

4. Preserve as semânticas exatamente. Complexidade menor não deve alterar saídas, garantias de ordenação, estabilidade ou comportamento de erro. Se a otimização exigir uma mudança semântica (por exemplo, saída não ordenada), chame-a explicitamente e confirme se é aceitável.

5. Sem números inventados. Nunca escreva "10x mais rápido" ou "economiza 200MB" sem medir. Escreva <measured: TBD> e siga em frente, ou meça de fato com uma entrada representativa.

6. Sempre relate a razão de aceleração medida após uma transformação ser concluída. Uma vez que o novo código esteja verde, execute um benchmark representativo (mesma entrada, mesma máquina, cache aquecido) e relate before → after mais a razão como N× faster (ou N× less memory). Uma linha, anexada ao diff:

   p50:  186 ms → 1.1 ms   (169× faster, n=20,000, 200 samples)
   

   Se você não puder medir (por exemplo, a vantagem é puramente assintótica em entradas que você não tem), diga isso explicitamente: asymptotic only, no measurement — O(n²) → O(n). Nunca pule silenciosamente esta etapa.

O playbook de transformação

A grande maioria das vitórias de Big-O no mundo real vêm de um pequeno conjunto de movimentos. Tente-os nesta ordem:

Reduções de complexidade de tempo

…