Изменения

ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (<tex>0< e < 1</tex>) ЭП-поддеревьев, в каждом из которых <tex>n^{1 - e}</tex> листьев; каждое ЭП-поддерево является сыном корня <tex>r</tex>. В этом дереве <tex>O(n \log\log n)</tex> уровней. При нарушении баланса дерева, необходимо балансирование, которое требует <tex>O(n \log\log n)</tex> времени при <tex>n</tex> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночкепоодиночке, как изначально предлагает предлагал Андерссон.

# Алгоритм , сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> , называется консервативным, если длина контейнера (число бит в контейнере), является равна <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.

Для сортировки <tex>n</tex> целых чисел в диапазоне от {<tex>0, 1, \ldots, m - 1</tex>} предполагается, что в нашем консервативном алгоритме используется контейнер длины <tex>O(\log (m + n))</tex> в нашем консервативном алгоритме. Далее всегда везде считается, что все числа упакованы в контейнеры одинаковой длины.

Берем <tex>1/e = 5</tex> для экспоненциального поискового ЭП-дерева Андерссона. Следовательно, у корня будет <tex>n^{1/5}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <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>S_{i}</tex>. Теперь числа опускаются дальше в ЭП-дереве.

Нетрудно заметить, что перебалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(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>.

Procedure linear'''Linear-Time-Sort'''

# Сортируем все <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>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>.

Теперь для каждого набора собираются все его поднаборы в подзадачах собираются в один набор. Затем, используя '''лемму №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>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>B[i]</tex> находится в поднаборе <tex>B[i].subset</tex>. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все <tex>B[j]</tex> в <tex>B[j].subset</tex>.

Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <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}O^{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_{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> контейнеров. Считаем, что время , потраченное на один контейнер — константа.