Набор <tex>S1</tex> < <tex>S2</tex> если <tex>\max(S1) \le \min(S2)</tex>
}}
{{ Определение | definition =
Предположим, есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex> и набор <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex>. Тогда '''разделением''' <tex>q</tex> чисел <tex>p</tex> числами называется <tex>p + 1</tex> набор <tex>S_{0}, S_{1}, \ldots, S_{p}</tex>, где <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>.
}}
==Сортировка с использованием O(n log log n) времени и памятиЛеммы==Для сортировки <tex>n</tex> целых чисел в диапазоне {<tex>0, 1, \ldots, m - 1</tex>} предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex>O(\log (m + n))</tex>. Далее везде считается, что все числа упакованы в контейнеры одинаковой длины.
{{Лемма
|id = lemma1
|about = № 1
|statement =
Даны целые числа <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>1/e {{Лемма|id = lemma3|about = № 3|statement = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет Выбор <tex>n^{1/5}s</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь ого наибольшего числа среди <tex>n^{4/5}</tex> листьев. В отличие от оригинального дерева, зараз вставляется не один элемент, а <tex>d^2</tex>чисел, где <tex>d</tex> — количество детей узла дерева, упакованных в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{2/5}g</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровеньконтейнеров, они успешно разделились на может быть сделан за время <tex>t_{1} = O(n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, \ldots, S_{t_{1}}<log g/tex>, в каждом из которых <tex>n^{4/5}g)</tex> чисел и с использованием <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex>O(n^{(4/5)(2/5g)}</tex> чисел из <tex>S_{i}</tex> и опускаются на следующий уровень ЭП-деревапамяти. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex>t_{2} = n^{1/5}n^{4/25} = n^{9/25}</tex> наборов <tex>T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>В том числе, аналогичных наборам <tex>S_{i}</tex>, в каждом из которых <tex>n^{16/25}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереветак может быть найдена медиана.
Нетрудно заметить|proof = Так как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, что перебалансирока занимает <tex>Og</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex>, уберем хотя бы <tex>n \log\log /4</tex> чисел среди <tex>n)</tex> времени с . Затем упакуем оставшиеся из <tex>O(n)/g</tex> контейнеров в <tex>3n/4g</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссонаконтейнеров и затем продолжим рекурсию.}}
{{Лемма
|id = lemma4
|about = № 4
|statement =
Если <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> памяти.
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex>s</tex>. Имеется <tex>t = n^{1 - (4/5)^s}</tex> наборов по <tex>n^{(4/5)^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{(1/5)(4/5)^s}</tex> детей, то на <tex>s + 1</tex> уровень опускаются <tex>q = n^{(2/5)(4/5)^s}</tex> чисел для каждого набора, или всего <tex>qt \ge n^{2/5}</tex> чисел для всех наборов за один раз.
|proof =
Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <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>q</tex> чисел в каждом наборе вместе с <tex>p</tex> числами Для контейнеров вне групп (которых <tex>a_{1}, a_{2}, \ldots, a_sqrt{pn}</tex> из ЭП(g -дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex>S_{0} < </tex> {<tex>a_{1}</tex>} <tex><)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex>\ldots<O(n/tex> <tex><g)</tex> {времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex>a_{p}</tex>} <tex>< S_{p}n</tex>контейнеров. Таким образом, все числа отсортированы.
Так как Заметим, что когда <tex>qg = O( \log n)</tex>, сортировка <tex>O(n)</tex> чисел не надо полностью сортировать и в <tex>n/g</tex>q = p^2контейнеров произойдет за время <tex>O((n/g) \log\log n)</tex>, то можно использовать '''лемму №2''' для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления использованием <tex>O(multi-dividing techniquen/g)</tex> памяти. Выгода очевидна.}}
{{Лемма
|id = lemma5
|about = № 5
|statement =
Примем, что каждый контейнер содержит <tex> \log m > \log n</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((n \log\log n)/g)</tex> с использованием <tex>O(n/g)</tex> памяти.
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
После <tex>g</tex> сокращений бит в '''signature sorting''' получаем неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на '''лемму №2''' для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</tex>.
|proof =
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>( \log n)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma4|лемме №4]]. Перемещаем каждую группу контейнеров для чисел.
}}
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем{{Лемма|id = lemma6|about = № 6|statement =Предположим, используя '''лемму №2''', делается разделение. Так как получено неконсервативное преимущество в что каждый контейнер содержит <tex>(h/ \logm \log\log n > \log n)^</tex> бит, что <tex>g</tex> и работа происходит на уровнях не нижечисел, чем в каждом из которых <tex>2 (\log\log\log nm)/g</tex>бит, то алгоритм занимает упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>O(qt \log\log n)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(\log h - \log\log\log n/g) - \log\log\log n)) = </tex> с использованием <tex>O(\log\log n/g)</tex> временипамяти.
|proof =
Заметим, что несмотря на то, что длина контейнера <tex>\log m \log\log n</tex> бит, всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в [[#lemma4|лемме №4]] и [[#lemma5|лемме №5]] сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <tex>g \log\log n</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex>g \log\log n</tex> контейнеров, упаковываем <tex>g \log\log n</tex> контейнеров в <tex>g</tex>, упаковывая <tex>\log\log n</tex> контейнеров в один. Далее делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(g \log\log n)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, распаковываем <tex>g</tex> контейнеров в <tex>g \log\log n</tex> контейнеров.
В итоге разделились <tex>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть получилось, что <tex>S_{0}</tex> < {<tex>e_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>e_{p}</tex>} < <tex>S_{p}</tex>, где <tex>e_{i}</tex> {{---}} сегмент <tex>a_{i}</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <tex>B</tex> так, что числа в <tex>S_{i}</tex> предшествуют числам в <tex>S_{j}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i - 1}</tex>, но до <tex>S_{i}</tex>.
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в [[#lemma3|лемме №3]] может быть сделан за время и память <tex>O(n/g)</tex>, потому что упаковка в доказательстве [[#lemma3|лемме №3]] теперь может быть сделана за время <tex>O(n/g)</tex>.
}}
Пусть <tex>B[i]</tex> находится в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <tex>B[j]</tex> в <tex>B[j].subset</tex>.
На это потребуется линейное {{Лемма|id = lemma2|about = № 2|statement = <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>.
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере |proof = Алгоритм сортировки <tex>\log m \ge \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} \ldots 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} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>, где <tex>t_{i, k}</tex>: элемент с номером <tex>k = 1, 2, \ldots, 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} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1, h/ \log\log n}t_{2, h/ \log\log n} \ldots 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}0^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, 2, \ldots, \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} \ldots t_{1, h/ \log\log n}0^{r}t_sqrt{2, 1} \ldots 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} \ldots t_{1, h/ \log\log n}t_{2, 1}t_{2, 2} \ldots t_{\log\log n, h/ \log\log n}</tex>. В итоге используется <tex>O(\log\log n)</tex> времени для упаковки <tex>\log\log n</tex> контейнеров. Считаемнаборов, что времяпредставленный ниже, потраченное на один контейнер — константаявляется доказательством данной леммы.
==Уменьшение числа бит в числах==Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время без коллизий. Для этого используется модифицированная хеш-функция авторстваПостановка задачи и решение некоторых проблем: Dierzfelbinger и Raman.
Алгоритм: Пусть целое число Рассмотрим проблему сортировки <tex>b \ge 0n</tex> и пусть целых чисел из множества <tex>U = \{0, 1, \ldots, 2^b m - 1\}</tex>. Класс в <tex>H_\sqrt{b,sn}</tex> хеш-функций из наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <tex>Uk \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество {{0, ---}} <tex>k \ldots, 2^s - 1log \}log n</tex> определен как . Также предполагаем, что <tex>H_{b,s} = \{h_{a} log m \ge \log n \log\mid 0 log n< a /tex>. Иначе можно использовать radix sort для сортировки за время < 2^b, a tex>O(n \equiv 1 (log\bmod 2log n)\}</tex> и для всех линейную память. Делим <tex>x\log m</tex> из бит, используемых для представления каждого числа, в <tex>U\log n</tex>: блоков. Таким образом, каждый блок содержит как минимум <tex>h_{a}(x) = (ax\log\log n</tex> бит. <tex>\bmodi</tex> -ый блок содержит с <tex>2^b)i \log m/ \log n</tex> -ого по <tex>div((i + 1) \log m/ \log n - 1)</tex> -ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex>2^{b - s}\log n</tex>.-уровневый алгоритм, который работает следующим образом:
Данный алгоритм базируется на '''лемме №1'''.
На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По [[#lemma3|лемме №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>s = 2 \log n</tex>, получаем хеш-функцию <tex>h_{a}</tex>, которая захеширует <tex>n</tex> чисел из <tex>U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{a}(x)</tex> может быть посчитана для любого <tex>x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex>h_{a}</tex> ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex>\bmod</tex> <tex>2^b</tex>) и (<tex>div</tex> <tex>2^{b - s}</tex>).
Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma6|лемме №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> для [[#lemma6|лемме №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> бит. Таким образом, [[#lemma6|лемма №6]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <tex>O((n \log e)/ \log n)</tex>.
Такая хеш-функция может быть найдена за <tex>O(n^3)</tex>Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma6|леммы №6]].
Следует отметить, что, несмотря на размер таблицы <tex>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex>, потому что хеширование используется только для уменьшения количества бит в числе.
==Signature sorting==Предположим, что <tex>n</tex> чисел должны быть отсортированы, и в каждом <tex>\log m</tex> бит. Будем считаем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log m/h</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>\log m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>\log m/h</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>a_{1}</tex>, <tex>a_{2}</tex>, <tex>\ldots</tex>, <tex>a_{p}</tex> {{---}} <tex>p</tex> чисел и <tex>S</tex> {{---}} множество чисeл. Необходимо разделить <tex>S</tex> в <tex>p + 1</tex> наборов, таких, что: <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < {<tex>a_{2}</tex>} < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Так как используется '''signature sorting''' то перед тем, как делать вышеописанное разделение, необходимо поделить биты в <tex>a_{i}</tex> на <tex>h</tex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex>S</tex> и оставляем только один в каждом числе. По существу, для каждого <tex>a_{i}</tex> берутся все <tex>h</tex> сегментов. Если соответствующие сегменты <tex>a_{i}</tex> и <tex>a_{j}</tex> совпадают, то нам понадобится только один. Сегмент, который берется для числа в <tex>S</tex> это сегмент, который выделяется из <tex>a_{i}</tex>. Таким образом, начальная задача о разделении <tex>n</tex> чисел по <tex>\log m</tex> бит преобразуется в несколько задач на разделение с числами по <tex>\log m/h</tex> бит.
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы [[#lemma4|4]], [[#lemma5|5]], [[#lemma6|6]] расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем быть не должно.
Пример:
<tex>a_{1}</tex> = 3, <tex>a_{2}</tex> = 5, <tex>a_{3}</tex> = 7, <tex>a_{4}</tex> = 10, S = <tex>\{1, 4, 6, 8, 9, 13, 14\}</tex>.Собственно алгоритм:
Делим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> {{---}} верхний 1, нижний 1; <tex>a_{3}</tex> {{---}} верхний 1, нижний 3; <tex>a_{4}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим: для 1 нижний 1, так как он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.
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>)
Использование '''signature sorting''' <tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в данном алгоритме:наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.
Есть набор # Если <tex>T(level == 1)</tex> из тогда изучаем размер набора. Если размер меньше или равен <tex>p\sqrt{n}</tex> чисел, которые отсортированы как то <tex>a_{1}, a_{2}, \ldots, a_{p}return</tex>. Используем числа Иначе делим этот набор в <tex>T\le</tex> 3 набора, используя [[#lemma3|лемму №3]], чтобы найти медиану, а затем используем [[#lemma6|лемму №6]] для разделения сортировки. Для набора <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}где все элементы равны медиане, \ldotsне рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{являющийся номером набора для каждого из чисел (0}, S_{1}или 2). Затем направляем маркер для каждого числа назад к месту, \ldotsгде число находилось в начале. Также направляем двубитное число для каждого входного числа, S_{p}</tex>указывающее на текущий блок. Пусть # От <tex>h u = \log n/(c \log p)1</tex> для константы до <tex>c > 1k</tex>. (## Упаковываем <tex>h/ \log\log n \log pa^{(u)}_{i}</tex>)-битные числа могут храниться ый в одном контейнере, содержащим часть из <tex>(\log n)1/(c \log\log n)k</tex> бит-ых номеров контейнеров. Сначала рассматриваем биты в каждом Где <tex>a_a^{i(u)}</tex> и каждом <tex>b__{i}</tex> как сегменты одинаковой длины содержит несколько непрерывных блоков, которые состоят из <tex>h1/ \log\log nk</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (-ых битов <tex>a_{i}</tex>-ом и . При этом у <tex>b_a^{(u)}_{i}</tex>-ом) хешируются, и получается текущий блок это самый крупный блок.## Вызываем Sort(<tex>h/ k \log\log n</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <tex>a'_{i}level - 1</tex> {{---}} хеш-контейнер для , <tex>a_a^{i(u)}</tex>, аналогично <tex>b'_{i0}</tex>. В сумме хеш-значения имеют , <tex>a^{(2 \log n)/(c \log\log nu)}_{1}</tex> бит, хотя эти значения разделены на сегменты по <tex>h/ \log\log nldots</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>a^{(2 \log n)/(c \log\log nu)}_{t}</tex> бит). Потом рассматривается каждый хеш-контейнер как Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это числоотносится, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже)уже направлен назад к месту, где число находится во входных данных. После этой сортировки биты Число, имеющее наибольшее число бит в <tex>a_{i}</tex> и , показывающее на текущий блок в нем, так же направлено назад к <tex>b_a_{i}</tex> разрезаны на .## Отправляем <tex>\log\log n/ha_{i}</tex> сегментов. Таким образом-ые к их наборам, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage)используя [[#lemma6|лемму №6]].
После того, как вышеописанный процесс повторится Algorithm IterateSortCall Sort(<tex>gk \log\log n</tex> раз, получится неконсервативное преимущество в <tex>\log_{k}((h/ \log\log n)^g/4)</tex> раз, в то время как потрачено только <tex>O(gqt)a_{0}</tex>, <tex>a_{1}</tex>, <tex>\ldots</tex> времени, так как каждое многократное деление происходит за линейное время <tex>O(qt)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>\log\log n/h</tex>-ые, Время работы алгоритма <tex>O(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> по счету в числе. Хеш-функцию для <tex>(\log\log n/h)^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\log\log n/hk)^t</tex> сегментов. Рассматривая каждый сегмент как число, получаем <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex>t < \log n</tex>, то получится не более <tex>\log n</tex> хеш-функцийчто доказывает лемму.}}
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <tex>==Сортировка с использованием O(2 \log n)/(c \log\log n)времени и памяти==Для сортировки </tex> бит. Есть <tex>tn</tex> наборов, целых чисел в каждом из которых диапазоне {<tex>q + p0, 1, \ldots, m - 1</tex> хешированных контейнеров по } предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex>O(2 \log (m + n)/(c \log\log n)</tex> бит в каждом. Эти контейнеры должны быть отсортированы Далее везде считается, что все числа упакованы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образомодинаковой длины.
Procedure '''LinearБерем <tex>1/e = 5</tex> для ЭП-Timeдерева Андерссона. Следовательно, у корня будет <tex>n^{1/5}</tex> детей, и каждое ЭП-Sort'''дерево в каждом ребенке будет иметь <tex>n^{4/5}</tex> листьев. В отличие от оригинального дерева, зараз вставляется не один элемент, а <tex>d^2</tex>, где <tex>d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{2/5}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex>t_{1} = n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <tex>n^{4/5}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex>n^{(4/5)(2/5)}</tex> чисел из <tex>S_{i}</tex> и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex>t_{2} = n^{1/5}n^{4/25} = n^{9/25}</tex> наборов <tex>T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <tex>S_{i}</tex>, в каждом из которых <tex>n^{16/25}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереве.
Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>Нетрудно заметить, что перебалансирока занимает <tex>d_{i}.value</tex> — значение числа <tex>d_{i}</tex>, в котором <tex>O(2 \log n)/(c \log\log n)</tex> бит, времени с <tex>d_{i}.setO(n)</tex> — наборвремени на уровень, в котором находится <tex>d_{i}</tex>. Следует отметить, что всего есть <tex>t</tex> наборованалогично стандартному ЭП-дереву Андерссона.
# Сортируем все <tex>d_{i}</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа в <tex>A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex>n^{2/5}</tex> чисел.
# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</tex>.
==Лемма №1==Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0, и <tex>T</tex> является подмножеством множества <tex>\{0, \ldots, 2^b Нам следует нумеровать уровни ЭП- 1\}</tex>дерева с корня, содержащим начиная с нуля. Рассмотрим спуск вниз на уровне <tex>ns</tex> элементов, и . Имеется <tex>t</tex> <tex>\ge</tex> <tex>2= n^{1 -(4/5)^s + 1}</tex>Снаборов по <tex>n^k_{n(4/5)^s}</tex>чисел в каждом. Функция Так как каждый узел на данном уровне имеет <tex>h_p = n^{a(1/5)(4/5)^s}</tex>детей, принадлежащая то на <tex>H_{b,s}+ 1</tex>, может быть выбрана за время уровень опускаются <tex>Oq = n^{(bn^2/5)<(4/tex> так, что количество коллизий <tex>coll(h_{a5)^s}, T)</tex> чисел для каждого набора, или всего <tex>qt \le<ge n^{2/tex> <tex>t5}</tex>чисел для всех наборов за один раз.
==Лемма №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>q</tex> чисел в каждом наборе вместе с <tex>p</tex> числами <tex>a_{1}, a_{2}, \ldots, a_{p}</tex> из ЭП-дерева, так, что эти <tex>q</tex> чисел разделены в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex> таких, что <tex>S_{0} < </tex> {<tex>a_{1}</tex>} <tex><</tex> <tex>\ldots</tex> <tex><</tex> {<tex>a_{p}</tex>} <tex>< S_{p}</tex>.
Доказательство:
Алгоритм сортировки Так как <tex>nq</tex> целых чисел в не надо полностью сортировать и <tex>\sqrt{n}q = p^2</tex> наборов, представленный нижето можно использовать [[#lemma2|лемму №2]] для сортировки. Для этого необходимо неконсервативное преимущество, является доказательством данной леммыкоторое получается с помощью signature sorting. Для этого используется линейная техника многократного деления (multi-dividing technique).
==Сортировка n целых чисел в sqrt(n) наборов==
Постановка задачи и решение некоторых проблем:
После <tex>g</tex> сокращений бит в '''signature sorting''' получаем неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на [[#lemma2|лемму №2]] для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</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>-уровневый алгоритм, который работает следующим образом:
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma2|лемму №2]], делается разделение. Так как получено неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> и работа происходит на уровнях не ниже, чем <tex>2 \log\log\log n</tex>, то алгоритм занимает <tex>O(qt \log\log n/(g(\log h - \log\log\log n) - \log\log\log n)) = O(\log\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>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть получилось, что <tex>S_{0}</tex> < {<tex>e_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>e_{p}</tex>} < <tex>S_{p}</tex>, где <tex>e_{i}</tex> {{---}} сегмент <tex>a_{i}</tex>, полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве <tex>B</tex> так, что числа в <tex>S_{i}</tex> предшествуют числам в <tex>S_{j}</tex> если <tex>i < j</tex> и <tex>e_{i}</tex> хранится после <tex>S_{i - 1}</tex>, но до <tex>S_{i}</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>B[i]</tex> находится в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполниться, т.кдля каждого поднабора помещаем все <tex>B[j]</tex> в <tex>B[j]. основан на алгоритме из '''леммы №6'''subset</tex>.
На это потребуется линейное время и место.
При таком помещении сразу возникает следующая проблема.
Рассмотрим Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>a\log m \ge \log\log\log n</tex>, которое является потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть <tex>ih/ \log\log n</tex>-ым хешированных значений (сегментов) в наборе себе на уровне <tex>S\log h</tex>в ЭП-дереве. Рассмотрим блок Полное число хешированных бит в контейнере равно <tex>a(2 \log n)(c \log\log n)</tex> (назовем его бит. Хешированные биты в контейнере выглядят как <tex>a'0^{i}t_{1}0^{i}t_{2} \ldots t_{h/ \log\log n}</tex>), который является где <tex>it_{k}</tex>-ым мые — хешированные биты, а нули {{---}} это просто нули.ч. в Сначала упаковываем <tex>S\log\log n</tex>. Когда используется вышеописанный метод перемещения нескольких следующих блоков контейнеров в один и получаем <tex>aw_{1} = 0^{j}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}0^{j}t_{1, 2} \ldots t_{\log\log n, h/ \log\log n}</tex> (назовем это , где <tex>a''t_{i, k}</tex>) в : элемент с номером <tex>Sk = 1, 2, \ldots, h/ \log\log n</tex>, из <tex>a''i</tex> просто перемещен на позицию в наборе -ого контейнера. Используем <tex>SO(\log\log n)</tex>шагов, но не обязательно на позицию чтобы упаковать <tex>iw_{1}</tex> (где расположен в <tex>a'w_{2} = 0^{jh/ \log\log n}t_{1, 1}t_{2, 1} \ldots t_{\log\log n, 1}t_{1, 2}t_{2, 2} \ldots t_{1, h/ \log\log n}t_{2, h/ \log\log n} \ldots t_{\log\log n, h/ \log\log n}</tex>). Если значение блока Теперь упакованные хеш-биты занимают <tex>a'2 \log n/c</tex> одинаково для всех чисел в бит. Используем <tex>SO(\log\log n)</tex>, то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в времени чтобы распаковать <tex>Sw_{2}</tex> помещен в <tex>a''\log\log n</tex>. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блокеконтейнеров <tex>w_{3, k} = 0^{jh/ \log\log n}0^{r}t_{k, 1}0^{r}t_{k, 2} \ldots t_{k, h/ \log\log n} k = 1, который назовем "текущий блок набора". Блоки2, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор\ldots, последующие блоки помещаются в набор вместе с текущим блоком\log\log n</tex>. Так вотЗатем, в вышеописанном процессе помещения предполагаетсяиспользуя <tex>O(\log\log n)</tex> времени, что самый значимый блок среди упаковываем эти <tex>k \log e\log n</tex> блоков контейнеров в один <tex>w_{4} = 0^{r}t_{1, 1}0^{r}t_{1, 2} \ldots t_{1, h/ \log\log n}0^{r}t_{---2, 1}\ldots t_{\log\log n, h/ \log\log n} это текущий блок</tex>. Таким образом, после тогоЗатем, как эти используя <tex>k O(\log\log en)</tex> шагов, упаковываем <tex>w_{4}</tex> блоков помещены в набор<tex>w_{5} = 0^{s}t_{1, 1}t_{1, 2} \ldots t_{1, изначальный текущий блок удаляетсяh/ \log\log n}t_{2, потому что известно1}t_{2, 2} \ldots t_{\log\log n, что эти h/ \log\log n}</tex>. В итоге используется <tex>k O(\log\log en)</tex> блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных времени для упаковки <tex>k \log e\log n</tex> блокахконтейнеров. Считаем, что время, потраченное на один контейнер — константа.
==Уменьшение числа бит в числах==
Один из способов ускорить сортировку {{---}} уменьшить число бит в числе. Один из способов уменьшить число бит в числе {{---}} использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий <tex>O(m)</tex> памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до <tex>O(n)</tex>. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования <tex>n</tex> чисел в таблицу размера <tex>O(n^2)</tex> за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.
Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. '''Леммы №4, №5, №6''' расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из <tex>n</tex> элементов в наборы размера <tex>\sqrt{n}</tex>, то проблем быть не должно.
Алгоритм: Пусть целое число <tex>b \ge 0</tex> и пусть <tex>U = \{0, \ldots, 2^b - 1\}</tex>. Класс <tex>H_{b,s}</tex> хеш-функций из <tex>U</tex> в <tex>\{0, \ldots, 2^s - 1\}</tex> определен как <tex>H_{b,s} = \{h_{a} \mid 0 < a < 2^b, a \equiv 1 (\bmod 2)\}</tex> и для всех <tex>x</tex> из <tex>U</tex>: <tex>h_{a}(x) = (ax</tex> <tex>\bmod</tex> <tex>2^b)</tex> <tex>div</tex> <tex>2^{b - s}</tex>.
Собственно Данный алгоритм:базируется на [[#lemma1|лемме №1]].
Algorithm Sort(Взяв <tex>k \logs = 2 \log n</tex>, получаем хеш-функцию <tex>levelh_{a}</tex>, которая захеширует <tex>n</tex> чисел из <tex>a_U</tex> в таблицу размера <tex>O(n^2)</tex> без коллизий. Очевидно, что <tex>h_{0a}(x)</tex>может быть посчитана для любого <tex>x</tex> за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить <tex>a_h_{1a}</tex>ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только (<tex>\ldotsbmod</tex> <tex>2^b</tex>) и (<tex>div</tex>, <tex>a_2^{tb - s}</tex>).
<tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</tex> это уровень рекурсии.
# Если <tex>(level == 1)</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\le</tex> 3 набора, используя '''лемму №3''', чтобы найти медиану, а затем используем '''лемму №6''' для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.# От <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>. При этом у <tex>a^{(u)}_{i}функция может быть найдена за </tex> текущий блок это самый крупный блок.## Вызываем SortO(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u3)}_{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>O(n^2)</tex>, потребность в памяти не превышает <tex>O(n)</tex>, потому что хеширование используется только для уменьшения количества бит в числе.
==Signature sorting==
Предположим, что <tex>n</tex> чисел должны быть отсортированы, и в каждом <tex>\log m</tex> бит. Будем считаем, что в каждом числе есть <tex>h</tex> сегментов, в каждом из которых <tex>\log m/h</tex> бит. Теперь применяем хеширование ко всем сегментам и получаем <tex>2h \log n</tex> бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке <tex>n</tex> чисел по <tex>\log m</tex> бит в каждом стала задачей по сортировке <tex>n</tex> чисел по <tex>\log m/h</tex> бит в каждом.
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>);
от Также рассмотрим проблему последующего разделения. Пусть <tex>a_{1 до 5# Помещаем }</tex>, <tex>a_{i2}</tex> в соответствующий набор с помощью bucket sort, потому что наборов около <tex>\sqrtldots</tex>, <tex>a_{np}</tex> {{---}}<tex>p</tex> чисел и <tex>S</tex>{{---}} множество чисeл.# Для каждого набора Необходимо разделить <tex>S = </tex>в <tex>p + 1</tex> наборов, таких, что: <tex>S_{0}</tex> < {<tex>a_{i_1}</tex>} < <tex>S_{01}}, </tex> < {<tex>a_{i_{12}</tex>}, < <tex>\ldots, </tex> < {<tex>a_{i_p}</tex>} < <tex>S_{t}p}</tex>}. Так как используется '''signature sorting''' то перед тем, как делать вышеописанное разделение, если необходимо поделить биты в <tex>t > \sqrta_{ni}</tex>, вызываем Sort(на <tex>h</tex> сегментов и взять некоторые из них. Так же делим биты для каждого числа из <tex>k \log\log nS</tex>и оставляем только один в каждом числе. По существу, для каждого <tex>\log_a_{ki}((\log n)</4)tex> берутся все <tex>h</tex>, сегментов. Если соответствующие сегменты <tex>a_{i_{0i}}, </tex> и <tex>a_{i_{1}j}</tex> совпадают, то нам понадобится только один. Сегмент, \ldotsкоторый берется для числа в <tex>S</tex> это сегмент, который выделяется из <tex>a_{i_{t}i}</tex>). Таким образом, начальная задача о разделении <tex>n</tex> чисел по <tex>\log m</tex> бит преобразуется в несколько задач на разделение с числами по <tex>\log m/h</tex> бит.
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает '''лемму №2'''.
==Лемма №3==Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел, упакованных в <tex>n/g</tex> контейнеров, может быть сделан за время <tex>O(n \log g/g)</tex> и с использованием <tex>O(n/g)</tex> памяти. В том числе, так может быть найдена медиана.Пример:
<tex>a_{1}</tex> = 3, <tex>a_{2}</tex> = 5, <tex>a_{3}</tex> = 7, <tex>a_{4}</tex> = 10, S = <tex>\{1, 4, 6, 8, 9, 13, 14\}</tex>.
ДоказательствоДелим числа на 2 сегмента. Для <tex>a_{1}</tex> получим верхний сегмент 0, нижний 3; <tex>a_{2}</tex> {{---}} верхний 1, нижний 1; <tex>a_{3}</tex> {{---}} верхний 1, нижний 3; <tex>a_{4}</tex> {{---}} верхний 2, нижний 2. Для элементов из S получим:для 1 нижний 1, так как он выделяется из нижнего сегмента <tex>a_{1}</tex>; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.
Так как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex>, уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.
==Лемма №4==Если <tex>g</tex> целых чисел, Использование '''signature sorting''' в сумме использующих <tex>(\log n)/2</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы за время <tex>O((n/g) \log g)</tex> с использованием <tex>O(n/g)</tex> памяти.данном алгоритме:
Есть набор <tex>T</tex> из <tex>p</tex> чисел, которые отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>. Используем числа в <tex>T</tex> для разделения набора <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в <tex>p + 1</tex> наборов <tex>S_{0}, S_{1}, \ldots, S_{p}</tex>. Пусть <tex>h = \log n/(c \log p)</tex> для константы <tex>c > 1</tex>. (<tex>h/ \log\log n \log p</tex>)-битные числа могут храниться в одном контейнере, содержащим <tex>(\log n)/(c \log\log n)</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>h/ \log\log n</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) хешируются, и получается <tex>h/ \log\log n</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <tex>a'_{i}</tex> {{---}} хеш-контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш-значения имеют <tex>(2 \log n)/(c \log\log n)</tex> бит, хотя эти значения разделены на сегменты по <tex>h/ \log\log n</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>(2 \log n)/(c \log\log n)</tex> бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\log\log n/h</tex> сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>h/ \log\log n</tex> (additional multiplicative advantage).
Доказательство:После того, как вышеописанный процесс повторится <tex>g</tex> раз, получится неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex> раз, в то время как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex>O(qt)</tex>.
Так как используется только <tex>(\log n)/2</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <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{log\log n}/h</tex>-ые, <tex>(g \log\log n/h)^2</tex>- 1ые, <tex>\ldots</tex> по счету в числе. Хеш-функцию для <tex>(\log\log n/h)^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex>p</tex> штукчисел на <tex>(\log\log n/h) разбираем и собираем заново контейнеры^t</tex> сегментов. На это потребуется не более Рассматривая каждый сегмент как число, получаем <tex>Op(\log\log n/gh)^t</tex> времени и памятичисел. После всего этого используем bucket sort вновь Затем получаем одну хеш-функцию для сортировки этих чисел. Так как <tex>t < \log n</tex> контейнеров. Таким образом, все числа отсортированыто получится не более <tex>\log n</tex> хеш-функций.
ЗаметимРассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что когда хешированные значения для каждого контейнера упакованы в <tex>g = O( 2 \log n)/(c \log\log n)</tex>, сортировка бит. Есть <tex>O(n)t</tex> чисел наборов, в каждом из которых <tex>n/gq + p</tex> хешированных контейнеров произойдет за время по <tex>O((2 \log n)/g) (c \log\log n)</tex> с использованием <tex>O(n/g)</tex> памятибит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Выгода очевиднаКомбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
==Лемма №5==
Примем, что каждый контейнер содержит <tex> \log m > \log n</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O((n \log\log n)/g)</tex> с использованием <tex>O(n/g)</tex> памяти.
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
Procedure '''Linear-Time-Sort'''
ДоказательствоВходные данные: Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>( \log r > = n)^{2/25}</tex> бит. Сортировка сгруппирует контейнеры для чисел как в '''лемме №4'''. Перемещаем каждую группу контейнеров для чисел. ==Лемма №6==Предположим, что каждый контейнер содержит <tex>\log m \log\log n > \log nd_{i}</tex> бит, что <tex>gd_{i}.value</tex> чисел, в каждом из которых — значение числа <tex>(\log m)/gd_{i}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий котором <tex>(2 \log n)/(2gc \log\log n)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числаd_{i}. Тогда <tex>nset</tex> чисел — набор, в котором находится <tex>n/gd_{i}</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g). Следует отметить, что всего есть </tex> с использованием <tex>O(n/g)t</tex> памятинаборов.
# Сортируем все <tex>d_{i}</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа в <tex>A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex>n^{2/5}</tex> чисел.
# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</tex>.
Доказательство:
Заметим, что несмотря на то, что длина контейнера <tex>\log m \log\log n</tex> бит, всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в '''леммах №4, №5''' сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем <tex>g \log\log n</tex> вместо <tex>g</tex> контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей <tex>g \log\log n</tex> контейнеров, упаковываем <tex>g \log\log n</tex> контейнеров в <tex>g</tex>, упаковывая <tex>\log\log n</tex> контейнеров в один. Далее делаем транспозицию над <tex>g</tex> контейнерами. Таким образом перемещение занимает всего <tex>O(g \log\log n)</tex> времени для каждой группы и <tex>O(n/g)</tex> времени для всех чисел. После завершения транспозиции, распаковываем <tex>g</tex> контейнеров в <tex>g \log\log n</tex> контейнеров.
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \le \log n</tex> чисел в один контейнер, тогда выбор в '''лемме №3''' может быть сделан за время и память <tex>O(n/g)</tex>, потому что упаковка в доказательстве '''леммы №3''' теперь может быть сделана за время <tex>O(n/g)</tex>.
==Литература==
