Complexidade do algoritmo recursivo de Fibonacci

Usando o seguinte algoritmo recursivo de Fibonacci:

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

Se eu inserir o número 5 para encontrar fib (5), sei que isso produzirá 5, mas como examino a complexidade desse algoritmo? Como calculo as etapas envolvidas?

Na maioria das vezes, você pode representar os algoritmos recursivos usando equações recursivas. Nesse caso, a equação recursiva para esse algoritmo é . Em seguida, você pode encontrar a forma fechada da equação usando o método de substituição ou o método de expansão (ou qualquer outro método usado para resolver recorrências). Nesse caso, você obtém T ( n ) = Θ ( ϕ n ) , onde $T(n) = T(n-1) + T(n-2) + \Theta(1)$$T(n) = \Theta(\phi^n)$$\phi$é a proporção áurea ( )$\phi = \frac{(1 + \sqrt{5})}{2}$

Se você quiser descobrir mais sobre como resolver recorrências, recomendo fortemente que você leia o capítulo 4 da Introdução aos algoritmos .

como alternativa às relações de recorrência / análise matemática (mas não um substituto ), um simples exercício empírico, aparentemente não ensinado com muita frequência nas aulas, mas muito informativo, é contar o número de execuções da função e, em seguida, representar graficamente a contagem para um intervalo de pequenas n entradas e, em seguida, curva ajustam-se ao resultado. Os resultados geralmente correspondem à abordagem matemática teórica.

um bom material de apoio para este exercício pode ser encontrado no capítulo on-line gratuito 3, tempo de execução dos algoritmos / Foundations of Computer Science , Ullman

O resultado de fib (n) é a soma de todas as chamadas recursivas que retornaram 1. Portanto, existem exatamente chamadas recursivas de fib (n) avaliando fib (1). Portanto, o tempo de execução é Ω (fib (n)); você precisaria mostrar que as chamadas retornando 0 e as outras chamadas recursivas não contribuem significativamente para isso.

O mesmo raciocínio se aplica a qualquer função definida recursivamente que retorne 1 ou 0 ou o resultado de outra chamada recursiva.

Um limite inferior é intuitivo: $T(n)=T(n-1)+T(n-2)$ $T(n)>2T(n-2)$ Desde a $T(n-1)>T(n-2)$ Conseqüentemente $T(n)= \Omega(c^{n})$