Retour à la leçonMission
Mission : sauver l'algorithme qui dépasse le temps limite
Diagnostiquer pourquoi une solution O(n²) échoue à l'échelle, puis la réécrire avec une complexité inférieure.
Contexte
Une candidate a rendu une fonction qui, pour un tableau de n entiers, cherche s'il existe deux indices différents dont les valeurs sont égales (un doublon). Sa version utilise deux boucles imbriquées et passe tous les petits exemples de l'énoncé, mais l'évaluateur automatique la rejette pour dépassement de temps sur un tableau de 50 000 éléments.
Tu dois comprendre pourquoi cette solution s'effondre à grande échelle, puis produire une version qui reste rapide même avec des millions d'éléments.