Contar Antes de Programar: Complexidade, Restrições e Medição

Nesta série, a curiosa leitora vai estudar os algoritmos e as estruturas de dados que decidem as competições de programação e, com a mesma frequência, decidem o desempenho de sistemas reais. O ponto de vista será sempre o de quem precisa entregar um programa que responde certo e responde a tempo. Cada técnica aparecerá junto com o problema que a obriga a existir, com a matemática que a justifica, com um exemplo pequeno rastreado passo a passo e com a implementação em C++23. Pelo menos, eu vou tentar.

O combinado é o mesmo das séries Transformers e Redes para Engenharia de Software: os exemplos de código são em C++23, completos quando precisam ser completos, e a leitora refaz na linguagem que preferir. Os programas integrais, em versões clássicas e modernas, ficam no repositório competitive-code, organizado por capítulos. Os artigos mostram os fragmentos necessários para entender cada ideia e indicam o arquivo completo. Os laboratórios rodam no navegador, sem instalar nada.

Antes do primeiro algoritmo, precisamos de uma régua. Algoritmos são comparados pelo trabalho que realizam, e trabalho só pode ser comparado depois de contado. Este artigo ensina a contar o trabalho de laços e de funções recursivas, a traduzir essa contagem na notação que a área usa, a ler os limites de entrada de um problema como uma lista de algoritmos que ainda estão vivos e a medir o tempo de um programa de um jeito que resista à desconfiança. Parece muito para um primeiro artigo. É o mínimo para que os próximos façam sentido.

1. O veredito que a correção não evita

Uma competição de programação apresenta um problema, um conjunto de restrições sobre a entrada e um limite de tempo, tipicamente um ou dois segundos por arquivo de teste. A participante envia um programa. Um juiz, que é apenas outro programa, executa a solução em dezenas de entradas secretas, compara as saídas com as respostas esperadas e mede o tempo de cada execução. O veredito só é aceito quando todas as saídas estão corretas e todas as execuções terminam dentro do limite.

Vamos considerar um programa que compara todos os pares de elementos de uma entrada com $n={10}^6$ elementos. Ele pode estar logicamente perfeito. Pode reproduzir os exemplos do enunciado, compilar na primeira tentativa, um evento raro e levemente suspeito, e implementar uma ideia bonita. Nada disso muda o veredito, porque o número de pares ordenados será dado por

$$n\cdot n={10}^6\cdot {10}^6={10}^{12}.$$

Um trilhão de comparações. Um processador moderno executa algo entre ${10}^8$ e ${10}^9$ operações simples por segundo em código que percorre memória, número que vamos justificar na Seção 5. No melhor cenário, o programa precisaria de ${10}^{12}/{10}^9=1000$ segundos, cerca de dezesseis minutos, para responder a uma pergunta que o juiz espera em um segundo.

Correto não basta.

A programação de alto desempenho conhece a mesma verdade com outros nomes. O juiz pode ser uma usuária impaciente, um cliente com um contrato de latência, um sensor que envia dados mais depressa do que o programa consegue processar ou uma simulação que precisa terminar antes da reunião de amanhã. Sempre existe um juiz. A diferença entre uma competição e um sistema real está apenas na clareza com que o limite foi escrito.