Lire les contraintes et choisir la complexité

Chaque problème indique des limites pour n et pour les valeurs. Ces contraintes vous indiquent discrètement la complexité attendue par l'auteur de l'énoncé. 🔍

Avant de concevoir quoi que ce soit, trouvez la plus grande valeur de n dans les contraintes. La taille de n détermine si une complexité quadratique, linéaire ou logarithmique est nécessaire.

Lorsque n vaut au plus 20, même une recherche exhaustive exponentielle tient dans le budget. De petites limites vous invitent à essayer toutes les combinaisons sans crainte.

Si n atteint quelques centaines, une solution en O(n^3) passe encore. Les triples boucles ou une DP élémentaire sur des paires sont tout à fait envisageables ici.

Pour n proche de 5000, visez O(n^2). Des boucles imbriquées sur le tableau coûtent environ 2,5 fois 10^7 étapes, ce qui respecte encore le budget.

Lorsque n atteint 10^5 ou 10^6, il vous faut O(n log n) ou O(n). Le tri, les sommes préfixes et les deux pointeurs deviennent vos outils de prédilection.

Si n vaut un milliard, aucune boucle parcourant n éléments ne tient. Vous devez être en O(log n) ou O(1), en utilisant les mathématiques ou une recherche binaire sur la réponse.

Les contraintes sur les valeurs comptent également. De grands nombres signalent un risque de dépassement de capacité dans d'autres langages et peuvent suggérer une arithmétique modulaire.

Les problèmes comportant plusieurs épreuves limitent souvent la somme de n, et non chaque valeur de n. Lisez attentivement cette information, car elle change la taille maximale que vos boucles peuvent gérer sans risque.

Choisissez la complexité cible à partir de n, puis sélectionnez un algorithme qui l'atteint. Laissez n guider la conception : c'est plus efficace que de deviner puis de réécrire plus tard.

Gardez ce tableau en tête. La correspondance contraintes-complexité transforme un simple coup d'œil aux limites en plan immédiat pendant les concours.

Laissez n vous orienter vers la bonne complexité.

Vous savez maintenant lire les contraintes comme une cible : un petit n autorise la force brute, 10^5 nécessite n log n, et 10^9 exige une complexité logarithmique ou des mathématiques. Laissez n choisir l'approche. 🗺️