Sinopsis
Los algoritmos de hash codifican datos y crean distribuciones de datos pseudouniformes. Los algoritmos de cubo operan con datos sin transformar sin transformar que se dividen en grupos de acuerdo con la membresía en enredos equl-slzed d-dlmenslonal hyperrec, llamados celdas o cubos. La estructura de datos del bucket es bastante sensible a la distribución de los datos. En estas notas de conferencia, intentamos explicar la conexión entre el tiempo esperado de varios algoritmos de cubo y la des-tribución de los datos. Los resultados se ilustran en problemas estándar de búsqueda, clasificación y selección, así como en una variedad de problemas en geometría computacional e investigación de operaciones. Las notas crecieron parcialmente a partir de un curso de posgrado en teoría de probabilidad en ciencias de la computación. Deseo agradecer a Elizabeth Van Gulick por su ayuda con el manuscrito, y a David Avis, Hanna AYukawa, Vasek Chvatal, Beatrice Devroye, Hossam EI Glndy, Duncan McCallum, Magda McCallum, Godfrled Toussaint y Sue Whltesldes" por hacer que la Escuela de Ciencias de la Computación de la Universidad McGill sea tan placentera. lugar capaz. El trabajo fue apoyado por NSERC Grant A3456 y FCAC Grant EQ-1679. Introducción 1: No es un secreto que los métodos basados en el truncamiento de datos tienen un buen rendimiento de tiempo esperado. Por ejemplo, para una buena distribución de los datos, la búsqueda a menudo se realiza mejor a través de una estructura de datos hash en lugar de a través de un árbol de búsqueda. La velocidad que se observa en la práctica se debe al hecho de que la operación de truncamiento es una operación de tiempo constante.
"Sinopsis" puede pertenecer a otra edición de este libro.