Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Shop Recherche
1769 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Explication complexité d'un algorithme

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Explication complexité d'un algorithme

n°2270067
Jeckhys
Posté le 22-11-2015 à 14:27:22  profilanswer
 

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 !

mood
Publicité
Posté le 22-11-2015 à 14:27:22  profilanswer
 

n°2270072
flo850
moi je
Posté le 22-11-2015 à 18:12:37  profilanswer
 

parceque log(n) est la complexité maximale
Je suis trop rouillé pour faire une démonstration propre, mais  
 
Le nombres impaire (2n+1) : 0 tour de boucle ( et ça représente moitié des nombres entier)
Les nombres paires qui sont des nombres impaires doublés ( 2 x (2n+1)) : 1 tour (ça représente  une autre grosse brouette)
 


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


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Explication complexité d'un algorithme

 

Sujets relatifs
[Clos]Explication mathématique d'un algorithme plus ou moins "stable"algorithme d'enrichissement
Algorithme Unsharp Mask (HELP)Complexité Calendar Queue
[MATLAB] Algorithme ressortissant les plus courts chemins[HELP ] Explication d'un Programme
algorithme pour réseau d'échange numismatiqueAlgorithme pour le calcul de % de paiements affectés à des factures
Help, Algorithme de tri sélectif VBA 
Plus de sujets relatifs à : Explication complexité d'un algorithme


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR