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, ..., 2^<tex>b</tex> - 1}. Класс H_{b,s} хэш функций из <tex>U</tex> в {0, ..., 2^<tex>s</tex> - 1} определен как H_{b,s} = {<tex>h_{a}</tex>| 0 < <tex>a</tex> < 2^<tex>b</tex>, и <tex>a</tex> нечетно} и для всех <tex>x</tex> из <tex>U</tex>: <tex>h_{a}(x) = (ax </tex> mod 2^<tex>b</tex>) div 2^{b - s}</tex>
