Algoritmos de Búsqueda

1

Nombre Alumno: Daniel ArroyoManuel Díaz

Cristian Fuentealba.Damary Paquien.

Nombre Profesor: Pilar pardo.

Fecha: 16 de Abril de 2014

Análisis de Algoritmos

INDICE

ContenidoINDICE................................................................................................................................................2

INTRODUCCIÓN..................................................................................................................................3

BÚSQUEDA LINEAL.............................................................................................................................4

BÚSQUEDA BINARIA...........................................................................................................................6

BÚSQUEDA POR TRANSFORMACIÓN DE CLAVES (HASHING).............................................................8

TRUNCAMIENTO..........................................................................................................................10

PLEGAMIENTO..............................................................................................................................11

ARITMÉTICA MODULAR................................................................................................................12

MITAD DEL CUADRADO................................................................................................................13

CONCLUSIÓN....................................................................................................................................14

2

INTRODUCCIÓNEn este trabajo se darán a conocer los diferentes algoritmos de búsqueda, los cuales se caracterizan por estar diseñados para localizar un elemento con ciertas propiedades dentro de una estructura de datos.

Dentro de los algoritmos de búsqueda se encuentran:

Búsqueda lineal.

Búsqueda binaria.

Búsqueda por Transformación de claves (hashing).

Se conocerá las características particulares de cada uno y las diferentes técnicas de la transformación de claves (hash) entre las que podemos destacar:

Truncamiento.

Plegamiento.

Aritmética modular.

Mitad del cuadrado.

3

BÚSQUEDA LINEALEsta búsqueda se centra en recorrer un vector, comparando el contenido del vector con el elemento que se desea buscar un tras otro hasta llegar al final del vector.

En esta búsqueda existen dos posibles resultados al aplicar este algoritmo:

a.- La posición en la que se encontró el elemento.

b.- Un mensaje de fracaso si el elemento no fue hallado.

Entonces este algoritmo tiene una complejidad de O(n).

Mejor caso: Es cuando se encuentra el elemento en el primer intento.

Peor caso: Es cuando la búsqueda ha comparado todos los campos con el elemento buscado.

Caso promedio: Es cuando la búsqueda ha encontrado el elemento en una posición no mayor a la mitad del vector.

Ventajas:

Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar.

La ventaja real del método secuencial indexado es que los elementos en la tabla pueden ser examinados en forma secuencial si todos los registros en el archivo deben ser accesados, pero sin embargo, el tiempo de búsqueda para algún elemento en particular se reduce considerablemente. La búsqueda secuencial se realiza en la tabla de índices que es más pequeña en lugar de la tabla más grande. Una vez que se ha encontrado un índice correcto, se hace una segunda búsqueda secuencial únicamente en la parte reducida de la tabla que contiene los registros.

La organización secuencial indexado es conveniente para archivos con mediana volatilidad, actividad variable y tamaño relativamente estable.

Las eliminaciones de una tabla secuencial indexada se pueden hacer fácilmente mediante la asignación de banderas a las entradas que son eliminadas. Durante la búsqueda secuencial a través de la tabla, se ignoran las entradas que han sido eliminadas.

Desventajas:

Pero implica un aumento en la cantidad de espacio requerida, porque se ocupa un índice y “se pone a un lado además del fichero clasificado a sí mismo”.

La inserción en una tabla secuencial indexada es un poco más difícil debido a que puede que no exista espacio entre dos entradas en la tabla, siendo necesario mover un gran número de elementos en la tabla.

El uso de una lista ligada (índice) da una gran sobrecarga de espacio y tiempo para los apuntadores que se utilizan en la búsqueda de registros.

4

Los registros deben ser de longitud fija. El archivo debe estar soportado por una memoria de masa tal como el disco; no se utiliza en cinta magnética. A veces todo el archivo debe estar presente en línea.

Principales Aplicaciones.

Un uso en la cual esta búsqueda se aplica, es donde se presenta el ingreso de datos (registros) sin ningún tipo de orden especifico; pero en cada determinado momento su campo llave es almacenado en un índice, en el cual esas llaves están ordenadas de menor a mayor o de mayor a menor dependiendo el uso que se le de. De esta manera, para agilizar la búsqueda de un registro en particular se accesa a ese registro por medio de su campo llave almacenado en el índice.

Un ejemplo de nuestra vida diaria y donde se aplica esta búsqueda es en un negocio mediano (negocio de carnes frías , refaccionaria), ya que aquí se necesita una búsqueda eficiente con una sola clave de acceso y otorgándonos la información requerida.

5

BÚSQUEDA BINARIAEsta búsqueda al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás, unos de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado.

No se puede utilizar con listas simplemente ligadas (no se podría retroceder para establecer intervalos de búsqueda) ni con arreglos desordenados.

En esta búsqueda el número de comparaciones a realizar disminuye notablemente por cada iteración.

El algoritmo de búsqueda binaria tiene una complejidad de O(log n).

Mejor caso: Es cuando el elemento buscado es el central del arreglo.

Peor caso: Que el elemento buscado sea la última comparación que realiza la operación o simplemente no esté en el arreglo.

Ventajas:

La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.

La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.

Es más rápido por su recursividad, su mayor ventaja es con los archivos extensos.

El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de búsqueda.

En esencia, con una sola comparación eliminamos la mitad de la tabla; este es el método mas eficiente de buscar en una lista ordenada sin emplear tablas o índices adicionales.

Desventajas:

La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:

El archivo debe estar ordenado y el almacenamiento de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.

No revisa todos los elementos del archivo, requiere que todos los elementos estén ordenados

Esta búsqueda más de uno o dos accesos si el archivo es enorme; y mantener ese archivo ordenado es muy costoso.

6

Principales Aplicaciones.

Ejemplo: Árbol Binario de Búsqueda:

Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol.

Solución:

Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas).

La combinación de resultados es trivial: la solución del subproblema es también la del problema global.

7

BÚSQUEDA POR TRANSFORMACIÓN DE CLAVES (HASHING)

El método consiste en aplicar una función que traduce un conjunto de posibles valores llaves en un rango de direcciones relativas.

Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un registro, archivo, documentó, etc.

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales).

Ventajas:

1. Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar2. Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones3. No se requiere almacenamiento adicional para los índices.

Desventajas:

1. No pueden usarse registros de longitud variable2. El archivo no está clasificado3. No permite llaves repetidas4. Solo permite acceso por una sola llave

Costos

-Tiempo de procesamiento requerido para la aplicación de la función hash-Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

La eficiencia de una función hash depende de:

1. La distribución de los valores de llave que realmente se usan2. El número de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones3. El número de registros que pueden almacenarse en una dirección dad sin causar una colisión

8

4. La técnica usada para resolver el problema de las colisiones

9

Una de las principales desventajas de hashing es que el conjunto de posibles claves siempre es mayor a las posiciones que disponemos para guardarlas, cuando 2 claves se les asigna el mismo índice se produce una colisión.

La eficiencia del algoritmo dependerá del número de colisiones que se produzcan teniendo:

El mejor caso: que no se produzca ninguna colisión.

El caso promedio: en el cual se producen algunas colisiones.

El peor caso, donde todas las claves colisionan.

10

Existen numerosos métodos de transformación de claves:

TRUNCAMIENTO

La función hash por truncamiento consiste en tomar parte de la clave que se desea encontrar el índice e ignorar el resto, es así como de una clave grande se obtiene una más pequeña que corresponde al índice, considerando campos no numéricos y sus códigos numéricos.

Ejemplo.

Si se tiene una Clave de 9 dígitos y la tabla de transformación posee solo mil posiciones, para el índice se considera el primer, segundo y quinto dígito formando así la función.

Clave: 91521697 → h(clave) = 911

El truncamiento es un método muy rápido, pero tiene el problema de que no es capaz de distribuir las claves de manera uniforme.

11

PLEGAMIENTO

La función hash por plegamiento consiste en cortar la clave en partes iguales, con excepto la última que puede ser distinta, y aplicar una operación matemática entre ellas, esto puede ser suma o multiplicación. El resultado de esta operación será el índice que ocupara la clave en el arreglo.

Si el índice obtenido esta fuera de rango, este se debe truncar para obtener la dirección definitiva.

Ejemplo.

El número de socio de un club deportivo consta de cuatro dígitos y las direcciones reales son 100. Se desea calcular las direcciones correspondientes por el método de plegamiento.

Claves: 4270, 7021, 1643

Para Fórmula Resultado

4270 = 42 + 70 = 112 12*

7021 = 70 + 21 = 91 91

1643 = 16 + 43 = 59 59

*En el primer caso el índice resultante excede a las direcciones disponibles, por lo cual es necesario truncar.

H(4270) = 12

En general el hashing por plegamiento es el método más simple de utilizar, sin embargo dependiendo de la longitud de la clave puede producir resultados erráticos.

12

ARITMÉTICA MODULAREste tipo de transformación de claves (hash), consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo.

La función hash se define con la siguiente formula:

H(K) = (K mod N) + 1

En este tipo de transformación de claves (hash), se recomienda el uso de un numero primo inmediato o menor al número total de elementos del arreglo.

Si tenemos un arreglo de 100 elementos y las direcciones que se deben asignar a los elementos son del 1 al 100, si consideramos dos claves a las que se deben asignar posiciones en el arreglo con diferentes claves K= (7259 y 9359). Y aplicando la formula anterior con N = 100.

a.- H(K) = (7259 mod 100) + 1 = 60

b.- H(K) = (9359 mod 100) + 1 = 60

Como (a) y (b) tienen el mismo resultado, y K diferentes cifras, se está ante una colisión que se debe resolver porque a los dos elementos le corresponde la misma dirección.

Pero si aplicáramos la formula con un número primo más cercano a N, el resultado cambiaria.

a.- H(K) = (7259 mod 97) + 1 = 82

b.- H(K) = (9359 mod 97) + 1 = 48

Con el cambio de N a 97 se a resuelto la colisión de las direcciones dentro del arreglo.

13

MITAD DEL CUADRADO

Consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El número de dígitos a tomar queda determinado por el rango del índice. Sea K la clave del dato a buscar. La función hash queda definida por la siguiente fórmula: H(K)= c donde c se forma por los dígitos de k2 que están en las posiciones p1, p2,...pi.

Ejemplo:

En un curso el archivo de alumnos con el campo clave de 6 dígitos, se escogen los dígitos 4to, 5to y 6to por la derecha

A continuación:

Para Fórmula Resultado

245643 = h(245643)2=60340483449 483

245981 = h(245981)2=60506652361 652

257135 = h(257135)2=66118408225 408

14

CONCLUSIÓNDe la presente investigación se puede concluir que existen variados algoritmos de búsqueda, los cuales presentan distintos niveles de complejidad y eficiencia, al hacer una comparación entre estos, se puede apreciar que todos presentan ventajas y desventajas propias. Es así como para elegir el mejor algoritmo de búsqueda se deben considerar diversos factores, ya que va a depender el tipo de clave de que se trate, cual tendrá mejores resultados.

Dentro del algoritmo de búsqueda por claves (hashing), existen diversos métodos que podemos utilizar, y si bien hay algunos más simples que otros, no se puede determinar el mejor, ya que, en el global son todos relativamente iguales, y van a presentar mejor o peor rendimiento dependiendo para que se utilicen.

Cuadro Comparativo

ALGORITMO VENTAJAS DESVENTAJAS

BÚSQUEDA LINEAL Pude llegar a encontrar el buscado al primer intento sin necesidad de procesos previos.

Puede tener que recorrer todo el vector para ejecutar la búsqueda

BÚSQUEDA BINARIA Es el más eficiente si el vector esta ordenado

El Vector necesita estar ordenado

BÚSQUEDA POR TRANSFORMACIÓN DE CLAVES (HASHING)

No necesita estar ordenador Su eficiencia dependerá de cómo se resuelven las colisiones

15