Complejidad temporal del programa recursivo de Fibonacci

Los números de Fibonacci son los números en la siguiente secuencia de enteros 0, 1, 1, 2, 3, 5, 8, 13…
Matemáticamente, los números de Fibonacci se pueden escribir mediante la siguiente fórmula recursiva.

For seed values F(0) = 0 and F(1) = 1
F(n) = F(n-1) + F(n-2)

Antes de continuar con este artículo, asegúrese de estar familiarizado con el enfoque recursivo discutido en Programa para números de Fibonacci

Análisis del programa recursivo de Fibonacci:
Sabemos que la ecuación recursiva de Fibonacci es $T(n)$ = $T(n-1)$ + $T(n-2)$ + $O(1)$ .
Lo que esto significa es que el tiempo necesario para calcular fib(n) es igual a la suma del tiempo necesario para calcular fib(n-1) y fib(n-2). Esto también incluye el tiempo constante para realizar la adición anterior.

Al resolver la ecuación recursiva anterior, obtenemos el límite superior de Fibonacci, $O(2^n)$ pero este no es el límite superior ajustado. El hecho de que Fibonacci se pueda representar matemáticamente como una función recursiva lineal se puede usar para encontrar el límite superior ajustado.
Ahora Fibonacci se define como

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

La ecuación característica de esta función será
$x^2$ = $x$ + $1$
$x^2$ – $x$ – $1$ = $0$

Resolviendo esto por fórmula cuadrática podemos obtener las raíces como
$x$ = ( $1$ + $\sqrt{5}$ )/ $2$ y $x$ =( $1$ – $\sqrt{5}$ )/ $2$

Ahora sabemos que la solución de una función recursiva lineal se da como
$F(n)$ = $($\alpha_1)^n$ + $($\alpha_2)^n$

donde $$\alpha_1$ y $$\alpha_2$ son las raíces de la ecuación característica.
Entonces para nuestra función de Fibonacci $F(n)$ = $F(n-1)$ + $F(n-2)$ la solución será

$F(n)$ = $((1+$\sqrt{5})/2)^n$ + $((1-\sqrt{5})/2)^n$
Clearly $T(n)$ and $F(n)$ are asymptotically the same as both functions are representing the same thing.
Hence it can be said that
$T(n)$ = $O(((1+$\sqrt{5})/2)^n+((1-\sqrt{5})/2)^n)$
or we can write below (using the property of Big O notation that we can drop lower order terms)
$T(n)$ = $O(((1+$\sqrt{5})/2)^n$
$T(n)$ = $O(1.6180)^n$
This is the tight upper bound of fibonacci.\

Dato curioso:
1,6180 también se conoce como proporción áurea. Puede leer más sobre la proporción áurea aquí: Proporción áurea en matemáticas

Este artículo es una contribución de Vineet Joshi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta