Bonsoir je souhaite calculer la complexité en temps et en espace de mon algorithme récursif :
fonction f(n entier) : entier
si n<=2
retourner 17
si non retourner f(n-1)*f(n-2)+f(n-3)
ma solution est la suivante :
complexité en temps : c(n)=c(n-1)+c(n-2)+c(n-3)+2 ( le 2 pour deux opérations )
complexité en espace : O(1)
que pensez vous ?
Merci d'avance.
J'en pense que ce serait idiot de calculer à chaque appel de f f(n-1), f(n-2) et f(n-3). Car le n-3 de n est le n-2 de n-1 et le n-2 de n est le n-1 de n-1.
Je suis pas allé au bout mais déjà quelques infos:
Chaque appel à f(n) engendre trois appels à la fonction f qui chacun engendreront trois appels, etc...
Si ta fonction était f(n-1)*f(n-1)+f(n-1) alors chaque appel en engendrerait trois, et ce sur n niveau. La complexité en temps serait donc O(3^n). C'est une limite haute, ton algo est plus rapide car f(n-3) va demander moins d'appels que f(n-1)
Si ta fonction était f(n-3)*f(n-3)+f(n-3) alors chaque appel en engendrerait trois, et ce sur n/3 niveau. alors la complexité en temps serait O(3^(n/3)). C'est une limite basse.
Ton algo a une complexité exponentielle.
Et minushabens a raison: l'approche récursive est une très mauvaise idée sur cet algo. Il vaut mieux itérer de 0 à n en stockant les résultats dans un tableau. Ce serait un algo linéaire en temps et en mémoire.
En temps, expo bien sûr.
Pour gagner du temps, une fonction récursive est en général expo à partir de deux sous appels (sauf cas particuliers si le double appel n'est pas systématique)
Pour te faire une idée, ton algo ressemble assez au calcul (naïf) des suites de Fibonacci dont tu trouveras assez facilement une étude complète et une implémentation itérative sur le net.
Un petit plus, les complexités spatiale et temporelle sont liées.
Un algo en O(a^n) (temporel) ne peut avoir une complexité spatiale inférieure à O(n) (et réciproquement)
Dans ton cas, la mémoire à prendre en compte est la pile (la mémoire utilisée à chaque appel de fonction)
+1 pour la complexité linéaire en temps, par contre pour la mémoire on serait plutôt en log(n), non?Envoyé par Yvanhoe
oops... je me suis trompé sur le formule. Avec la bonne le résultat diverge donc, sauf passe passe mathématique que je ne vois pas même en base 17, c'est bien exponentiel en temps et espace.
