Temps limite contrainte de performance langage

Bonsoir,

Je suis en train de chercher l'exercice 5 des qualifications. J'ai trouvé quelque chose, malheureusement trop lent et ne passe pas les gros tests (à partir du 16ème).

J'avais une première fois codé mon algorithme en Python. Le système coupe alors le test au bout de 15 secondes, le jugeant trop long. Je pensais au début que mon code s'exécutait en exactement 15 secondes, mais en voyant que même en divisant le temps de calcul par plus de 10 (grâce à des optimisations), je reste à 15 secondes, j'ai alors compris qu'il s'agissait d'un seuil.

Cherchant à vraiment optimiser, j'ai changé de langage et suis passé en Java. Le résultat est plutôt satisfaisant : pour le même algorithme, je mets 4 à 5 fois moins de temps qu'en Python. J'ai alors soumis mon nouveau programme en Java (voir si je pouvais enfin passer le test 16), mais malheureusement il se coupe au bout de 4,29 secondes. Je me demandais alors : mon programme s'est-il vraiment arrêté en 4,29 secondes ou a-t-il été stoppé avant la fin de son exécution ?

Et surtout, pourquoi ces temps ne correspondent pas à celui de l'énoncé qui est de 1000 millisecondes ?

Bon après, je sais bien que mon algorithme ne pourra jamais faire tourner les tests avec L = 2 000 000 tant qu'il gardera une complexité en O(n²). C'est vraiment possible de faire moins ?

Salut !

Comme tu le sais chaque langage est plus ou moins rapide, et vu qu'on souhaite évaluer l'efficacité de ton algorithme plutôt que celle du langage que tu utilises, nous employons différents facteurs de temps en fonction des langages. Ceci explique les différences de temps limite que tu observes et pourquoi ton programme codé en Java passe autant de tests que celui codé en Python (puisque comme tu le dis, l'algorithme est le même). Le but est de rétablir un équilibre entre les langages pour ne pas désavantager ceux qui utilisent des langages de nature plus lente.

Pour ce qui est de la contrainte de 1000ms donnée par l'énoncé, elle te permet d'estimer le nombre d'opérations que tu es capable de faire indépendamment du langage choisi (à part si tu utilises un langage très rapide comme le C ou le C++ où le facteur temps est proche/égal à 1).

Sinon, il existe bien une solution efficace pour résoudre ce problème, mais ce n'est pas pour rien que cet exercice est de niveau 5 :p

Bonne chance !