Изменения
Нет описания правки
==Лемма №2==
<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>\sqrt{n}</tex> наборов, представленный ниже, является доказательством данной леммы.
==Сортировка n целых чисел в sqrt(n) наборов==
Постановка задачи и решение некоторых проблем:
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов как во второй лемме. Предполагая, что в каждом контейнере <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> м.ч. упакованных в один контейнер. Пренебрегая временем, потраченным на на эту упаковку, считается, что она бесплатна. По третьей лемме находим медиану этих <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>\le <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> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <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> для использования леммы шесть. Поэтому предполагается, что <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> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <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> блоках.
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы четыре, пять и шесть расчитанны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем не должно быть.
Собственно алгоритм:
Algorithm Sort(<tex>k \log\log n</tex>, <tex>level</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{t}</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 набора используя лемму три, чтобы найти медиану а затем использовать лемму 6 для сортировки. Для набора где все элементы равны медиане, не рассматривать текущий блок и текущим блоком сделать следующий. Создать маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направьте маркер для каждого числа назад к месту, где число находилось в начале. Также направьте двубитное число для каждого входного числа, указывающее на текущий блок. <tex>Return</tex>.
# От <tex>u = 1</tex> до <tex>k</tex>
## Упаковать <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров, где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>1/k</tex>-ых битов <tex>a_{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>
end.
Algorithm IterateSort
Call Sort(<tex>k \log\log n</tex>, <tex>\log_{k}((\log n)/4)</tex>, <tex>a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex>, <tex>a_{n - 1}</tex>);
от 1 до 5
# Поместить <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>)
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает лемму 2.
==Лемма №3==
