81
правка
Изменения
Нет описания правки
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку - уменьшить число бит в числе. Один из способов уменьшить число бит в числе - использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.
Алгоритм: Пусть целое число <tex>b</tex> >= 0 и пусть <tex>U</tex> = {0, ..., <tex>2^b</tex> - 1}. Класс <tex>H_{b,s}</tex> хэш функций из <tex>U</tex> в {0, ..., <tex>2^s</tex> - 1} определен как <tex>H_{b,s}</tex> = {<tex>h_{a}</tex>| 0 < <tex>a</tex> < <tex>2^b</tex>, и <tex>a</tex> нечетно} и для всех <tex>x</tex> из <tex>U</tex>: <tex>h_{a}(x) = (ax</tex> mod <tex>2^b</tex><tex>)</tex> div <tex>2^{b - s}</tex>
Данный алгоритм базируется на следующей лемме:
{{Лемма
|id=lemma1.
|statement=
Даны целые числа <tex>b</tex> >= <tex>s</tex> >= 0 и <tex>T</tex> является подмножеством {0, ..., <tex>2^b</tex> - 1}, содержащим <tex>n</tex> элементов, и <tex>t</tex> >= <tex>2^{-s + 1}</tex><tex>С^n_{k}</tex>
|proof=доказательство (необязательно)
}}