Bonjour,
Je n'ai pas vraiment compris la question 15, même avec le corrigé- Je ne comprends pas le calcul de somme qu'on a fait, par exemple pourquoi il y a un 4 dans la somme pour "algo 1".
Est-ce que que quelqu'un pourrait expliquer?
(Écrit initialement le mardi, 23 octobre 2018, 22:54 ; modifié par Jean-Cédric Chappelier : j'ai mis la bonne année (2015) dans le titre)
Je suis désolé, il s'agit en fait du sujet 1 de 2015 apparemment.
Voici le sujet (son corrigé, plutôt) en question. Je n'ai pas compris le calcul qui est dans la justification de la question 15.
Si l'on veut comparer 2 algorithmes qui ont le même ordre de grandeur de complexité (ce qui est le cas ici), alors il faut utiliser le même « langage » pour les comparer, c.-à-d. décider le jeu d'instructions élémentaires (au final ce serait la table de la machine de Turing qui fait cet algorithme, mais ce n'est pas ce que je vous demande ici). Tant que vous choisissez la même convention pour les deux, ce sera comparable. Pour ma part, j'ai pris celle du cours : 1 instruction pour la comparaison de j à t dans la boucle for, 1 pour l'incrément de j dans la boucle for, 1 pour la comparaison de L[j] à L[k] et 1 pour l'affectation, ce qui fait 4.
Merci! Je ne pensais pas que la boucle for ajoutait aux opérations élémentaires.