Luis Padron

Búsqueda de Fibonacci

La búsqueda de Fibonacci es un método de búsqueda en un array ordenado usando un algoritmo de divide y vencerás que disminuye las ubicaciones posibles con la ayuda de los números de Fibonacci. Comparado con la búsqueda binaria, Fibonacci busca las ubicaciones cuyas direcciones tienen poca dispersión. Por lo tanto, cuando los elementos se buscan, tiene un acceso a memoria no uniforme (el tiempo necesario para acceder a la ubicación de almacenamiento varía en dependencia de la ubicación previamente accedida), la búsqueda de Fibonacci tiene una ventaja sobre la búsqueda binaria en disminuir ligeramente el tiempo promedio necesario para acceder a la ubicación de almacenamiento.

Dado un array ordenado A y un elemento t, verificar si t esta en A:

Sea F el array de los números de Fibonacci. Fm es el m-ésimo elemento de F. n es el tamaño A. Sea m tal que Fm es el número más pequeño de F mayor o igual que n.

F es definido como: F0 = 1, F1 = 1, Fk = Fk-1 + Fk-2.

Búsqueda por sección dorada

Es una técnica simple de búsqueda de una sola variable de propósito general. Es similar en esencia al enfoque de la bisección para localizar raíces. La clave para hacer eficiente este procedimiento es la mejor elección de los puntos intermedios. Esta meta se puede alcanzar al especificar que las siguientes dos condiciones se cumplan.

Sustituyendo la primera ecuación en la segunda tenemos:

Si tomamos el reciproco y R = l2/l1, se llega a

1 + R = 1/R

R2 + R - 1=0

Interpolación Cuadrática

La interpolación cuadrática tiene la ventaja del hecho que un polinomio de segundo orden con frecuencia proporciona una buena aproximación a la forma de f(x) cercana a un valor máximo o mínimo.

Este método al igual que el de Muller hacen una aproximación cuadrática de un polinomio, así f(x) = Ax2 + Bx + C. Para esta función el mínimo o máximo se localiza en

Se puede mostrar que después de un manejo algebraico el valor de x3 que maximiza la ecuación es:

...