Bonjour,
Je suis étudiant en L2 informatique et j'ai des cours sur la complexité des algorithmes, cependant même avec l'aide de ces cours j'ai du mal avec un exercice d'une de mes annales, voici l'exercice :
"Soit M un nombre aléatoire dont l’écriture propre en base 2 comporte n chiffres. Quelle est la complexité temporelle moyenne de l’algorithme suivant ?"
x := M ; i := 0 ;
Tant que (x mod 2 = 0) faire
x := x/2 ; i := i + 1 ;
Fin tant que
Je sais que la réponse à cette question est que la complexité moyenne est en thêta(1). Or je ne comprends pas pourquoi elle n'est pas en thêta(log n). Peut-être que je n'ai pas bien compris l'algorithme, mais dans ma tête je prends un exemple : 16
16 comporte 5 chiffres en base 2 (10000), on va rentrer dans la boucle 4 fois avant d'avoir fini : 16/2, 8/2, 4/2, 2/2. Or 2^4 = 16, même raisonnement pour 32, 64, 128, etc.. Je ne dois pas avoir le bon raisonnement puisque de ce fait j'aurais dis que la complexité était en thêta(log n), quelqu'un pourrait-il m'éclairer sur cet exercice ?
Merci d'avance pour votre aide !
