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
Votes
Date
Date décroissante
KX
Modérateur
Bonjour,
Je te conseilles de calculer x^n avec n=2^k.
Pour être logarithmique tu dois le faire en k étapes.
tpoll
avec n=2^k?j'ai pas bien saisi...
KX
Modérateur
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
Trouvez des réponses à vos questions sur les langages, les frameworks et les astuces de codage. Échangez avec d'autres développeurs passionnés pour améliorer vos compétences en programmation et rester au fait des dernières tendances du secteur.