Complexité algo

tpoll -  
 tpoll -
Bonjour,
J'ai un problème avec ceci:
Écrire un algorithme qui calcule x a la puissance n avec une complexité logarithmique.
Justifier cette complexité et prouver l'algorithme.
J'ai écrit un algo, mais ma complexité est linéaire!Comment faire?
Merci d'avance!

1 réponse

  1.
    KX Messages postés 19031 Statut Modérateur 3 020
     
    Bonjour,

    Je te conseilles de calculer x^n avec n=2^k.
    Pour être logarithmique tu dois le faire en k étapes.
    0
    1. tpoll
       
      avec n=2^k?j'ai pas bien saisi...
      0
    2. KX Messages postés 19031 Statut Modérateur 3 020
       
      Si tu as n=2^k, alors k=log2(n), c'est mathématique...

      En passant de 2^0 à 2^1 jusqu'à 2^k tu seras linéaire sur k donc logarithmique sur n
      0
    3. tpoll
       
      ok, merci!
      0

Discussions similaires

Algorithme avec alg 32
Mira -
Utilisateur anonyme -

3 réponses
algo: créer toutes les combinaisons possibles
Kobaya -
librequetucrois -

25 réponses
Arnaque site Etsy
Fanchon -
madmyke -

2 réponses
Impossible de modifier mot de passe
Darshaq -
Help--ps2-- -

13 réponses
erreur de modification mot de passe win7
zouba_slim -
zouba_slim -

19 réponses