Sujet Précédent Sujet Suivant

Complexité algo

Fermé
tpoll - 24 nov. 2015 à 19:54
 tpoll - 25 nov. 2015 à 16:23
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 16755 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 12 février 2025 3 020
24 nov. 2015 à 20:50
Bonjour,

Je te conseilles de calculer x^n avec n=2^k.
Pour être logarithmique tu dois le faire en k étapes.
0
tpoll
24 nov. 2015 à 22:27
avec n=2^k?j'ai pas bien saisi...
0
KX Messages postés 16755 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 12 février 2025 3 020
24 nov. 2015 à 22:39
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
25 nov. 2015 à 16:23
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
Complexité
noemie.der -
jordane45 -

1 réponse
[Active Directory] Problème de mot de passe
Utilisateur anonyme -
Utilisateur anonyme -

6 réponses
complexité
walamefteh -
walamefteh -

2 réponses