Salut,

Je débute dans l'algo et je suis actuellement un tuto' de developpez (initiation à l'algorithmique), et il y a un exercice qui m'intrigue :

fonction decalage (a:entier) : entier
Si a=0 Alors :
retourner 0
FinSi
TantQue a est pair faire :
a <- a/2
FinTantQue
retourner a

Dans le pire des cas, la complexité est constante pour tout entier impair, et est égale à log(a) pour toute puissance de 2.

Mais pour la complexité en temps moyenne, on observe sur les entiers de taille 3 (représentés en binaire):

a nbre d'instructions
001 0
010 1
011 0
100 2
101 0
110 1
111 0

Ainsi, le nombre d'executions de a/2 sur des entiers de taille 3 égale à 4/7.

Exercice :

Prouver que la complexité en moyenne dedecalage est constante.

---------------------------

Seulement voilà, en faisant la même chose pour des entiers de taille 2 et 4 je trouve respectivement 1/3 et 11/15. Et (1/3)=/=(4/7)=/=(11/15)... Quelqu'un pour éclaircir ce petit problème à un débutant ? :D Peut-être que la différence entre 1/3 et 4/7 et 11/15 est petite donc n'est pas prise en compte, mais peut-être que je me trompe et que j'ai même pas saisi la notion de complexité... Merci d'avance en tout cas.

Bonsoir,

"a nbre d'instructions
001 0 "
0 ? vraiment ?

Le test à 0 coûte aussi cher que la division par 2 sur une machine normale. Est-ce que tu comptes juste les sauts (jump) dus aux branchements du if ?

Pour le reste, l'énoncé m'a l'air un peu flou. On a quoi en entrée de l'algorithme ? Un entier n quelconque (possiblement très très grand) ? Si oui, je ne sais pas définir la complexité moyenne proprement (= je sais prouver qu'on ne peut pas tirer au hasard un entier dans N avec équiprobabilité, ce qui est logique quand on y réfléchit).

Bonsoir et merci pour ta réponse,

<<"a nbre d'instructions
001 0 "
0 ? vraiment ?

Le test à 0 coûte aussi cher que la division par 2 sur une machine normale. Est-ce que tu comptes juste les sauts (jump) dus aux branchements du if ? >>

Bah j'ai simplement recopié ce qu'il y avait dans le pdf. Selon lui vu que 1 est un nombre impair, aucune instruction ne sera executée et la fonction renverra directement la valeur de 'a'. (a =/= 0, et a n'est pas pair, donc toutes les instructions seront sautées. Enfin c'est ce que j'ai compris.)

Pour l'énoncé, oui on a entrée un entier N quelconque.

Chris_27 Au final ce qui compte c'est le nombre de 0 de poids faible dans la représentation binaire du nombre N en question

Et si on suppose que le nombre est tiré au hasard, on sait qu'on a 1/2 que le ième bit soit à 0.

En admettant ça, on peut évaluer la complexité "en moyenne" comme :
sum_i=1^+infini lg(i)/2^i

Ce qui se traduit par une partition de l'espace des solutions en multipliant la probabilité que l'événement arrive par la complexité en question

La série associée converge bien (majorée par sum 1/n^2) … Donc on peut dire que l'opération se déroule en temps constant en moyenne pour un entier arbitrairement grand

Mhhh. Mouais, après tout +1 est bien constant en amorti, au final ça ne me choque pas plus que ça

Au pire si on fait une analyse amortie on arrive aux mêmes conclusions, le bit de poids 0 a une chance sur 2 de se faire manger, celui de poids 1 a une chance sur 4, etc … le raisonnement est analogue à l'incrémentation

Erratum : c'est i / 2^i en fait, après réflexion

Mais ça converge quand même

Et une analyse amortie n'aurait aucun sens ici puisqu'en fait on ne réitère pas l'opération plusieurs fois

My bad.