81
правка
Изменения
Нет описания правки
Так как нам не надо полностью сортировать <tex>q</tex> чисел и <tex>q = p^2</tex>, есть возможность использовать лемму 2 для сортировки. Для этого нам надо неконсервативное преимущество которое мы получим ниже. Для этого используем линейную технику многократного деления (multi-dividing technique) чтобы добиться этого.
Для этого воспользуемся signature sorting. Адаптируем этот алгоритм для нас. Предположим у нас есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, ..., a_{p}</tex>, и мы хотим использовать числа в <tex>T</tex> для разделения <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, ..., b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, ..., S_{p}</tex> что <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < ... < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами. Пусть <tex>h = logn/(clogp)</tex> для константы <tex>c > 1</tex>. <tex>h/loglognlogp</tex> битные числа могут быть хранены в одном контейнере, так что одно слово хранит <tex>(logn)/(cloglogn)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/loglogn</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки мы хэштруем числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) чтобы получить <tex>h/loglogn</tex> хэшированных значений в одном контейнере. Чтобы получить значения сразу, при вычислении хэш значений сегменты не влияют друг на друга, мы можем даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хэш значения считаются за константное время. Затем, посчитав значения мы объединяем два контейнера в один. Пусть <tex>a'_{i}</tex> хэш контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хэш значения имеют <tex>(2logn)/(cloglogn)</tex> бит. Хотя эти значения разделены на сегменты по <tex>h/loglogn</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые мы забиваем нулями. Сначала упаковываем все сегменты в <tex>(2logn)/(cloglogn)</tex> бит. Потом рассмотрим каждый хэш контейнер как число и отсортируем эти хэш слова за линейное время (сортировка рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>loglogn/h</tex>. Таким образом мы получили дополнительное мультипликативное преимущество в <tex>h/loglogn</tex> (additional multiplicative advantage).
После того, как мы повторили вышеописанный процесс <tex>g</tex> раз мы получили неконсервативное преимущество в <tex>(h/loglogn)^g</tex> раз, в то время как мы потратили только <tex>O(gqt)</tex> времени, так как каждое многократное деление делятся за линейное время <tex>O(qt)</tex>.
На это потребуется линейное время и место.
Теперь рассмотрим проблему упаковки, которую решим следующим образом. Будем считать что число бит в контейнере <tex>logm >= logloglogn</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/loglogn</tex> хэшированных значений (сегментов) в себе на уровне <tex>logh</tex> в Э.П.дереве. Полное число хэшированных бит в контейнере <tex>(2logn)(cloglogn)</tex> бит. Хотя хэшированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2}...t_{h/loglogn}</tex>, где <tex>t_{k}</tex>-ые это хэшированные биты, а нули это просто нули. Сначала упаковываем loglogn контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1}...t_{loglogn, 1}0^{j}t_{1, 2}...t_{loglogn, h/loglogn}</tex> где <tex>t_{i, k}</tex>: <tex>k = 1, 2, ..., h/loglogn</tex> из <tex>i</tex>-ого контейнера. мы ипользуем <tex>O(loglogn)</tex> шагов, чтбы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/loglogn}t_{1, 1}t_{2, 1} ... t_{loglogn, 1}t_{1, 2}t_{2, 2} ... t_{1, h/loglogn}t_{2, h/loglogn} ... t_{loglogn, h/loglogn}</tex>. Теперь упакованные хэш биты занимают <tex>2logn/c</tex> бит. Мы используем <tex>O(loglogn)</tex> времени
