Algorimos de Busqueda (Interpolation Search, Extrapolation Search)
Jérémy Barbay 21 Sep 201021/09/10 a las 14:04 hrs.2010-09-21 14:04:21
Algorimos de Busqueda (Interpolation Search, Extrapolation Search)
==================================================================
1) Interpolacion
1. Introduccion:
- Hagaria busqueda binaria en un anuario telefonico para
el nombre "Barbay"? En un diccionario para la ciudad
"Zanzibar"?
- ojala que no: se puede provechar de la informacion
que da la primera letra de cada palabra
2. Algoritmo
- Interaccion
3. Analisis
* La analisis *en promedio* es complicada: conversamos
solamente la intuicion matematica (para mas ver la
publicacion cientifica de SODA04, Demaine Jones y
Patrascu):
- si las llaves son *distribuidas uniformamente*, la
distancia en promedio de la posicion calculada por
interpolacion *lineal* hasta la posicion real es de
$\sqrt{r-l}$.
- entonces, se puede reducir el tamaño del subarreglo
de $n$ a $\sqrt{n}$ cada (dos) comparaciones
- la busqueda por interpolacion
- en promedio,
- si las llaves son *distribuidas uniformamente*,
- toma $O(\lg \lg n)$ comparaciones
* La analisis *en el peor caso*
- Interaccion.
4. Variantas
1. Interpolacion non-lineal
- en un anuario telefonico o en un diccionario, las
frecuencias de las letras *no* son uniformes
2. Busqueda por Interpolacion Mixta con Binaria
- Se puede buscar en tiempo
- $O(\lg n)$ en el peor caso Y
- $O(\lg \lg n)$ en el caso promedio?
- Solucion facil
- Solucion mas compleja
3. Busqueda por Extrapolacion
- Tarea 3
4. Busqueda por Extrapolacion Mixta con Doblada
- Tarea 3
3) Discussion:
- Porque todavia estudiar la complejidad en el modelo de comparaciones?
- Cuando el peor caso es importante
- Cuando la distribucion no es uniforme o no es conocida
- cuando el costo de la evaluacion es mas costo que una
simple comparacion (en particular para la interpolacion
non lineal)
==================================================================
1) Interpolacion
1. Introduccion:
- Hagaria busqueda binaria en un anuario telefonico para
el nombre "Barbay"? En un diccionario para la ciudad
"Zanzibar"?
- ojala que no: se puede provechar de la informacion
que da la primera letra de cada palabra
2. Algoritmo
- Interaccion
3. Analisis
* La analisis *en promedio* es complicada: conversamos
solamente la intuicion matematica (para mas ver la
publicacion cientifica de SODA04, Demaine Jones y
Patrascu):
- si las llaves son *distribuidas uniformamente*, la
distancia en promedio de la posicion calculada por
interpolacion *lineal* hasta la posicion real es de
$\sqrt{r-l}$.
- entonces, se puede reducir el tamaño del subarreglo
de $n$ a $\sqrt{n}$ cada (dos) comparaciones
- la busqueda por interpolacion
- en promedio,
- si las llaves son *distribuidas uniformamente*,
- toma $O(\lg \lg n)$ comparaciones
* La analisis *en el peor caso*
- Interaccion.
4. Variantas
1. Interpolacion non-lineal
- en un anuario telefonico o en un diccionario, las
frecuencias de las letras *no* son uniformes
2. Busqueda por Interpolacion Mixta con Binaria
- Se puede buscar en tiempo
- $O(\lg n)$ en el peor caso Y
- $O(\lg \lg n)$ en el caso promedio?
- Solucion facil
- Solucion mas compleja
3. Busqueda por Extrapolacion
- Tarea 3
4. Busqueda por Extrapolacion Mixta con Doblada
- Tarea 3
3) Discussion:
- Porque todavia estudiar la complejidad en el modelo de comparaciones?
- Cuando el peor caso es importante
- Cuando la distribucion no es uniforme o no es conocida
- cuando el costo de la evaluacion es mas costo que una
simple comparacion (en particular para la interpolacion
non lineal)
| Compartir | |
|---|---|
| Última Modificación | 21 Sep 201021/09/10 a las 14:04 hrs.2010-09-21 14:04:21 |
| Vistas Únicas | 0 |
