Busqueda De Datos

Desarrollo

1. Defina con sus propias palabras, qué se entiende por “colisiones” en el tratamiento de los datos mediante Tablas Hash y explique cuáles son las medidas que podemos utilizar para tratarlas.

La función principal en el ordenamiento de un arreglo en ciertos casos debe tener al menos un proceso de orden previo, es decir que los datos recibidos son ordenados por ejemplo:

Si recibimos 5 – 4 – 2 – 3 – 1,

Los algoritmos los ordenan primero quedando de la siguiente forma: 1 – 2 - 3 – 4 – 5,

ahora bien en la tablas hash esto no es necesario ya que lo que este método hace es designarle un índice a cada dato que recibe le entrega un número por orden de llegada, ósea tomando el ejemplo anterior si recibimos 5 – 4 – 2 – 3 – 1, tomara los siguientes índices respectivamente (1) - (2) - (3) - (4) - (5), ahora bien este sistema también tiene problemas y es lo que nos aboca en esta pregunta y es que en muchas ocasiones al entregar los índices puede existir efectos de redundancia, a los que nos referimos “colisión”, para poder tratar con este problema que es inevitable en algunos algoritmos existen tres posibles soluciones:

Opción 1: Sabemos que cuando un índice ya está utilizado por otro elemento en el arreglo al dato se le aplicará el siguiente índice sin utilización que se encuentre, sin embargo un nuevo dato que ingrese puede volver a tener el mismo problema y que se le asigne un índice ya utilizado.

Opción 2: se reservan posiciones al final del arreglo ante posibles colisiones que puedan ocurrir, sin embargo esto genera otra interrogante, pues no sabemos cuántas colisiones tendremos, obviamente si no conocemos la cantidad de datos que en el arreglo ingresaran.

Opción 3: por último tenemos este método que es vez de utilizar arreglos de números, utiliza punteros es uno de los más recomendados por el poco tiempo de búsqueda que demora, lo que realiza es definir si son listas en los índices enlazadas una vez que los datos entran son ingresados al final de los mismos índices para irlos ordenando y los punteros los entregan en el arreglo.

2. Defina con sus propias palabras los siguientes términos e indique brevemente cómo trabajan sus algoritmos básicos. Indique para cada uno de ellos de qué orden es el tiempo de ejecución esperado de dichos algoritmos:

A.- Búsqueda Secuencial: Para este tipo de búsqueda podemos decir que la realiza como su nombre lo indica en forma ordenada desde el primer dato hasta el último, esto solo si es que no encuentra el dato que busca, ahora cuando en algunos casos ocurre que sino solo realizará este procedimiento hasta que encuentre el dato buscado, allí el tiempo de ejecución puede ser O(n2) y O(n).

B.- Búsqueda Binaria: La búsqueda

...