Discussion :

[Simonlp]

Bonsoir, je cherche deux algorithmes qui élèvent n la puissance p, un en O(n) et l'autre en 0(ln(n))

J'avais pensé à un algo récursif :

algo (int n, int p)
si p = 0 retourner 1
sinon retourner r=r*algo(p-1)

Cependant je ne pense pas que sa complexité soit la bonne.
Pourriez vous m'aider ?

[kwariz]

Bonsoir,

En général quand tu es en phase de recherche tu peux te dire qu'une complexité en O(n) signifie «il y aura une boucle simple variant de 1 à n à peu près» ou en récursif «il y aura un appel récursif sur n-1 en s'arrêtant à pas loin de 1». Une complexité en O(ln(n)) devrait te faire chercher un algorithme qui résout un problème en résolvant un problème dont la taille est divisé par une constante, un peu comme dans la recherche dichotomique dans un tableau trié => trouver un élément dans un tableau trié de n élément se résout en le trouvant dans un tableau de taille n/2 ...

Quelle est la complexité de ton algo ?
Peux-tu exprimer a^n en fonction de a^(n/2) par exemple ?

[Simonlp]

Si je suis ce que vous m'avez dit, la complexité de mon algo est bien en O(n) non ?
Comme a^n=(a^(n/2))*(a^(n/)), pour que la complexité soit en O(ln(n)) il faut que j'appelle la méthode avec n/2 en entrée, mais j'imagine que je dois encore le modifier...?

[prgasp77]

kwariz> Tiens, attrape ça

Comme a^n=(a^(n/2))*(a^(n/)) [...]

Voila ! tu y es ! S'il te faut k étapes pour calculer a^(n/2), combien t'en faut-il pour en calculer a^n ? Conclus sur la relation entre k et n (ho ! le joli log !) .

[Simonlp]

Il m'en faudrait k² ?
Je suis un peu un long à la détente, mais j'arrive toujours pas à voir comment je dois construire l'algorithme...

[prgasp77]

Perdu. k+1 . Et pas de question par MP stp.

[souviron34]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
res = n 
pour i = 1 jusqu'à i < p
  res = n * res

O(p-1)