Un algoritmo es como un conjunto de instrucciones que se
deben seguir para realizar una tarea concreta. Este se rige por una serie de
pasos o ciclos con sus condiciones definidas para el proceso del trabajo que se
quiere hacer.
Hoy nos basaremos mayormente en los algoritmos de búsqueda,
estos se encargan de encontrar un elemento en una estructura de datos. Existen diversos
algoritmos para este propósito.
Unos de los vistos en las clases anteriores son el
secuencial, binario y el de interpolación.
Secuencial:
Uno de los algoritmos más sencillos y fáciles de implementar,
ya que su única función es la de comparar cada elemento de la estructura de
datos con el elemento que se quiere encontrar:
L: Largo de la estructura
T: temporal contador
ELE: Elemento a buscar
A: Estructura donde se desea buscar
Mientras L >
T:
Si ELE es
igual a A posición [T]:
Retorna
ELE
Si no:
Incrementa
en uno a T
Retorna -1
Como vemos el algoritmo es muy sencillo, el problema con
este es la capacidad de procesamiento que requiere y la pérdida de tiempo que ocasionaría
utilizarlo en grandes estructuras de datos.
Binario:
Otro de los más conocidos es el algoritmo binario, este lo
que hace es hacer división por 2 del arreglo y compara en cuál de las dos
mitades se puede encontrar el elemento deseado, haciéndolo mucho más eficiente
que el exponencial ya que acorta el tiempo y procesamiento de la búsqueda.
Datos de entrada:
vec: vector
en el que se desea buscar el dato
tam: tamaño
del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive.
dato:
elemento que se quiere buscar.
Variables
centro:
subíndice central del intervalo
inf: límite
inferior del intervalo
sup: límite
superior del intervalo
inf = 0
sup = tam-1
Mientras inf <= sup:
centro =
((sup - inf) / 2) + inf // División entera: se trunca la fracción
Si
vec[centro] == dato devolver verdadero y/o pos, de lo contrario:
Si dato
< vec[centro] entonces:
sup =
centro - 1
En caso
contrario:
inf =
centro + 1
Fin (Mientras)
Devolver Falso
Fuente:
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda#B.C3.BAsqueda_dicot.C3.B3mica_.28binaria.29
La condición (inconveniente
en algunos casos) para utilizar este algoritmo es que la estructura que se va
utilizar debe tener algún tipo de orden en los elementos que la componen.
Interpolación:
Uno de los últimos de
los cuales se hablo fue el algoritmo de interpolación, este es muy similar al
algoritmo binario, pero con una peculiaridad de que con una formula trata de
tener un rango de donde se ubica el elemento, esto quiere decir que se obvia
que los elementos de la estructura son números enteros. En este algoritmo los
elementos también deben tener un tipo de orden secuencial.
Esta fórmula es la
que calcula la posición promedio de donde se podría ubicar el elemento deseado.
Con el mismo
procedimiento del binario, pero implementando está formula se obtiene un poco
más de precisión a la hora de encontrar un elemento.
Fibonacci
“En ciencia de la computación, la técnica de 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. El típico ejemplo de acceso no
uniforme al almacenamiento es una cinta magnética, donde el tiempo de acceso a un elemento en particular
es proporcional a su distancia desde el elemento actual apuntado por el cabezal
de la cinta. Note, sin embargo, que grandes arrays no adecuados en la cache
del CPU o incluso en RAM pueden ser considerados como ejemplos de acceso no
uniforme. La búsqueda de Fibonacci tiene complejidad O(log(x)) (Ver notación de O Grande). La búsqueda de Fibonacci fue concebida por primera vez
por Kiefer (1953) como una
búsqueda minimax para el
máximo (mínimo) de una función unimodal en un intervalo.”
Información tomada de
Wikipedia.
Paso Inicial Fijar h > 0 y > 0.
Elegir n tal que Fn > b−a h.
Hacer a1 = a, b1 = b, y1 = a1 + 1 − Fn−1 Fn (b1
− a1) z1 = a1 + Fn−1 Fn (b1 − a1), y k = 1.
Paso General
Repetir: 1. Si f(yk) ≥ f(zk), ir a 2.
En caso contrario, ir
a 3.
2. Hacer ak+1 = yk, bk+1 = bk, yk+1 = zk y zk+1 = ak+1 +
Fn−k−1 Fn − k (bk+1 − ak+1).
Si k = n − 2, ir a 5.
En caso contrario, calcular f(zk+1) e ir a 4.
3. Hacer ak+1 = ak, bk+1 = zk, zk+1 = yk y calcular yk+1 =
ak+1 + 1 − Fn−k−1 Fn − k (bk+1 − ak+1).
Si k = n − 2, ir a 5.
En caso contrario, calcular f(zk+1) e ir a 4.
4. Hacer k = k + 1 e ir a 1.
5. Hacer yn = yn−1,
zn = yn−1 + . Si f(yn) ≤ f(zn), tomar an = an−1, bn = zn−1.
Si f(yn) ≥ f(zn), tomar an = yn−1, bn = bn−1.
FINAL. [an, bn] es el intervalo de incertidumbre final.
7 Para un valor de n
suficientemente grande, la proporción Fn−1 Fn tiende al número ´áureo, y por lo
tanto el método de Fibonacci se aproxima al método de la sección ´aurea.
Su algoritmo es
algo complejo, pero cuando se entiende tiene muy buena funcionalidad.
Hasta la próxima.
Comentarios
Publicar un comentario