Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 39: Строка 39:
 
}}
 
}}
  
Взяв <tex>s = 2logn</tex> мы получим хэш функцию <tex>h_{a}</tex> которая захэширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить <tex>h_{a}</tex> ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только mod<tex>2^b</tex> и div<tex>2^{b - s}</tex>.
+
Взяв <tex>s = 2logn</tex> мы получим хэш функцию <tex>h_{a}</tex> которая захэширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить <tex>h_{a}</tex> ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod <tex>2^b</tex>) и (div <tex>2^{b - s}</tex>).
 +
 
 +
Такая хэш функция может быть найдена за <tex>О(n^3)</tex>.
 +
 
 +
Следует отметить, что несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex> потому, что хэштрование используется только для уменьшения количества бит в числе.

Версия 23:24, 10 июня 2012

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(nlog(logn))[/math], где [math]n[/math] — количество элементов для сортировки.

Алгоритм

Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.

Andersson's exponential search tree

Э.П.дерево с [math]n[/math] листьями состоит из корня [math]r[/math] и [math]n^e[/math] (0<[math]e[/math]<1) Э.П.поддеревьев, в каждом из которых [math]n^{1 - e}[/math] листьев; каждое Э.П.поддерево является сыном корня [math]r[/math]. В этом дереве [math]O(log(logn))[/math] уровней. При нарушении баланса дерева, необходимо балансирование, которое требует [math]O(nlog(logn))[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.

Необходимая информация

Определение:
Контейнер - объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.


Определение:
Алгоритм сортирующий [math]n[/math] целых чисел из множества {0, 1, ..., [math]m[/math] - 1} называется консервативным, если длина контейнера (число бит в контейнере), является [math]O(log(m + n)).[/math] Если длина больше, то алгоритм не консервативный.


Определение:
Для множества [math]S[/math] определим

min([math]S[/math]) = min([math]a[/math]:[math]a[/math] принадлежит [math]S[/math]) max([math]S[/math]) = max([math]a[/math]:[math]a[/math] принадлежит [math]S[/math])

Набор [math]S1[/math] < [math]S2[/math] если max([math]S1[/math]) <= min([math]S2[/math])


Уменьшение числа бит в числах

Один из способов ускорить сортировку - уменьшить число бит в числе. Один из способов уменьшить число бит в числе - использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий [math]O(m)[/math] памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до [math]O(n)[/math]. Для того, чтобы еще ускорить алгоритм нам необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хэширование для всех чисел хранимых в контейнере. Для этого используется хэш функция для хэширования [math]n[/math] чисел в таблицу размера [math]O(n^2)[/math] за константное время, без коллизий. Для этого используется хэш модифицированная функция авторства: Dierzfelbinger и Raman.

Алгоритм: Пусть целое число [math]b[/math] >= 0 и пусть [math]U[/math] = {0, ..., [math]2^b[/math] - 1}. Класс [math]H_{b,s}[/math] хэш функций из [math]U[/math] в {0, ..., [math]2^s[/math] - 1} определен как [math]H_{b,s}[/math] = {[math]h_{a}[/math]| 0 < [math]a[/math] < [math]2^b[/math], и [math]a[/math] нечетно} и для всех [math]x[/math] из [math]U[/math]: [math]h_{a}(x) = (ax[/math] mod [math]2^b[/math][math])[/math] div [math]2^{b - s}[/math]

Данный алгоритм базируется на следующей лемме:

Лемма:
Даны целые числа [math]b[/math] >= [math]s[/math] >= 0 и [math]T[/math] является подмножеством {0, ..., [math]2^b[/math] - 1}, содержащим [math]n[/math] элементов, и [math]t[/math] >= [math]2^{-s + 1}[/math]С[math]^n_{k}[/math]. Функция [math]h_{a}[/math] принадлежащая [math]H_{b,s}[/math] может быть выбрана за время [math]O(bn^2)[/math] так, что количество коллизий [math]coll(h_{a}, T) \lt = t[/math]

Взяв [math]s = 2logn[/math] мы получим хэш функцию [math]h_{a}[/math] которая захэширует [math]n[/math] чисел из [math]U[/math] в таблицу размера [math]O(n^2)[/math] без коллизий. Очевидно, что [math]h_{a}(x)[/math] может быть посчитана для любого [math]x[/math] за константное время. Если мы упакуем несколько чисел в один контейнер так, что они разделены несколькими битами нулей, мы спокойно сможем применить [math]h_{a}[/math] ко всему контейнеру, а в результате все хэш значения для всех чисел в контейере были посчитаны. Заметим, что это возможно только потому, что в вычисление хэш знчения вовлечены только (mod [math]2^b[/math]) и (div [math]2^{b - s}[/math]).

Такая хэш функция может быть найдена за [math]О(n^3)[/math].

Следует отметить, что несмотря на размер таблицы [math]O(n^2)[/math], потребность в памяти не превышает [math]O(n)[/math] потому, что хэштрование используется только для уменьшения количества бит в числе.