Изменения

Перейти к: навигация, поиск

Сортировка Хана

11 байт добавлено, 16:13, 21 июня 2012
Нет описания правки
Алгоритм: Пусть целое число <tex>b \ge 0</tex> и пусть <tex>U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хеш функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex>x</tex> из <tex>U: h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex> div </tex> <tex>2^{b - s}</tex>.
Данный алгоритм базируется на лемме №1:
Анонимный участник

Навигация