Изменения

Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0, и <tex>T</tex> является подмножеством множества <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <tex>h_{a}</tex>, принадлежащая <tex>H_{b,s}</tex>, может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T)</tex> <tex>\le</tex> <tex>t</tex>.

<tex>n</tex> целых чисел можно отсортировать в <tex>\sqrt{n}</tex> наборов <tex>S_{1}</tex>, <tex>S_{2}</tex>, <tex>\ldots</tex>, <tex>S_{\sqrt{n}}</tex> таким образом, что в каждом наборе <tex>\sqrt{n}</tex> чисел и <tex>S_{i}</tex> < <tex>S_{j}</tex> при <tex>i</tex> < <tex>j</tex>, за время <tex>O(n \log\log n/ \log k)</tex> и место <tex>O(n)</tex> с не консервативным неконсервативным преимуществом <tex>k \log\log n</tex>.

Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов, как в '''лемме №2'''. ПредполагаяПредполагаем, что в каждом контейнере каждый контейнер содержит <tex>k \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <tex>k \log \log n</tex>. Так же Также предполагаем, что <tex>\log m \ge \log n \log\log n</tex>. Иначе можно использовать radix sort для сортировки за время <tex>O(n \log\log n)</tex> и линейную память. Делим <tex>\log m</tex> бит, используемых для представления каждого числа, в <tex>\log n</tex> блоков. Таким образом , каждый блок содержит как минимум <tex>\log\log n</tex> бит. <tex>i</tex>-ый блок содержит с <tex>i \log m/ \log n</tex>-ого по <tex>((i + 1) \log m/ \log n - 1)</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом:

На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.) , потому, что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самыми самым большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованных упакованными в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считаетсясчитаем, что она бесплатна. По '''лемме №3''' находим медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/ \log n)</tex>. Пусть <tex>a</tex> {{---}} это найденная медиана. Тогда <tex>n</tex> м.ч. могут быть разделены на не более чем три группы: <tex>S_{1}</tex>, <tex>S_{2}</tex> и <tex>S_{3}</tex>. <tex>S_{1}</tex> содержит м.ч. , которые меньше <tex>a</tex>, <tex>S_{2}</tex> содержит м.ч. , равные <tex>a</tex>, <tex>S_{3}</tex> содержит м.ч. , большие <tex>a</tex>. Так же Также мощность <tex>S_{1}</tex> и <tex>S_{3} </tex> {{---}} не превосходит <tex>n/2</tex>. Мощность <tex>S_{2}</tex> может быть любой. Пусть <tex>S'_{2}</tex> {{---}} это набор чисел, у которых наибольший блок находится в <tex>S_{2}</tex>. Тогда убираем из дальнейшего рассмотрения <tex>\log m/ \log n</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex>S'_{2}</tex>, из дальнейшего рассмотрения. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>\log n</tex> блоков, для каждого числа потребуется не более <tex>\log n</tex> стадий, чтобы поместить его в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex>n/ \log n</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex>O(n)</tex> времени из-за <tex>2 \log n</tex> стадий.

Сложная часть алгоритма заключается в том, как поместить маленькие числа м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать используем '''лемму №6'''. Полный размер маркера для каждого контейнера должен быть <tex>\log n/2</tex>, и маркер использует <tex>\log e</tex> бит, значит количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\log n/(2\log e)</tex>. В дальнейшем т.к. , так как <tex>g = \log n/(2 \log e)</tex> , м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex>O(k \log n/g) = O(k \log e)</tex> блоков. Заметим, что используем используется неконсервативное преимущество в <tex>\log\log n</tex> для использования '''леммы №6'''. Поэтому предполагается, что <tex>\log n/(2 \log e)</tex> м.ч. , в каждом из которых <tex>k \log e</tex> блоков битов числа упакованный , упакованны в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит, который показывает , к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры , как и м.ч. Так как каждый контейнер для маркеров содержит <tex>\log n/(2 \log e)</tex> маркеров, то для каждого контейнера требуется <tex>(\log n)/2</tex> бит. Таким образом, '''лемма №6''' может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров , то время , необходимое для помещения м.ч. в их наборы потребуется , равно <tex>O((n \log e)/ \log n)</tex> времени.

Рассмотрим число <tex>a</tex>, которое является <tex>i</tex>-ым в наборе <tex>S</tex>. Рассмотрим блок <tex>a</tex> (назовем его <tex>a'</tex>), который является <tex>i</tex>-ым м.ч. в <tex>S</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков <tex>a</tex> (назовем это <tex>a''</tex>) в <tex>S</tex>, <tex>a''</tex> просто перемещен на позицию в наборе <tex>S</tex>, но не обязательно на позицию <tex>i</tex> (где расположен <tex>a'</tex>). Если значение блока <tex>a'</tex> одинаково для всех чисел в <tex>S</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в <tex>S</tex> помещен <tex>a''</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, помещаются последующие блоки помещаются в набор вместе с текущим блоком в набор. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди <tex>k \log e</tex> блоков {{---}} это текущий блок. Таким образом, после того, как помещены эти <tex>k \log e</tex> блоков помещены в набор, удаляется изначальный текущий блокудаляется, потому, что известно, что эти <tex>k \log e</tex> блоков перемещены в правильный набор , и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных <tex>k \log e</tex> блоках.

Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. '''Леммы №4, №5, №6''' расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем быть не должно быть.

<tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.

# Если <tex>if (level == 1)</tex> тогда изучить изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе разделить делим этот набор в <tex>\le</tex> 3 набора , используя '''лемму №3''', чтобы найти медиану, а затем использовать используем '''лемму №6''' для сортировки. Для набора, где все элементы равны медиане, не рассматривать рассматриваем текущий блок и текущим блоком сделать делаем следующий. Создать Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направьте направляем двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>.

## Упаковать Упаковываем <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где . Где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{i}</tex> и . При этом у которого <tex>a^{(u)}_{i}</tex> текущий блок это самый крупный блок.## Вызвать Вызываем Sort(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к которому какому набору это число относится, уже отправлен направлен назад к месту , где число находится во входных данных. Число, имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на ткущий текущий блок в нем, так же отправлено направлено назад к <tex>a_{i}</tex>.## Отправить Отправляем <tex>a_{i}</tex>-ые к их наборам, используя '''лемму №6'''.</tex>

endКонец.

# Поместить Помещаем <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort , потому, что наборов около <tex>\sqrt{n}</tex>.# Для каждого набора <tex>S = </tex>{<tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>}, если <tex>t > \sqrt{n}</tex>, вызвать вызываем Sort(<tex>k \log\log n</tex>, <tex>\log_{k}((\log n)/4)</tex>, <tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).