Complexité de l'algorithme de Fibonacci récursif

En utilisant l'algorithme récursif de Fibonacci suivant:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Si j'entre le nombre 5 pour trouver fib (5), je sais que cela produira 5 mais comment puis-je examiner la complexité de cet algorithme? Comment calculer les étapes impliquées?

La plupart du temps, vous pouvez représenter les algorithmes récursifs à l'aide d'équations récursives. Dans ce cas, l'équation récursive de cet algorithme est . Ensuite, vous pouvez trouver la forme fermée de l'équation en utilisant la méthode de substitution ou la méthode d'expansion (ou toute autre méthode utilisée pour résoudre les récurrences). Dans ce cas, vous obtenez T ( n ) = Θ ( ϕ n ) , où $T(n) = T(n-1) + T(n-2) + \Theta(1)$$T(n) = \Theta(\phi^n)$$\phi$est le nombre d'or ( ).$\phi = \frac{(1 + \sqrt{5})}{2}$

Si vous souhaitez en savoir plus sur la façon de résoudre les récidives, je vous recommande fortement de lire le chapitre 4 de Introduction aux algorithmes .

comme alternative aux relations récurrentes / analyse mathématique (mais pas comme substitut ), un simple exercice empirique, apparemment peu enseigné en classe mais très instructif, consiste à compter le nombre d'exécutions de la fonction, puis à représenter graphiquement le nombre d'une plage de petites entrées n , puis courbe ajuster le résultat. les résultats correspondent généralement étroitement à l'approche mathématique théorique.

Un bon matériel de support pour cet exercice peut être trouvé dans le chapitre 3 en ligne gratuit, Durée d'exécution des algorithmes / Fondements de l'informatique , Ullman

Le résultat de fib (n) est la somme de tous les appels récursifs qui ont renvoyé 1. Par conséquent, il existe exactement des appels récursifs fib (n) évaluant fib (1). Le temps d'exécution est donc Ω (fib (n)); vous devez montrer que les appels renvoyant 0 et les autres appels récursifs n'y ajoutent pas de manière significative.

Le même raisonnement s'appliquerait à toute fonction définie récursivement qui retourne 1 ou 0, ou le résultat d'un autre appel récursif.

Une borne inférieure est intuitive: $T(n)=T(n-1)+T(n-2)$ $T(n)>2T(n-2)$ puisque $T(n-1)>T(n-2)$ Par conséquent $T(n)= \Omega(c^{n})$