Название: Lecture Notes on Bucket Algorithms
Автор: DEVROYE
Издательство: Birkhauser
Год: 1986
Формат: pdf
Страниц: 150
Размер: 15,83 Мб
Язык: английский

Hashing algorithms scramble data and create pseudo-uniform data distribu­ tions. Bucket algorithms operate on raw untransformed data which are parti­ tioned Into groups according to membership In equl-slzed d-dlmenslonal hyperrec­ tangles, called cells or buckets. The bucket data structure Is rather sensitive to the distribution of the data. In these lecture notes, we attempt to explain the connection between the expected time of various bucket algorithms and the dis­ tribution of the data. The results are Illustrated on standard searching, sorting and selection problems, as well as on a variety of problems In computational geometry and operations research.