¿Por qué la complejidad de la computación de la serie de Fibonacci 2^n y no n^2?

El árbol de recursión para fib (n) sería algo así como:

                              n       
                           /     \
                          n-1    n-2      --------- maximum 2^1 additions
                         /  \    /   \
                       n-2   n-3 n-3 n-4  -------- maximum 2^2 additions
                      /   \           
                     n-3 n-4              -------- maximum 2^3 additions         
                                                ........
                                          -------- maximum 2^(n-1) additions  

1. Usando n-1 en 2^(n-1) ya que para fib (5) eventualmente bajaremos a fib(1)
2. Número de nodos internos = Número de hojas - 1 = 2^(n-1) - 1
3. Número de adiciones = Número de nodos internos + Número de hojas = (2^1 + 2^2 + 2^3 + ...) + 2^(n-1)
4. Podemos reemplazar el número de nodos internos a 2^(n-1) - 1 porque siempre será menor que este valor : = 2^(n-1) - 1 + 2^(n-1) ~ 2^n

Míralo así. Supongamos que la complejidad de calcular F(k), el número de Fibonacci kth, por recursión es como máximo 2^k para k <= n. Esta es nuestra hipótesis de inducción. Entonces la complejidad de calcular F(n + 1) por recursión es

F(n + 1) = F(n) + F(n - 1)

Que tiene complejidad 2^n + 2^(n - 1). Nótese que

2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).

Hemos demostrado por inducción que la afirmación de que calcular F(k) por recursión es a lo sumo 2^k es correcta.

Tienes razón en que la profundidad del árbol es O(n), pero no estás haciendo trabajo de O(n) en cada nivel. En cada nivel, usted hace O(1) trabajo por llamada recursiva, pero cada llamada recursiva entonces aporta dos nuevas llamadas recursivas, una en el nivel inferior y una en el nivel dos por debajo de ella. Esto significa que a medida que avanzas más y más por el árbol de recursión, el número de llamadas por nivel crece exponencialmente.

Curiosamente, en realidad puede establecer el número exacto de llamadas necesarias para calcular F(n) como 2F(n + 1) - 1, donde F (n) es el enésimo número de Fibonacci. Podemos probar esto inductivamente. Como caso base, para calcular F(0) o F (1), necesitamos hacer exactamente una llamada a la función, que termina sin hacer ninguna llamada nueva. Digamos que L(n) es el número de llamadas necesarias para calcular F (n). Entonces tenemos que

L(0) = 1 = 2*1 - 1 = 2F(1) - 1 = 2F(0 + 1) - 1

L(1) = 1 = 2*1 - 1 = 2F(2) - 1 = 2F(1 + 1) - 1

Ahora, para el paso inductivo, asumir que para todos n '

1 + L(n - 1) + L(n - 2)

= 1 + 2F((n - 1) + 1) - 1 + 2F((n - 2) + 1) - 1

= 2F (n) + 2F (n - 1) - 1

= 2(F(n) + F (n - 1)) - 1

= 2(F (n + 1)) - 1

= 2F (n + 1) - 1

Que completa la inducción.

En este punto, puede usar La fórmula de Binet para mostrar que

L(n) = 2(1/√5)(((1 + √5) / 2)ⁿ - ((1 - √5) / 2)ⁿ) - 1

Y por lo tanto L (n) = O(((1 + √5) / 2)ⁿ ). Si utilizamos la convención que

Φ = (1 + √5) / 2 &aprox; 1,6

Nosotros tener que

L (n) = Θ (φⁿ)

Y desde φ n) (usando la notación de-o pequeña).

Curiosamente, he elegido el nombre L(n) para esta serie porque esta serie se llama los números de Leonardo. Además de su uso aquí, surge en el análisis del algoritmo smoothsort .

Espero que esto ayude!

T (n) = t (n-1)+t (n-2) que se puede resolver mediante el método de árbol:

                                  t(n-1)  +  t(n-2)        2^1=2
                                   |         |  
                            t(n-2)+t(n-3)  t(n-3)+t(n-4)   2^2=4  
                                .               .          2^3=8
                                .               .           .
                                .               .           .

De manera similar para el último nivel . . 2^n
hará que total time complexity = >2+4+8+.....2^n después de resolver el gp anterior, obtendremos la complejidad del tiempo como O (2^n)

La complejidad de la serie de Fibonacci es O(F(k)), donde F(k) es el número k-ésimo de Fibonacci. Esto puede ser probado por inducción. Es trivial para el caso basado. Y suponga que para todo k

La complejidad O(2^n) del cálculo del número de Fibonacci solo se aplica al enfoque de recursión. Con un poco de espacio extra, puede lograr un rendimiento mucho mejor con O (n).

public static int fibonacci(int n) throws Exception {

  if (n < 0)
    throws new Exception("Can't be a negative integer")

  if (n <= 1)
    return n;

  int s = 0, s1 = 0, s2 = 1;
  for(int i= 2; i<=n; i++) {
    s = s1 + s2;
    s1 = s2;
    s2 = s;            
  }
  return s;
}

La complejidad de las series recursivas de Fibonacci es 2^n:
Estas serán las Relaciones de Recurrencia para Fibonacci recursivo

 T(n)=T(n-1)+T(n-2)                  No  of elements  2

Ahora resolviendo esta relación usando el método de sustitución(sustituyendo el valor de T(n-1) y T (n-2))

T(n)=T(n-2)+2*T(n-3)+T(n-4)          No  of elements  4=2^2

Otra vez sustituyendo los valores del término anterior obtendremos

T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6)  No  of elements  8=2^3

Después de resolverlo completamente, obtenemos

T(n)={T(n-k)+---------+---------}----------------------------->2^k  eq(3) 

Esto implica que el máximo no de llamadas recursivas en cualquier nivel será como máximo 2^n.
Y para todos los las llamadas recursivas en la ecuación 3 son Θ (1), por lo que la complejidad del tiempo será 2^n* ϴ(1)=2^n

No puedo resistir la tentación de conectar un algoritmo iterativo de tiempo lineal para Fib al recursivo de tiempo exponencial: si uno lee el maravilloso pequeño libro de Jon Bentley sobre "Escribir Algoritmos eficientes", creo que es un simple caso de "almacenamiento en caché": siempre que se calcule Fib(k), guárdelo en una matriz FibCached[k]. Siempre que se llame a Fib(j), primero verifique si está almacenado en caché en FibCached[j]; si es así, devuelva el valor; si no, use recursión. (Mira el árbol de las llamadas ahora ...)