81
правка
Изменения
Нет описания правки
Если <tex>g</tex> целых чисел, в сумме использующие <tex>(\log n)/2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g) \log g)</tex>, с использованием <tex>O(n/g)</tex> места.
|proof=
Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, мы можем использовать bucket sorting чтобы отсортировать все контейнеры. представляя каждый как число, что занимает <tex>O(n/g)</tex> времени и места. Потому, что мы используем <tex>(\log n)/2</tex> бит на контейнер нам понадобится <tex>\sqrt {n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < (\log n)/2</tex> контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более <tex>g - 1</tex> контейнеров которые не смогут образовать группу. Поэтому не более <tex>\sqrt{n}(g - 1)</tex> контейнеров не смогут сформировать группу. Для каждой группы мы помещаем <tex>i</tex>-е число во всех <tex>g</tex> контейнерах в один. Таким образом мы берем <tex>g</tex> <tex>g</tex>-целых векторов и получаем <tex>g</tex> <tex>g</tex>-целых векторов где <tex>i</tex>-ый вектор содержит <tex>i</tex>-ое число из входящего вектора. Эта транспозиция может быть сделана за время <tex>O(g \log g)</tex>, с использованием <tex>O(g)</tex> места. Для всех групп это занимает время <tex>O((n/g) \log g)</tex>, с использованием <tex>O(n/g)</tex> места.
Для контейнеров вне групп (которых <tex>\sqrt({n)}(g - 1)</tex> штук) мы просто разберем и соберем заново контейнеры. На это потребуется не более <tex>O(n/g)</tex> места и времени. После всего этого мы используем bucket sorting вновь для сортировки <tex>n</tex> контейнеров. таким образом мы отсортируем все числа.
}}
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g <= \log n</tex> чисел в один контейнер, тогда выбор в лемме три может быть сделан за время и место <tex>O(n/g)</tex>, потому, что упаковка в доказатльстве леммы три теперь может быть сделана за время <tex>O(n/g)</tex>.
==Сортировка n целых чисел в <tex>sqrt(n)</tex> наборов==
Постановка задачи и решение некоторых проблем:
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает лемму 2.
==Собственно сортировка с использованием <tex>O(n \log\log nnloglogn)</tex> времени и памяти==
Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, ..., m - 1</tex>} мы предполагаем, что используем контейнер длины <tex>O(\log (m + n))</tex> в нашем консервативном алгоритме. Мы всегда считаем что все числа упакованы в контейнеры одинаковой длины.
Теперь рассмотрим проблему упаковки, которую решим следующим образом. Будем считать что число бит в контейнере <tex>\log m >= \log\log\log n</tex>, потому, что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>h/ \log\log n</tex> хэшированных значений (сегментов) в себе на уровне <tex>\log h</tex> в Э.П.дереве. Полное число хэшированных бит в контейнере <tex>(2 \log n)(c \log\log n)</tex> бит. Хотя хэшированны биты в контейнере выглядят как <tex>0^{i}t_{1}0^{i}t_{2}...t_{h/ \log\log n}</tex>, где <tex>t_{k}</tex>-ые это хэшированные биты, а нули это просто нули. Сначала упаковываем <tex>\log\log n</tex> контейнеров в один и получаем <tex>w_{1} = 0^{j}t_{1, 1}t_{2, 1}...t_{\log\log n, 1}0^{j}t_{1, 2}...t_{\log\log n, h/ \log\log n}</tex> где <tex>t_{i, k}</tex>: <tex>k = 1, 2, ..., h/ \log\log n</tex> из <tex>i</tex>-ого контейнера. мы ипользуем <tex>O(\log\log n)</tex> шагов, чтобы упаковать <tex>w_{1}</tex> в <tex>w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} ... t_{\log\log n, 1}t_{1, 2}t_{2, 2} ... t_{1, h/ \log\log n}t_{2, h/ \log\log n} ... t_{\log\log n, h/ \log\log n}</tex>. Теперь упакованные хэш биты занимают <tex>2 \log n/c</tex> бит. Мы используем <tex>O(\log\log n)</tex> времени чтобы распаковать <tex>w_{2}</tex> в <tex>\log\log n</tex> контейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}O^{r}t_{k, 2} ... t_{k, h/ \log\log n} k = 1, 2, ..., \log\log n</tex>. Затем используя <tex>O(\log\log n)</tex> времени упаковываем эти <tex>\log\log n</tex> контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} ... t_{1, h/ \log\log n}0^{r}t_{2, 1} ... t_{\log\log n, h/ \log\log n}</tex>. Затем используя <tex>O(\log\log n)</tex> шагов упаковать <tex>w_{4}</tex> в <tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} ... t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} ... t_{\log\log n, h/ \log\log n}</tex>. В итоге мы используем <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаем что время потраченное на одно слово {{---}} константа.
==Литераура==
