algorithm - programacion - ¿Por qué la complejidad de calcular las series de Fibonacci 2 ^ n y no n ^ 2?

sucesion de fibonacci ejercicios (9)

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

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

Estoy tratando de encontrar la complejidad de la serie de Fibonacci utilizando un árbol de recursión y la height of tree = O(n) peor caso, el cost of each level = cn , por lo tanto la complexity = n*n=n^2

¿Cómo es que es O(2^n) ?

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 la serie de Fibonacci es O (F (k)), donde F (k) es el kth número de Fibonacci. Esto puede ser probado por inducción. Es trivial para el caso basado. Y supongamos que, para todo k <= n, la complejidad de calcular F (k) es c * F (k) + o (F (k)), luego para k = n + 1, la complejidad de calcular F (n + 1) ) es c * F (n) + o (F (n)) + c * F (n-1) + o (F (n-1)) = c * (F (n) + F (n-1) ) + o (F (n)) + o (F (n-1)) = O (F (n + 1)).

La complejidad de la serie recursiva de Fibonacci es 2 ^ n:
Esta será la relación de recurrencia para Fibonacci recursivo

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

Ahora, al resolver 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

Nuevamente 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 por completo, obtenemos

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

Esto implica que el número máximo de llamadas recursivas en cualquier nivel será como máximo de 2 ^ n.
Y para todas las llamadas recursivas en la ecuación 3 es Θ (1) entonces la complejidad del tiempo será 2^n* ϴ(1)=2^n

La complejidad de un ingenuo fibonacci recursivo es de hecho 2ⁿ.

T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) = = T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...

En cada paso, usted llama T dos veces, por lo tanto, proporcionará una eventual barrera asintótica de:
T(n) = 2⋅2⋅...⋅2 = 2ⁿ

bonificación : la mejor implementación teórica para fibonacci es en realidad una fórmula cercana , usando la proporción áurea :

Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]

(Sin embargo, adolece de errores de precisión en la vida real debido a la aritmética de punto flotante, que no son exactos)

Míralo así. Supongamos que la complejidad de calcular F(k) , el kth número de Fibonacci, 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) . Tenga en cuenta 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.

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

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

Curiosamente, puedes establecer la cantidad exacta 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 finaliza sin realizar ninguna nueva llamada. Digamos que L (n) es el número de llamadas necesarias para calcular F (n). Entonces tenemos eso

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, supongamos que para todos los n ''<n, con n ≥ 2, ese L (n'') = 2F (n + 1) - 1. Luego, para calcular F (n), necesitamos hacer 1 llamar a la función inicial que calcula F (n), que a su vez activa las llamadas a F (n-2) y F (n-1). Por la hipótesis inductiva sabemos que F (n-1) y F (n-2) se pueden calcular en llamadas L (n-1) y L (n-2). Por lo tanto, el tiempo de ejecución total es

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 así L (n) = O (((1 + √5) / 2) ⁿ ). Si usamos la convención que

φ = (1 + √5) / 2 ≈ 1.6

Tenemos eso

L (n) = Θ (φ ⁿ )

Y como φ <2, esto es o (2 ⁿ ) (usando notación little-o).

Curiosamente, he elegido el nombre L (n) para esta serie porque esta serie se llama 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 . . . . . .

similarmente para el último nivel. . 2 ^ n
hará una complejidad de tiempo total => 2 + 4 + 8 + ..... 2 ^ n después de resolver el gp anterior obtendremos complejidad de tiempo como O (2 ^ n)