Изменения
Нет описания правки
|definition=
Для множества <tex>S</tex> определим
min(<tex>S</tex>) = min(<tex>a</tex>:<tex>a</tex> принадлежит <tex>aS</tex>) max(<tex>S</tex>) = max(<tex>a</tex>:<tex>a</tex> принадлежит <tex>aS</tex>)
Набор <tex>S1</tex> < <tex>S2</tex> если max(<tex>S1</tex>) <= min(<tex>S2</tex>)
}}
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку - уменьшить число бит в числе. Один из способов уменьшить число бит в числе - использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется хэш функция авторства: Dierzfelbinger и Raman.
