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!
A voir également:

1 réponse

Réponse 1 / 1
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
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 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
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 -
Whismeril -

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

13 réponses
Stratégie de mot de passe est grisé dans secpol.msc
Win10-AD -
Renardrougeetnoir -

6 réponses
[algorithme calcul pgcd]
make1989 -
ZAINPRODUCT -

23 réponses
Algo poker
Algo23 -
YCN- -

2 réponses