¿Cuál es la complejidad del tiempo para una solución iterativa de la serie Fibonacci?

Obtener una secuencia de Fibonacci de longitud N requiere iteraciones O (N). Pero, con cualquier N razonable, los números ya no se ajustan incluso a enteros de 64 bits. Debido a que los enteros de 64 bits no son suficientes, debe usar algún tipo de representación BigNum, lo que aumenta la complejidad del algoritmo.

El valor del número k-ésimo de Fibonacci, según Wikipedia, es aproximadamente [matemática] 1.62 ^ k / \ sqrt {5} [/ matemática]. A partir de esto, es fácil ver que a partir de k = 94 se debe usar un tipo BigNum. El número de bits necesarios para representar el número k, debe ser aproximadamente k * 0,68. La complejidad temporal para calcular k-ésimo número, es decir, resumiendo sus dos predecesores, también es O (k). Esto es así, a menos que se tome un atajo, como se describe en Wikipedia.

Ahora, dado que la iteración k cuesta O (k), realizar N tales iteraciones, cuando k va de 1 a N, costará [matemática] O (N ^ 2) [/ matemática]. Esto también es la complejidad de memoria requerida para mantener una secuencia de Fibonacci de longitud N.

Para N <94, si utiliza un número entero de 64 bits, el algoritmo actuará y se sentirá como si tuviera una complejidad lineal. Sin embargo, para N> 94 comienza a comportarse como un algoritmo de complejidad cuadrática.

Se considera que la complejidad de la serie iterativa de Fibonacci es el revestimiento O (n), pero el problema surge cuando N es lo suficientemente grande, por lo que generalmente no será lineal. Aquí debe usar el contenedor bigInteger para manejar números grandes y los enteros grandes son lentos porque internamente realiza alguna operación (operación aritmética) y eso también usa algún algoritmo específico.

La complejidad de un bucle que se ejecuta n-2 veces es O (n).

En general, las iteraciones na tienen una complejidad O (n) para valores de n razonablemente mayores que a.

No creo que representar la entrada (n) vaya a tener ningún impacto. Será un número entero positivo y va a iterar n-2 veces, sin importar la cantidad de bits utilizados para representar ese número.