Hashing y Recursión dentro de Algoritmos

Hashing y Recursión dentro de Algoritmos

.

Análisis de Algoritmos

Instituto IACC

12/01/2019

DESARROLLO

PREGUNTAS:

Suponga que tiene un conjunto de animales, donde estos se distribuyen uniformemente entre animales acuáticos, animales terrestres y animales aéreos (con la misma cantidad de animales de cada tipo):

a) ¿Cómo se clasificarían dentro de un hash?

b) ¿Usaría un hash simple o uno encadenado?

c) ¿Cómo sería su función de hash?

d) ¿Cuánto demoraría una búsqueda en su estructura?

Escriba en pseudocódigo el algoritmo de búsqueda binaria de forma recursiva.

1.-

A) Para la clasificación dentro de un hash, se propone que el array donde guardemos la información  sea  un array de punteros hacia listas enlazadas.

B) En este caso, y según las condiciones planteadas, se usaría un hash encadenado, dado que este corresponde a una de las técnicas existentes para la solución de las colisiones dentro de las tablas de hash. Estas colisiones se producen cuando la función de hash retorna el mismo valor para dos datos distintos. Cuando esto pasa y se está utilizando un hash encadenado, el nuevo elemento se encola después del elemento que ya existe en la posición del hash.

Esta técnica, si bien es cierto que aumenta la complejidad en la búsqueda de elementos, incluso esa complejidad sigue siendo menor que almacenar todos los elementos en una lista enlazada: si el peor caso de búsqueda de un elemento en un conjunto desordenado de tamaño n hace que demore O(n), para que un hash encadenado demore lo mismo, la función de hash debiera retornar siempre el mismo índice, lo cual violaría la regla de las funciones de hash que dice que los elementos deben estar uniformemente distribuidos dentro del conjunto.

C) El hashing consta de una función de hash, llamada h(x), que puede ser definida de forma arbitraria, pero debe utilizarse la misma para la construcción de todo el hash. Para el problema señalado se tomará la segunda letra del nombre y se pondrá en la posición que le corresponde del alfabeto.

D)Un caso promedio de hash encadenado siempre es el cálculo de la función de hash para ubicarse en la lista correcta, que demora O(1) más el caso que el elemento buscado sea el último de la lista para ese espacio del hash. Como es búsqueda secuencial, esto demoraría O(k), donde k es un número mucho menor a n, ya que el conjunto de los elementos de la lista es un subconjunto del conjunto de elementos totales.