Complexité [Résolu/Fermé]

Signaler
Messages postés
35
Date d'inscription
lundi 10 mars 2008
Statut
Membre
Dernière intervention
14 septembre 2009
-
Messages postés
35
Date d'inscription
lundi 10 mars 2008
Statut
Membre
Dernière intervention
14 septembre 2009
-
Bonjour,
salut j'ai un exercice de complexité je veux savoir si ma réponse est juste ou non
voila l'algorithme:

function test(n:integer):integer;
var s:integer
begin
s:=0;
while(n>=1)do
begin
if(n mod 2=0) then n:=n div 2 else n:=n-1;
s:=s+1;
end
test:=s;
end;


la complexité est log(n) [ car on va diviser chaque fois n par 2]
est ce que c'est juste?
merci de m'aider

2 réponses

Messages postés
499
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123
Salutations,

Presque. L'algo effectue log2(n) divisions.

M.
Messages postés
35
Date d'inscription
lundi 10 mars 2008
Statut
Membre
Dernière intervention
14 septembre 2009

merci bien bon courage