Fibonacci Sequence
La sucesión de Fibonacci tiene cada término igual a la suma de los dos anteriores (0,1,1,2,3,5,8...); se relaciona con la proporción áurea y aparece ampliamente en la naturaleza y los algoritmos.
Propósito
Describir patrones de crecimiento, presentes en fenómenos naturales y en el análisis de complejidad algorítmica.
Mecanismo
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Forma cerrada (fórmula de Binet): F(n)=(φ^n-ψ^n)/√5, donde φ=(1+√5)/2 es la proporción áurea. La exponenciación matricial o el fast doubling la calculan en O(log n). La recursión ingenua es exponencialmente lenta, O(φ^n).
Casos de uso
- Análisis de complejidad algorítmica
- Cálculo de indicadores técnicos (retroceso de Fibonacci)
- Modelado de patrones naturales
- Enseñanza de programación dinámica
Ejemplos
- entrada
F(10)Output550,1,1,2,3,5,8,13,21,34,55
Errores comunes
- Naive recursion recomputes subproblems and runs exponentially slow
- Use memoization or fast matrix exponentiation
Términos relacionados
Factorial
El factorial n! = n×(n-1)×...×1 es la base de las permutaciones y combinaciones; crece extremadamente rápido, y 20! ya supera el rango de un entero de 64 bits. GLOSARIO
Big O Notation
La notación O grande describe el límite superior asintótico de una función, usada para analizar la complejidad temporal/espacial de los algoritmos ignorando constantes y términos de orden inferior. GLOSARIO
BigInteger
BigInteger es un tipo de entero de precisión arbitraria, no limitado por un tamaño de palabra fijo, usado para cálculos más allá del rango de los enteros nativos (como criptografía y combinatoria). GLOSARIO