Bonjour.

La professeur prend l'exemple de la suite de Fibonacci pour comparer la complexité de différents algorithmes.

Il est dit que l'ajout d'un nombre demande deux fois plus de mémoire que le précédent, soit une complexité 2^n (d'ailleurs, ne vaudrait-il mieux pas écrire 2^(n-1) ?).

Lorsque je dessine les arbres relatifs à l'algorithme dit "naïf", si je compte le nombre de fois où les opérations de soustraction (n-1, n-2) sont faites, cela nous donne pour n = 2, 3, 4 et 5 respectivement : 2 opérations, puis 4, puis 8 puis 14.

Ce qui donnerait plutôt une complexité pour le niveau n : (complexité niveau n-1) + (complexité niveau n-2) + 2...

Ou bien mon association complexité = nbre opérations fibo n'est pas bonne ?

Merci.

Pas d'avis sur la question ?