algorithm - recursiva - ¿La búsqueda de fibonacci es más rápida que la búsqueda binaria?
busqueda binaria recursiva (2)
¿Fibonacci busca más rápido que la búsqueda binaria sin tener en cuenta la velocidad operativa? Como los pasos de búsqueda binaria son menos.
Depende del sistema de almacenamiento subyacente de la lista. Por ejemplo, piensa en un disco. Es mucho más "barato" buscar una ubicación en el mismo cilindro de la lectura anterior, ya que el brazo de lectura no tiene que moverse. Por lo tanto, si sus lecturas son mucho más cercanas entre sí, es más probable que tenga que mover menos el brazo de lectura, por lo que el tiempo esperado de cada búsqueda de disco es más corto. Además, mover el brazo de lectura a través de menos cilindros es similarmente más rápido que moverlo a través de más cilindros
En el ejemplo:
Es mucho más barato mover el brazo de lectura de (1) a (2) que de (1) a (3). Y dado que (2) está "más cerca" (en términos de direcciones), entonces (3), los saltos más cortos tienen más probabilidades de estar en esta categoría. [De (1) a (2) el brazo de lectura no se moverá en absoluto, solo dejará que el disco gire hasta que llegue a él]
La división por 2 se puede hacer mediante la operación de cambio de bit, ¿es realmente más lento que la suma?
Esto es principalmente un problema de hardware (y optimización del compilador). No puedo imaginar ninguna razón por la cual una fabricación no hará esta optimización, y el cambio de bit en la mayoría de las implementaciones que conozco es tan rápido como las adiciones.
¿Cuál es la ventaja de la búsqueda de Fibonacci en comparación con la búsqueda binaria?
Como se menciona en (1), una distancia más corta entre las búsquedas de disco consecutivas da como resultado tiempos de búsqueda más cortos (esperados).
Leí algunos materiales que dicen que la búsqueda de Fibonacci es más rápida que la búsqueda binaria en promedio, y la causa principal es "solo implica sumas y restas, no división por 2".
Tengo algunas preguntas:
1. ¿La búsqueda Fibonacci es más rápida que la búsqueda binaria sin tener en cuenta la velocidad operativa? Como los pasos de la búsqueda binaria son menores.
2. La división por 2 se puede hacer mediante la operación de cambio de bit, ¿es realmente más lento que la suma?
3. ¿Cuál es la ventaja de la búsqueda de Fibonacci en comparación con la búsqueda binaria?
Adiciones, restas y divisiones por 2 todas toman un solo reloj. Entonces la aritmética involucrada no favorece a Fibonacci, al contrario.
Y necesitará aproximadamente un 44% más de búsquedas con Fibonacci ( Log(2)/Log(Phi) - 1 ). ¡Difícil de compensar con accesos de memoria más rápidos!
Si está buscando alternativas a la búsqueda binaria, pruebe su suerte con la búsqueda de interpolación. http://en.wikipedia.org/wiki/Interpolation_search