En informática , la técnica de búsqueda de Fibonacci es un método de búsqueda en una matriz ordenada utilizando un algoritmo de dividir y vencer que reduce las posibles ubicaciones con la ayuda de los números de Fibonacci . [1] En comparación con la búsqueda binaria , donde la matriz ordenada se divide en dos partes de igual tamaño, una de las cuales se examina más a fondo, la búsqueda de Fibonacci divide la matriz en dos partes que tienen tamaños que son números de Fibonacci consecutivos. En promedio, esto lleva a ejecutar alrededor de un 4% más de comparaciones, [2] pero tiene la ventaja de que solo se necesitan sumas y restas para calcular los índices de los elementos de la matriz a los que se accede, mientras que la búsqueda binaria clásica necesita desplazamiento de bits (ver Operación bit a bit ), división o multiplicación, [1] operaciones que eran menos comunes en el momento en que se publicó por primera vez la búsqueda de Fibonacci. La búsqueda de Fibonacci tiene una complejidad promedio y de peor caso de O (log n ) (ver Notación Big O ).
La secuencia de Fibonacci tiene la propiedad de que un número es la suma de sus dos predecesores. Por lo tanto, la secuencia se puede calcular mediante la adición repetida. La razón de dos números consecutivos se aproxima al número áureo , 1,618... La búsqueda binaria funciona dividiendo el área de búsqueda en partes iguales (1:1). La búsqueda de Fibonacci puede dividirla en partes que se aproximan a 1:1,618 mientras se utilizan las operaciones más simples.
Si los elementos que se buscan tienen un almacenamiento de memoria de acceso no uniforme (es decir, el tiempo necesario para acceder a una ubicación de almacenamiento varía según la ubicación a la que se accede), la búsqueda de Fibonacci puede tener la ventaja sobre la búsqueda binaria de reducir ligeramente el tiempo promedio necesario para acceder a una ubicación de almacenamiento. Si la máquina que ejecuta la búsqueda tiene una caché de CPU mapeada directamente , la búsqueda binaria puede llevar a más errores de caché porque los elementos a los que se accede a menudo tienden a agruparse en solo unas pocas líneas de caché; esto se mitiga dividiendo la matriz en partes que no tienden a ser potencias de dos. Si los datos se almacenan en una cinta magnética donde el tiempo de búsqueda depende de la posición actual del cabezal, una compensación entre un tiempo de búsqueda más largo y más comparaciones puede llevar a un algoritmo de búsqueda que esté sesgado de manera similar a la búsqueda de Fibonacci.
La búsqueda de Fibonacci se deriva de la búsqueda de sección áurea , un algoritmo de Jack Kiefer (1953) para buscar el máximo o mínimo de una función unimodal en un intervalo. [3]
Sea k un elemento de F , la matriz de números de Fibonacci. n = F m es el tamaño de la matriz. Si n no es un número de Fibonacci, sea F m el número más pequeño de F que sea mayor que n .
La matriz de números de Fibonacci se define donde F k +2 = F k +1 + F k , cuando k ≥ 0 , F 1 = 1 y F 0 = 1 .
Para comprobar si un elemento está en la lista de números ordenados, siga estos pasos:
Implementación alternativa (de "Ordenar y buscar" de Knuth [4] ):
Dada una tabla de registros R 1 , R 2 , ..., R N cuyas claves están en orden creciente K 1 < K 2 < ... < K N , el algoritmo busca un argumento dado K . Supongamos que N +1= F k +1
Paso 1. [Inicializar] i ← F k , p ← F k −1 , q ← F k −2 (a lo largo del algoritmo, p y q serán números de Fibonacci consecutivos)
Paso 2. [Comparar] Si K < K i , vaya al Paso 3 ; si K > K i vaya al Paso 4 ; y si K = K i , el algoritmo finaliza exitosamente.
Paso 3. [Reducir i ] Si q = 0, el algoritmo finaliza sin éxito. De lo contrario, establezca ( i , p , q ) ← ( i − q , q , p − q ) (lo que mueve p y q una posición hacia atrás en la secuencia de Fibonacci); luego regrese al Paso 2
Paso 4. [Aumentar i ] Si p = 1, el algoritmo finaliza sin éxito. De lo contrario, establezca ( i , p , q ) ← ( i + q , p − q , 2 q − p ) (lo que mueve p y q dos posiciones hacia atrás en la secuencia de Fibonacci); y vuelva al Paso 2
Las dos variantes del algoritmo presentadas anteriormente siempre dividen el intervalo actual en un subintervalo mayor y otro menor. Sin embargo, el algoritmo original [1] dividiría el nuevo intervalo en un subintervalo mayor y otro menor en el paso 4. Esto tiene la ventaja de que el nuevo i está más cerca del antiguo i y es más adecuado para acelerar la búsqueda en cinta magnética.