Instituto de
Estudios
Superiores
Rosario
Castellanos
Estructuras de datos
Docente: Sergio Elías C. Navarro
Alumno: Claudio Cesar Aparicio Feria
Grupo: LAIT3101B1_O_23-1
Foro de reforzamiento.
Métodos de búsqueda y
análisis de algoritmos
Indicaciones:
1. Lee detenidamente el contenido de la unidad.
2. Responde a la siguiente pregunta: En una operación de búsqueda ¡cuál es el
número máximo de comparaciones que requieren los algoritmos de búsqueda
secuencial, binaria y por funciones Hash para examinar una lista no ordenada
completa de n elementos?
El número máximo de comparaciones necesarias para buscar un elemento en
una lista no ordenada de n elementos usando el algoritmo de búsqueda
secuencial es n, ya que se debe comparar cada elemento de la lista hasta
encontrar el elemento buscado o recorrer toda la lista sin éxito.
Por otro lado, el número máximo de comparaciones necesarias para buscar un
elemento en una lista ordenada de n elementos usando el algoritmo de
búsqueda binaria es log2(n) + 1, ya que en cada paso se divide la lista en dos
mitades y se descarta la mitad en la que no se encuentra el elemento buscado.
Finalmente, en el caso de la búsqueda por funciones Hash, el número máximo
de comparaciones depende del factor de carga de la tabla hash, que se refiere
a la proporción de elementos ocupados en relación con el tamaño total de la
tabla. En el mejor de los casos, cuando el factor de carga es bajo, el número de
comparaciones es constante y cercano a 1. Sin embargo, en el peor de los
casos, cuando el factor de carga es alto, todas las claves podrían haber sido
apuntaron a la misma ubicación en la tabla y se requerían n comparaciones
para buscar un elemento.
En resumen, para una lista no ordenada de n elementos, el número máximo de
comparaciones para la búsqueda secuencial es n, para la búsqueda binaria es
log2(n) + 1 y para la búsqueda por funciones hash depende del factor de carga
de la tabla picadillo.
Búsqueda lineal (secuencial)
Consiste en recorrer y examinar cada uno de los elementos del array hasta
encontrar el o los elementos buscados, o hasta que se han mirado todos los
elementos del array.
Este es el método de búsqueda más lento, pero si nuestra información se
encuentra completamente desordenada es el único que nos podrá ayudar a
encontrar el dato que buscamos. El siguiente algoritmo ilustra un esquema de
implementación del algoritmo de búsqueda secuencial:
for(i=j=0;i<N;i++)
if(array[i]==elemento)
{
solucion[j]=i;
j++;
}
Este algoritmo se puede optimizar cuando el array está ordenado, en cuyo caso
la condición de salida cambiaría a:
for(i=j=0;array[i]<=elemento;i++)
o cuando sólo interesa conocer la primera ocurrencia del elemento en el array:
for(i=0;i<N;i++)
if(array[i]==elemento)
break;
En este último caso, cuando sólo interesa la primera posición, se puede utilizar
un centinela, esto es, dar a la posición siguiente al último elemento de array el
valor del elemento, para estar seguro de que se encuentra el elemento, y no
tener que comprobar a cada paso si seguimos buscando dentro de los límites
del array:
array[N]=elemento;
for(i=0;;i++)
if(array[i]==elemento)
break;
Complejidad de la Búsqueda Lineal
(A) MEJOR CASO: El algoritmo de búsqueda lineal termina tan pronto como
encuentra el elemento buscado en el array. Si tenemos suerte, puede ser que
la primera posición examinada contenga el elemento que buscamos, en cuyo
caso el algoritmo informará que tuvo éxito después de una sola comparación.
Por tanto, la complejidad en este caso será O(1).
(B) PEOR CASO: Sucede cuando encontramos X en la última posición del
array. Como se requieren n ejecuciones del bucle mientras, la cantidad de
tiempo es proporcional a la longitud del array n, más un cierto tiempo para
realizar las instrucciones del bucle mientras y para la llamada al método. Por lo
tanto, la cantidad de tiempo es de la forma an + b (instrucciones del mientras *
tamaño del arreglo + llamada al método) para ciertas constantes a y b, que
representan el coste del bucle mientras y el costo de llamar el método
respectivamente. Representando esto en notación O, O(an+b) = O(n).
(C) CASO MEDIO: Supongamos que cada elemento almacenado en el array es
igualmente probable de ser buscado. La media puede calcularse tomando el
tiempo total de encontrar todos los elementos y dividiéndolo por n:
Total = a (1 + 2 + ...+n) + bn = a (n(n+1) / 2) + bn, a representa el costo
constante asociado a la ejecución del ciclo y b el costo constante asociado a la
evaluación de la condición. 1, 2 , ..n, representan el costo de encontrar el
elemento en la primera, segunda, ..., enesima posición dentro del arreglo.
Media = (Total / n) = a((n+1) / 2) + b que es O(n).
Este es el algoritmo de más simple implementación pero no el más efectivo. En
el peor de los casos se recorre el array completo y el valor no se encuentra o
se recorre el array completo si el valor buscado está en la última posición del
array. La ventaja es su implementación sencilla y rápida, la desventaja, su
ineficiencia.
Búsqueda binaria (dicotómica)
Si los elementos sobre los que se realiza la búsqueda están ordenados,
entonces podemos utilizar un algoritmo de búsqueda mucho más rápido que el
secuencial, la búsqueda binaria. El algoritmo consiste en reducir
paulatinamente el ámbito de búsqueda a la mitad de los elementos, basándose
en comparar el elemento a buscar con el elemento que se encuentra en la
mitad del intervalo y en base a esta comparación:
• Si el elemento buscado es menor que el elemento medio, entonces
sabemos que el elemento está en la mitad inferior de la tabla.
• Si es mayor es porque el elemento está en la mitad superior.
• Si es igual se finaliza con éxito la búsqueda ya que se ha encontrado el
elemento.
Se puede aplicar tanto a datos en listas lineales (Vectores, Matrices, etc.) como
en árboles binarios de búsqueda. Los prerrequisitos principales para la
búsqueda binaria son:
• La lista debe estar ordenada en un orden especifíco de acuerdo al valor
de la llave.
• Debe conocerse el número de registros.
La búsqueda binaria consiste en dividir el array por su elemento medio en dos
subarrays más pequeños, y comparar el elemento con el del centro. Si
coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si
está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo,
para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los
siguientes pasos:
Se toma el elemento central y se divide el array en dos:
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el
primer subarray: {1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo
subarray: {3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a
dividir está vacio {}, el elemento no se encuentra en el array. La
implementación sería:
int desde,hasta,medio,elemento,posicion; // desde y hasta indican los límites
del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;)
{
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posicion=desde; // darle el valor.
else // si no es el valor:
posicion=-1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posicion=medio; // ese es la solución
break; // y sale del bucle.
}
else
if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array de la izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
Búsqueda mediante transformación de claves (hash)
Hasta ahora las técnicas de localización de registros vistas, emplean un
proceso de búsqueda que implica cierto tiempo y esfuerzo. El método de
transformación de claves nos permite encontrar directamente el registro
buscado en tablas o archivos que no se encuentran necesariamente
ordenados, en un tiempo independiente de la cantidad de datos.
En los párrafos siguientes se hará referencia a tablas, en lugar de arreglos,
como las estructuras de almacenamiento de la información, pues en general el
método de Hashing se aplica en situaciones que implican el manejo de una
considerable cantidad de información, organizada.
A diferencia de una búsqueda indexada por claves ordinaria, donde usamos el
valor de las claves como índices de un arreglo y necesitamos
indispensablemente que los mismos sean enteros distintos dentro de un rango
equivalente al rango de la tabla, utilizar el método de Hashing nos permite
manejar aplicaciones de búsqueda donde no tenemos claves con
características tan limitadas. El resultado es un método de búsqueda
completamente diferente a los métodos basados en comparaciones, ahora en
vez de navegar por las estructuras comparando palabras clave con las claves
en los items, tratamos de referenciar items en una tabla directamente haciendo
operaciones aritméticas para transformar claves en direcciones de la tabla.
Esto último se logra implementando una Función Hash, que se va a encargar
de dicha transformación.
Idealmente, todas las claves deberían corresponder con direcciones diferentes,
pero es muy frecuente que dos o más claves diferentes sean transformadas a
la misma dirección, cuando esto pasa, se dice que se presenta una Colisión. Es
por eso que también se debe implementar algún proceso de resolución de
Colisiones, que se va a encargar de tratar tales situaciones. Uno de los
métodos de resolución de colisiones que existen usa Listas enlazadas y se lo
denomina “encadenamiento directo” o “Hashing abierto” el cual es muy útil en
situaciones dinámicas, donde el número de elementos es difícil de predecir por
adelantado.
El Hashing es un buen ejemplo de balance entre tiempo y espacio. Si no
hubiera limitaciones de memoria, entonces podríamos hacer cualquier
búsqueda en un solo acceso simplemente utilizando la clave como una
dirección de memoria. Este ideal no puede ser llevado a cabo, porque la
cantidad de memoria requerida es prohibitiva cuando la cantidad de registros
es considerable. De la misma manera, si no hubiese limitación de tiempo,
podríamos usar un menor espacio en memoria usando un método secuencial.
Hashing provee una manera de usar una razonable cantidad de memoria y
tiempo y lograr un balance entre los dos extremos mencionados. En particular,
podemos lograr el balance deseado simplemente ajustando el tamaño de la
tabla, sin necesidad de re-escribir código o cambiar algoritmos.
En líneas generales podemos decir, que es razonable esperar búsquedas
(Search), borrados (Delete) e inserciones (Insert) en tiempo constante,
independientemente del tamaño de la tabla. O sea que es ideal para
aplicaciones que realicen mayoritariamente este tipo de operaciones, por el
otro lado, Hashing no provee implementaciones eficientes para otras
operaciones como por ejemplo Ordenamiento (Sort) o Selección (Select).
Funciones Hash:
La función hash es la que se va a encargar de transformar las claves en
direcciones de la tabla. Se puede definir la “función ideal” como aquella que
distribuya a todos los elementos lo más uniformemente posible sobre la gama
de valores índice, es decir, si tenemos una tabla que puede almacenar N items,
entonces requerimos de una función que transforme claves a enteros en el
rango [0, N-1], que la salida de la función tenga aproximadamente la misma
probabilidad para cada entero, y que la distribución de las claves no esté ligada
a patrón alguno. La función de Hash que se seleccione debe ser calculable de
modo eficiente, es decir, estar compuesta de un número reducido de
operaciones aritméticas básicas.
No hay reglas que permitan determinar cuál será la función más apropiada para
un conjunto de claves, de tal forma que se pueda asegurar una uniformidad
máxima. Hacer un análisis de las características de las claves, puede sin
embargo ayudar en la elección de la función.
La implementación de la función hash depende del tipo de clave. No va a ser la
misma si la clave es un entero, un real o una cadena.
Dentro de las funciones más comunes para la implementación de hashing se
encuentran:
• Función Modulo: Se toma el resto de la división entre la clave y el
número de N de items. Estadísticamente se puede verificar que, para
una mayor uniformidad en la distribución, N debe ser un número primo, o
al menos que sea divisible por pocos números. H(k) = (K mod N).
• Función Cuadrado: Se eleva al cuadrado la clave y se toman los dígitos
centrales como dirección. El número de dígitos a tomar es determinado
por el rango del índice (por ejemplo, si tengo 100 índices, tomo solo 2
dígitos). H(k) = dig_centrales(k^2).
• Sumatoria de valores ASCII: Se toma el resto entre la sumatoria de los
valores ASCII de la cadena de caracteres y el número N (tamaño de la
tabla). Como char es un valor entero que es como mucho 127, para
valores de N grandes, se necesita que las claves sean de una longitud
considerable, de otra manera la distribución no va a ser uniforme.
• Plegamiento: consiste en dividir el número en diferentes partes, y operar
con ellas (normalmente con suma o multiplicación). También se produce
colisión. Por ejemplo, si se dividen los números de 8 cifras en 3, 3 y 2
cifras y se suman, dará otro número de tres cifras (y si no, se cogen las
tres últimas cifras): 13000000 --> 130=130+000+00.
Aunque alguna otra técnica pueda desempeñarse mejor en situaciones
particulares, la técnica del residuo de la división proporciona generalmente la
mejor distribución. Ninguna función hash se desempeña siempre mejor que las
otras.
Referencias:
Cairo, O., Guardati, S. (2006). Estructura de datos. 3° edición. México: Mc.
GrawHill.
Hernández, R., Lázaro, J. C., Dormido, R. y Ros, S. (2001). Estructuras de
datos y algoritmos. Madrid: Pearson Education.
Guardati, S. (2007). Estructura de Datos Orientada a Objetos Algoritmos con
C++. 1° edición. México: Prentice Hall.
Joyanes, L. (2003). Fundamentos de Programación: algoritmos y estructuras
de datos. 3 ed. Madrid: McGraw-Hill.
Joyanes, L. (2000). Programación en C++: algoritmos, estructuras de datos y
objetos. Madrid: McGraw-Hill.
