81
правка
Изменения
Нет описания правки
На каждой стадии мы работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.) потому, что каждое м.ч. теперь содержит только <tex>logm/logn</tex> бит. Каждое число представлено и соотносится с м.ч., над которым мы работаем в данный момент. Положим, что нулевая стадия работает с самыми большим блоком (блок номер <tex>logn - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/logn</tex> контейнеров с <tex>logn</tex> м.ч. упакованных в один контейнер. Мы пренебрегаем временем, потраченным на на эту упаковку, считая что она бесплатна. По третьей лемме мы можем найти медиану этих <tex>n</tex> м.ч. за время и память <tex>O(n/logn)</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>logm/logn</tex> бит (наибольший блок) из каждого числа из <tex>S'_{2}</tex> из дальнейшего рассмотрения. Таким образом после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>logn</tex> блоков, для каждого числа потребуется не более <tex>logn</tex> стадий чтобы поместить его в набор половинного размера. За <tex>2logn</tex> стадий все числа будут отсортированы. Так как на каждой стадии мы работаем с <tex>n/logn</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, мы затратим <tex>O(n)</tex> времени из-за <tex>2logn</tex> стадий.
Сложная часть алгоритма заключается в том, как поместить маленькие числа в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Мы можем использовать <tex>loge</tex> битов чтобы сделать марки для каждого набора. Теперь хотелось бы использовать лемму шесть. Полный размер маркера для каждого контейнера должен быть <tex>logn/2</tex>, и маркер использует <tex>loge</tex> бит, количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>logn/(2loge)</tex>. В дальнейшем т.к. <tex>g = logn/(2loge)</tex> м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>kloglognlogn</tex> блоков, каждое м.ч. может содержать <tex>O(klogn/g) = O(kloge)</tex> блоков. Заметим, что мы используем неконсервативное преимущество в <tex>loglogn</tex> для использования леммы шесть. Поэтому мы предполагаем что <tex>logn/(2loge)</tex> м.ч. в каждом из которых <tex>kloge</tex> блоков битов числа упакованный в один контейнер. Для каждого м.ч. мы используем маркер из <tex>loge</tex> бит, который показывает к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры как и м.ч. Так как каждый контейнер для маркеров содержит <tex>logn/(2loge)</tex> маркеров, то для каждого контейнера требуется <tex>(logn)/2</tex> бит. Таким образом лемма шесть может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((nloge)/logn)</tex> контейнеров то время необходимое для помещения м.ч. в их наборы потребуется <tex>O((nloge)/logn)</tex> времени.
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из леммы шесть.
При таком помещении мы сразу сталкиваемся со следующей проблемой.
