Sujet Précédent Sujet Suivant

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 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
tpoll
 
avec n=2^k?j'ai pas bien saisi...
0
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
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
algo: créer toutes les combinaisons possibles
Kobaya -
librequetucrois -

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

19 réponses
algo procedure tres dificile
samiro6 -
DarkAurora -

1 réponse