Las propiedades únicas de los números de Fibonacci han resultado útiles en las estructuras de datos.
El “montón de Fibonacci”, por ejemplo, es una implementación de una cola prioritaria que realiza una implementación basada en un montón binario dado un patrón de uso específico (creo que menos eliminaciones que inserciones). Internamente, los montones de Fibonacci se representan como un bosque de árboles en el que cada árbol tiene la propiedad de que el tamaño de un subárbol enraizado en un nodo con n hijos es al menos F ( n +2), donde F ( n ) es el enésimo número de Fibonacci . Entonces, el tiempo de ejecución que alcanzan los montones de Fibonacci depende implícitamente de las propiedades de [math] \ phi [/ math] a medida que la relación de F ( n ) / F ( n -1) se aproxima a [math] \ phi [/ math] como n se acerca al infinito.
No puedo pensar en ninguna estructura de datos o algoritmo que explícitamente use [math] \ phi [/ math], aparte de una novedad: se puede calcular el enésimo número de Fibonacci en tiempo O (log n ) en lugar de tiempo lineal por haciendo uso de la fórmula de Binet pero sin realizar operaciones de coma flotante. Calcula en términos de una forma binomial como [math] \ frac {a + b \ sqrt {5}} {c} [/ math] pero debido a las extrañas propiedades algebraicas de [math] \ phi [/ math] todas La irracionalidad y todas las matemáticas no enteras se cancelan por arte de magia. No es necesario calcular realmente [math] \ sqrt {5} [/ math] ‘s mientras se encuentra [math] \ phi ^ n [/ math]. Solo necesita realizar un seguimiento de los coeficientes enteros de los diversos términos y lograr un tiempo de ejecución logarítmico a través del método de “exponenciación por cuadratura”.
- ¿Cómo es la complejidad del tiempo O (n * sqrt (n))?
- ¿Por qué es importante considerar las anotaciones asintóticas (como límite superior, límite inferior y límite estrecho)?
- ¿Ser bueno en matemáticas me ayudaría a ser un mejor programador?
- En programación, ¿qué devuelve n & -n?
- ¿Cuál es la mejor descripción del cálculo lambda?
Más allá del ejemplo artificial anterior, no lo sé. Las propiedades especiales de [math] \ phi [/ math] básicamente tienen que ver con su naturaleza recursiva y su auto-similitud entre escalas. Uno puede imaginar esta utilidad de auto-similitud en áreas de geometría computacional en las que las estructuras de datos comunes ya aprovechan relaciones geométricas similares: algoritmos y estructuras de datos en las que las curvas de relleno de espacio aparecen en la literatura, o quizás el hash espacial. Tal vez hay algún análogo de un quadtree estructurado como cuadrados anidados y rectángulos dorados que supera a un quadtree estándar dado un patrón de uso especial.
