Existe una forma cerrada para calcular un término de Fibonacci.
Puedes verlo aquí: número de Fibonacci
Sabemos que la secuencia de Fibonacci es una función monotónica. Para un número natural dado N, puede encontrar n tal que:
F_ (n-1) <N <F_ (n)
La complejidad se puede calcular de la siguiente manera:
El cálculo de pow (phi, n) depende del hardware de su computadora, por lo tanto, podría ser O (1). En el peor de los casos, sería O (log n).
Y para resolver raíz, un simple solucionador de raíz binaria puede converger en pasos O (log n).
Entonces, su complejidad total será O (log ^ 2 (n)).
Si desea encontrar los términos # fibonacci entre N1 y N2, use el algoritmo anterior en N1 y N2. Y luego restar el resultado.
