Bonjour Zacharie,
Le problème que tu rencontre vient très probablement d'un problème de complexité algorithmique. J'ai du mal à trouver des bonnes ressources, même l'article wikipédia n'a pas l'air terrible.
En gros l'idée est que dans le type de problèmes proposés à Prologin, on va te donner une très grosse entrée (typiquement, un mot d'un million de lettres dans l'exo 5), ces entrées sont si grande que dans l'étude de la rapidité de ton programme la façon dont tu implémentes ta solution a moins de poids que l'approche que tu as pour résoudre le problème.
Une mesure plutôt pertinente est de regarder la taille de l'entrée (typiquement dans l'exo 5 on prendrait en compte la taille des deux mots, $n$ et $m$) et d'estimer le nombre d'opérations qu'exécute ton programme, vraiment grossièrement. Ce qui compte, c'est seulement la façon dont évolue ce nombre d'opérations, typiquement si pour une entrée de taille $n$ c'est proportionnel à $n^2$, multiplier par 100 la taille de l'entrée va multiplier par 10 000 le temps d’exécution de ton programme ; si c'est proportionnel à $n^3$ ça multiplie ce temps par 1 000 000 !
L'exemple de base est le tri d'une liste:
- le tri par sélection consiste à chercher dans la liste son plus petit élément, puis le deuxième plus petit, puis le troisième, etc ... Ce tri demande un nombre d'opérations proportionnel à $n^2$ pour trier une liste de taille $n$ (il faut parcourir toute la liste pour récupérer le $i^\text{e}$ élément le plus petit. Avec un tri de ce type, si tu veux trier une liste d'un million d'éléments, il faut faire environs 1 000 000² = 1 000 000 000 000 opérations.
- il existe des tris plus intelligents par exemple le tri par fusion qui demandent un nombre d'opérations proportionnel à $n \log n$, sur un tel algorithme, trier un million de nombres demande de l'ordre de 10 000 000 d'opérations.
Je ne sait pas où tu en est dans tes études, mais j'espère que mon explication t'as aidé. Elle est un peu vague parce que ce concept est généralement défini en se basant sur des notions mathématiques un peu avancées. Si tu connais les concepts d'analyse asymptotique je recommande plus cette page qui est plus directe.
Je pense que ce post peut en éclairer d'autres, et je pense essayer de faire un article plus complet sur la notion de complexité, les ressources manquent d'une explication à ce sujet.
Enfin, je précise que c'est normal si cette notion te parait obscure et difficile, et qu'il n'est pas nécessaire de savoir la manipuler pour être qualifié au concours Prologin. L'exercice 5 est là pour donner un défis aux candidats les plus têtus, et les solutions se basent souvent sur des algorithmes connus comme ceux présents dans les ressources.
Bon courage, et n'hésites pas à demander plus de précision !
Prologin
2024
