La relación de recurrencia en consideración es la de la Serie Fibonacci, expresada como la suma del tiempo para calcular el término (n-1) + tiempo para calcular el término (n-2) th + el tiempo necesario para sumarlos [ O (1)].
T (n) = T (n-1) + T (n-2) + O (1)
Ahora, puede haber dos formas de averiguar la complejidad del tiempo.
- ¿Cuáles son los algoritmos más utilizados en los que puedo confiar para mejorar mis habilidades de resolución de problemas?
- ¿Qué debo comenzar primero con estructuras de datos y algoritmos o inteligencia artificial de aprendizaje automático?
- ¿Cuál ha sido el desarrollo reciente en algoritmos de búsqueda en tiempo real?
- Descubrí el algoritmo de Dijkstra yo mismo. ¿Puedo decir que soy bueno en informática?
- ¿Crees que KNN tiene privilegios en comparación con otros algoritmos de aprendizaje automático porque aprende con el tiempo?
- Enmarcando el árbol de recursión :
Para generar el quinto número de la serie, el árbol se vería así:
La profundidad del árbol es n, y hasta el nivel (n / 2) de cada nivel tendrá
2 ^ k nodos (0 <= k <= log2 (n + 1)). Las llamadas recursivas continuarán hasta que se alcancen las hojas, es decir, F (1). Por lo tanto, el nivel final comprende solo los casos base F (1) y F (0).
Por lo tanto, total de nodos en el árbol de recursión:
1 + 2 + 4 + ……. (N-1)
= 1 ((2 ^ n) -1) / (2-1)
= (2 ^ n) -1
Entonces, yendo por el árbol de recursión, podemos descubrir que la relación de recurrencia es asintóticamente O (2 ^ n).
- Usando la forma cerrada de la serie de Fibonacci :
donde ‘phi’
es la proporción áurea 
Ya que,
Por lo tanto,
Por lo tanto , Fn es asintótico para:
(Fuente: número de Fibonacci )O , T (n) = Θ (1.6 ^ n)
