Algoritmo de búsqueda de Fibonacci (Fibonacci Search)
1606
0
2025-08-03 12:40:31
Prohibida la reproducción sin autorización del autor
30
4
18
1
课程总结
收起全部章节
关闭课程总结
暂无课程总结
La búsqueda de Fibonacci es un algoritmo de búsqueda basado en la secuencia de Fibonacci, utilizado para arreglos ordenados. Es similar a la búsqueda binaria, también utiliza el concepto de dividir y conquistar, pero decide la posición de división mediante números de Fibonacci, en lugar del punto medio.
🧠 ¿Por qué usar números de Fibonacci?
La búsqueda de Fibonacci intenta utilizar la proporción áurea (≈0.618) para reducir el rango de búsqueda, localizando así el valor objetivo de manera más eficiente, especialmente ventajoso cuando el arreglo es grande.
✅ Prerrequisitos:
Los datos son un arreglo ordenado ascendentemente.
No es necesario que estén distribuidos uniformemente (más general que la búsqueda por interpolación).
📋 Flujo del algoritmo:
Encuentra el número de Fibonacci más pequeño F(k) tal que F(k) - 1 ≥ longitud del arreglo n.
Usa F(k-1) para comparar la posición del elemento.
Mueve el rango según el resultado de la comparación, y reduce el valor de k en consecuencia (de F(k) a F(k-1) o F(k-2)).
Repite hasta encontrar el objetivo o el rango esté vacío.
⏱️ Complejidad temporal:
Complejidad temporal en el peor de los casos: O(log n)
Igual que la búsqueda binaria, pero con un factor constante ligeramente mayor.
