La complexité de l'espace de la séquence Fibonacci

Question

J'ai vu un manuel sur la complexité de l'espace du pire cas de la séquence de Fibonacci. Cependant, je pose la question suivante:

Answer 1

Vous pouvez commencer par un exemple concret et généraliser. Commencez avec n = 5.

S(5) = S(4) + c 
    = (S(3) + c) + c 
    = ((S(2) + c) + c) + c 
    = (((S(1) + c) + c) + c) + c 

    = S(1) + 4c 

Il y a 4 c quand n = 5. En général, il y a n-1 c.