En informática , la técnica de búsqueda de Fibonacci es un método de búsqueda de una matriz ordenada utilizando un algoritmo de dividir y conquistar 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 que se ejecuten aproximadamente 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 en el peor de los casos de O (log n ) (consulte la 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 suma repetida. La proporción de dos números consecutivos se acerca a la proporción áurea , 1.618 ... La búsqueda binaria funciona dividiendo el área de búsqueda en partes iguales (1: 1). La búsqueda de Fibonacci puede dividirlo en partes que se aproximan a 1: 1.618 mientras se utilizan operaciones más simples.
Si los elementos que se buscan tienen 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 al reducir ligeramente el tiempo promedio necesario para acceder un lugar de almacenamiento. Si la máquina que ejecuta la búsqueda tiene un caché de CPU mapeado directamente , la búsqueda binaria puede conducir a más pérdidas de caché porque los elementos a los que se accede a menudo tienden a reunirse en sólo 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 la sección Golden , un algoritmo de Jack Kiefer (1953) para buscar el máximo o mínimo de una función unimodal en un intervalo. [3]
Algoritmo
Sea k definido como un elemento en 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 en F que es 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 probar si un artículo está en la lista de números ordenados, siga estos pasos:
- Establezca k = m .
- Si k = 0, deténgase. No hay coincidencia; el elemento no está en la matriz.
- Compare el elemento con el elemento en F k −1 .
- Si el artículo coincide, deténgase.
- Si el elemento es menor que la entrada F k −1 , descarte los elementos de las posiciones F k −1 + 1 an . Establezca k = k - 1 y vuelva al paso 2.
- Si el elemento es mayor que la entrada F k −1 , descarte los elementos de las posiciones 1 a F k −1 . Vuelva a numerar los elementos restantes de 1 a F k −2 , establezca k = k - 2 y regrese al paso 2.
Implementación alternativa (de "Clasificación y búsqueda" de Knuth [4] ):
Dada una tabla de registros R 1 , R 2 , ..., R N cuyas claves son en orden creciente K 1 < K 2 <... < K N , el algoritmo de búsqueda para un argumento dado K . Suponga N + 1 = F k +1
Paso 1. [Inicializar] i ← F k , p ← F k -1 , q ← F k -2 (en todo el algoritmo, p y q serán números consecutivos de Fibonacci)
Paso 2. [Compare] Si K < K i , vaya al Paso 3 ; si K > K i ir a la Etapa 4 ; y si K = K i , el algoritmo termina con éxito.
Paso 3. [Disminuir i ] Si q = 0, el algoritmo termina sin éxito. De lo contrario, establezca ( i , p , q ) ← ( i - q , q , p - q ) (que mueve p y q una posición hacia atrás en la secuencia de Fibonacci); luego regrese al paso 2
Paso 4. [Incrementar i ] Si p = 1, el algoritmo termina sin éxito. De lo contrario, establezca ( i , p , q ) ← ( i + q , p - q , 2q - p ) (que mueve p y q dos posiciones hacia atrás en la secuencia de Fibonacci); y regrese al paso 2
Las dos variantes del algoritmo presentadas anteriormente siempre dividen el intervalo actual en un subintervalo más grande y uno más pequeño. Sin embargo, el algoritmo original [1] dividiría el nuevo intervalo en un subintervalo más pequeño y uno más grande en el Paso 4. Esto tiene la ventaja de que la nueva i está más cerca de la antigua i y es más adecuada para acelerar la búsqueda en cinta magnética.
Ver también
Referencias
- ↑ a b c Ferguson, David E. (1960). "Búsqueda fibonacciana". Comunicaciones de la ACM . 3 (12): 648. doi : 10.1145 / 367487.367496 . S2CID 7982182 .Tenga en cuenta que el análisis del tiempo de ejecución de este artículo es defectuoso, como señaló Overholt (1972). [ se necesita cita completa ]
- ^ Overholt, KJ (1973). "Eficiencia del método de búsqueda de Fibonacci". BIT Matemáticas numéricas . 13 (1): 92–96. doi : 10.1007 / BF01933527 . S2CID 120681132 .
- ^ Kiefer, J. (1953). "Búsqueda secuencial minimax de un máximo" . Actas de la American Mathematical Society . 4 (3): 502–506. doi : 10.1090 / S0002-9939-1953-0055639-3 .
- ^ Knuth, Donald E. (2003). El arte de la programación informática . vol. 3 (Segunda ed.). pag. 418.
|volume=
tiene texto extra ( ayuda )
- Lourakis, Manolis. "Búsqueda fibonacciana en C" . Consultado el 18 de enero de 2007 . Implementa el algoritmo anterior (no el original de Ferguson).