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

Réponse 1 / 1
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   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
tpoll
 
avec n=2^k?j'ai pas bien saisi...
0
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   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
tpoll
 
ok, merci!
0

Discussions similaires

Algorithme avec alg 32
Mira -
Utilisateur anonyme -

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

13 réponses
[2003 Server] Mot de passe refusé !
mehdi -
sebsauvage -

4 réponses
[Active Directory] Problème de mot de passe
Utilisateur anonyme -
Utilisateur anonyme -

6 réponses
Complexité
noemie.der -
jordane45 -

1 réponse