| Metadato | Etiqueta | Valor | Idioma |
|---|---|---|---|
| dc.contributor.author | Autor | Martínez, Conrado | es |
| dc.contributor.author | Autor | Panario, Daniel | es |
| dc.contributor.author | Autor | Viola, Alfredo | es |
| dc.date.accessioned | Fecha ingreso | 2014-12-02T16:07:08Z | - |
| dc.date.available | Fecha disponible | 2014-12-02T16:07:08Z | - |
| dc.date.issued | Año de publicación | 2004 | es |
| dc.date.submitted | Fecha de subida | 20141202 | es |
| dc.description.abstract | 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. | es |
| dc.format.extent | Extensión | 43 p. | es |
| dc.format.mimetype | Formato | application/pdf | es |
| dc.identifier.citation | Citación | MARTÍNEZ, C., PANARIO, D., VIOLA, A. "Adaptative sampling strategies for Quickselect". Reportes Técnicos 04-14. UR. FI – INCO, 2004. | es |
| dc.identifier.issn | ISSN | 0797-6410 | es |
| dc.identifier.uri | URI | http://hdl.handle.net/20.500.12008/3505 | - |
| dc.language | metadata.dc.language | in | es |
| dc.publisher | Editorial | UR. FI – INCO. | es |
| dc.relation.ispartof | EN | Reportes Técnicos 04-14 | es |
| dc.rights | Derechos | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad De La República. (Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | es |
| dc.rights.licence | Licencia | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) | es |
| dc.title | Título | Adaptative sampling strategies for Quickselect | es |
| dc.type | Tipo de documento | Reporte técnico | es |
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| TR0414.pdf | — | 849.15 KB | Adobe PDF |