Problèmes d’implémentation
Lorsqu’on aborde les algorithmes et les structures de données, on a parfois une vision faussée selon laquelle ils seraient très compliqués. Pourtant, la plupart du temps, ils sont simples et intuitifs. Il suffit de s’exercer et de pratiquer pour acquérir l’intuition nécessaire au bon fonctionnement de ces algorithmes.
En travaillant sur des exercices concrets, on remarque rapidement que certains groupes de problèmes partagent des caractéristiques communes. Grâce à ces points communs, il est possible d’appliquer une même technique à l’ensemble de ces problèmes.
L’un de ces groupes est celui des problèmes d’implémentation. Dans ce type de problèmes, les étapes permettant d’aboutir à la solution sont généralement décrites dans l’énoncé. Le rôle de l’ingénieur logiciel est alors de mettre en œuvre ces étapes de manière optimale pour obtenir le résultat souhaité. Attention toutefois : même si les étapes sont fournies, il n’est pas toujours évident de les implémenter immédiatement.
Challenge - Trouver le nombre manquant
Étant donnés tous les nombres de 1 à
n sauf un, il faut retrouver le nombre manquant.Input
La première ligne de l’entrée contient un entier
n (2 ≤ n ≤ 100 000).La deuxième ligne de l’entrée contient
n-1 entiers séparés par des espaces (1 ≤ ≤ n).Output
Le programme doit afficher le nombre manquant.
Exemples
Entrée | Sortie |
4
3 4 1 | 2 |
3
2 1 | 3 |
Tutoriel sur la complexité et la notation Big
Même si le problème décrit ci-dessus peut sembler facile, une approche naïve ne sera pas assez rapide pour réussir tous les tests.
Une approche naïve pourrait consister à lire tous les éléments d’entrée dans une liste puis à parcourir les nombres de 1 à
n pour vérifier si chacun d’eux est présent dans cette liste. S’il ne l’est pas, on affiche ce nombre :n = int(input())
a = [int(ai) for ai in input().split()]
for i in range(1, n + 1): # n opérations
if i not in a: # n opérations (passe en revue tous les éléments)
print(i) # Nous avons trouvé la solution !Cet algorithme est particulièrement lent. Il parcourt tous les nombres de
1 à n et, pour chacun, vérifie s’il est dans la liste. Rechercher un élément dans une liste est une opération linéaire, ce qui signifie que le programme parcourt tous les éléments de a pour déterminer si i s’y trouve ou non. Pour faire ce test, il faut donc environ n opérations. Au total, on effectue donc ~ opérations (la boucle externe effectue n itérations et chaque vérification prend n opérations dans le pire des cas).💻
Nos ordinateurs peuvent exécuter ~10-100 millions d’opérations par seconde. Donc, si la limite de temps pour un problème est d’une seconde (ce qui est fréquent dans les concours d’algorithmique), nous devrions viser au maximum 100 millions d’opérations en tout.
Dans le problème décrit, la valeur de
n peut aller jusqu’à 100 000. Cela signifie que l’algorithme effectuerait opérations, soit dix milliards. Sur un ordinateur standard, cela prendrait environ 100 secondes, alors que la limite de temps fixée pour le problème est d’une seconde. Nous devons donc trouver une solution plus efficace.Notation Big
La notation Big O est un outil mathématique permettant de décrire la frontière supérieure du taux de croissance de la complexité en temps d’un algorithme en fonction de la taille de l’entrée. Elle donne une estimation du nombre d’opérations qu’un algorithme exécute par rapport à la taille de son entrée.
Pour ce problème, nous avons estimé qu’il effectuerait environ
~ opérations. On dira donc que sa complexité est de l’ordre de .Nous approfondirons ce concept plus tard dans le cours, en donnant plus d’intuition et de formalité.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB