Como calcular a complexidade computacional das implementações recursivas da série de fibonacci?

Question

# Implementação 1
def fibonacci_smart_recursive(n,x1=0,x2=1):
    if(n==1):
        return x1
    else:
        if(n==2):
            return x2
        else:
            return fibonacci_smart_recursive(n-1,x2,x1+x2)

#Implementação 2
def fibonacci_recursive(n):
    if(n>2):
        return fibonacci_recursive(n-1)+fibonacci_recursive(n-2)
    else:
        if(n==2):
            return 1    
        else:
            return 0 

if __name__ == '__main__':

    print fibonacci_recursive(12)

    print fibonacci_smart_recursive(12)

Answer 1

A primeira implementação é trivialmente linear e satisfaz \(O(n)\).

Para encontrar a complexidade computacional da segunda implementação, precisamos notar que a complexidade computacional de \(F(n)\) pode ser calculada pelo número de somas efetuadas:

\(n=1\) temos 0 somas
\(n=2\) temos 0 somas
\(n=3\) temos 1 soma
\(n=4\) precisamos calcular \(F(4)=F(3)+F(2)\) e temos 1 soma
\(n=5\) precisamos calcular \(F(5)=F(4)+F(3)\) e temos 2 somas
\(n=6\) precisamos calcular \(F(6)=F(5)+F(4)\) e temos 3 somas

Logo, o número de somas cresce com o termo \(F(n)\) da sequência de Fibonacci e basicamente precisamos descobrir como \(F(n)\) cresce.

A sequência de Fibonacci é um equação em diferenças com coeficientes constantes e é trivial mostrar que sua solução é dada por

\[F(n)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n \in \Theta(\phi^n),\]

onde \(\phi=\frac{1+\sqrt{5}}{2}\).