Leia as Restrições e Escolha a Complexidade

Todo problema lista limites para n e para os valores. Essas restrições indicam discretamente qual complexidade o elaborador espera. 🔍

Antes de projetar qualquer coisa, encontre o maior n nas restrições. O tamanho de n determina se você precisa de uma solução quadrática, linear ou logarítmica.

Quando n é no máximo 20, até uma força bruta exponencial cabe no limite. Limites pequenos são um convite para tentar todas as combinações sem medo.

Se n chegar a algumas centenas, uma solução O(n^3) ainda será aceita. Laços triplos ou uma DP básica sobre pares são opções válidas aqui.

Para n = 5000, procure uma solução O(n^2). Laços aninhados sobre o vetor custam cerca de 2,5 vezes 10^7 etapas, o que ainda cabe no orçamento.

Quando n chega a 10^5 ou 10^6, você precisa de O(n log n) ou O(n). Ordenação, somas prefixadas e dois ponteiros tornam-se suas ferramentas principais.

Se n for um bilhão, nenhum laço que percorra n elementos sobreviverá. Você precisa de O(log n) ou O(1), usando matemática ou busca binária sobre a resposta.

As restrições dos valores também importam. Números grandes alertam para a possibilidade de estouro em outras linguagens e podem indicar o uso de aritmética modular.

Problemas com vários testes costumam limitar a soma de n, e não cada n individualmente. Leia isso com atenção, pois muda o tamanho que seus laços podem ter com segurança.

Escolha a complexidade desejada a partir de n e depois selecione um algoritmo que a alcance. Deixar n orientar o projeto é melhor do que adivinhar e reescrever tudo depois.

Guarde esta tabela na memória. A relação entre restrições e complexidade transforma uma rápida olhada nos limites em um plano imediato durante as competições.

Deixe n indicar a complexidade correta.

Agora você interpreta as restrições como uma meta: n pequeno permite força bruta, 10^5 exige n log n, e 10^9 exige log ou matemática. Deixe n escolher a abordagem. 🗺️