Изменения
автор либо весьма упоролся, либо не знал о \{, \}
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(nlog(logn)n \log\log n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
== Алгоритм ==
== Andersson's exponential search tree ==
Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) Э.П.поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n \log(logn)\log n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(nlog(logn)n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.
==Необходимая информация==
|id=def2.
|definition=
Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, ...\ldots, <tex>m- 1\}</tex> - 1} называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n)).</tex> . Если длина больше, то алгоритм не консервативный.
}}
{{Определение
Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.
Алгоритм: Пусть целое число <tex>b>= 0</tex> >= 0 и пусть <tex>U</tex> = \{0, ...\ldots, <tex>2^b- 1\}</tex> - 1}. Класс <tex>H_{b,s}</tex> хэш функций из <tex>U</tex> в <tex>\{0, ...\ldots, <tex>2^s- 1\}</tex> - 1} определен как <tex>H_{b,s}</tex> = \{<tex>h_{a}</tex>| \mid 0 < <tex>a</tex> < <tex>2^b</tex>, и <tex>a\equiv 1 (\mod 2)\}</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>.
Данный алгоритм базируется на следующей лемме:
