Título:
Adaptative sampling strategies for Quickselect
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Martínez, Conrado
Panario, Daniel
Viola, Alfredo
Panario, Daniel
Viola, Alfredo
Tutor:
Tipo de documento:
Reporte técnico
Editor:
Palabras clave:
Descriptores:
Año de publicación:
2004
Contenido:
Resumen:
Quickselect con median-of-3 es usado ampliamente en la práctica y su comportamiento bastante bien comprendido. Sin embargo, la siguiente variante adaptativa, que llamamos proportion-from-3, no ha sido analizada previamente: "elegir como pivot el elemento más pequeño de la muestra si el rango relativo del elemento buscado está por abajo de 1/3; elegir el más grande si el rango relativo está por encima de 2/3; y elegir el mediano si el rango relativo está entre 1/3 y 2/3". Analizamos primero el número promedio de comparaciones realizadas al usar proportion-from-2 y luego al usar proportion-from-3. También analizamos nu-find, una generalización de proportion-from-3 con extremos de intervalo en los valores nu y 1-nu. Mostramos que existe un valor óptimo de nu y damos el rango de valores de nu en los que la estrategia nu-find supera a median-of-3. Luego, consideramos el costo total promedio de estas estrategias, teniendo en cuenta tanto el costo de las comparaciones como de los intercambios. Nuestros resultados apuntan fuertemente a que una implementación apropiada de nu-find podría ser el método preferible en un entorno práctico. También estudiamos el comportamiento de proportion-from-s con s ] 3 y en particular mostramos que estrategias del estilo proportion-from-s son óptimas cuando s tiende a infinito.
Descripción:
Editorial:
UR. FI – INCO.
EN:
Reportes Técnicos 04-14
Financiadores:
Citación:
MARTÍNEZ, C., PANARIO, D., VIOLA, A. "Adaptative sampling strategies for Quickselect". Reportes Técnicos 04-14. UR. FI – INCO, 2004.
Citación:
metadata.cc.license.name:
Documento del Gobiberno:
URI:
http://hdl.handle.net/20.500.12008/3505
ISBN:
e-ISBN:
ISSN:
0797-6410
ISMN:
Otros identificadores:
Título Obtenido:
Facultad o Servicio que otorga el Título:
Licencia:
Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0)
Cobertura geográfica:
Cobertura temporal:
metadata.dc.relation.IsVersionOf:
Clasificación:
Es versión de:
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| TR0414.pdf | — | 849.15 KB | Adobe PDF |