Сортировка Хана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
(Дроби)
Строка 29: Строка 29:
 
  }}
 
  }}
 
{{ Определение | definition =
 
{{ Определение | definition =
  Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с '''неконсервативным преимуществом''' <tex>k</tex>.
+
  Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\geqslant</tex> 1, тогда сортировка происходит с '''неконсервативным преимуществом''' <tex>k</tex>.
 
}}
 
}}
 
{{ Определение | definition =
 
{{ Определение | definition =
Строка 38: Строка 38:
 
<tex>\max(S) = \max\limits_{a \in S} a</tex>
 
<tex>\max(S) = \max\limits_{a \in S} a</tex>
  
Набор <tex>S1</tex> < <tex>S2</tex> если <tex>\max(S1) \le \min(S2)</tex>
+
Набор <tex>S1 < S2</tex> если <tex>\max(S1) \leqslant \min(S2)</tex>
 
}}
 
}}
  
 
{{ Определение | definition =
 
{{ Определение | 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>.
+
  Предположим, есть набор <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} < a_{1} < S_{1} < \ldots < a_{p} < S_{p}</tex>.
 
}}
 
}}
  
Строка 51: Строка 51:
 
|about = № 1
 
|about = № 1
 
|statement =  
 
|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>b</tex> <tex>\geqslant</tex> <tex>s</tex> <tex>\geqslant</tex> 0, и <tex>T</tex> является подмножеством множества <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\geqslant</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>\leqslant</tex> <tex>t</tex>.
 
}}
 
}}
  
Строка 58: Строка 58:
 
|about = № 2
 
|about = № 2
 
|statement =  
 
|statement =  
Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел, упакованных в <tex>n/g</tex> контейнеров, может быть сделан за время <tex>O(n \log g/g)</tex> и с использованием <tex>O(n/g)</tex> памяти. В том числе, так  может быть найдена медиана.
+
Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел, упакованных в <tex>\frac{n}{g}</tex> контейнеров, может быть сделан за время <tex>O(\frac{n \log g}{g})</tex> и с использованием <tex>O(\frac{n}{g})</tex> памяти. В том числе, так  может быть найдена медиана.
  
 
|proof =  
 
|proof =  
Так как возможно делать попарное сравнение <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> контейнеров и затем продолжим рекурсию.
+
Так как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>S</tex> из медиан теперь содержится в <tex>\frac{n}{5g}</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex>, уберем хотя бы <tex>\frac{n}{4}</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>\frac{n}{g}</tex> контейнеров в <tex>\frac{3n}{4g}</tex> контейнеров и затем продолжим рекурсию.
 
}}
 
}}
  
Строка 68: Строка 68:
 
|about = № 3
 
|about = № 3
 
|statement =  
 
|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>g</tex> целых чисел, в сумме использующих <tex>\frac{\log n}{2}</tex> бит, упакованы в один контейнер, тогда <tex>n</tex> чисел в <tex>\frac{n}{g}</tex> контейнерах могут быть отсортированы за время <tex>O(\frac{n \log g}{g})</tex> с использованием <tex>O(\frac{n}{g})</tex> памяти.
  
  
 
|proof =  
 
|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>\frac{\log n}{2}</tex> бит в каждом контейнере для хранения <tex>g</tex> чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает <tex>O(\frac{n}{g})</tex> времени и памяти. Так как используется <tex>\frac{\log n}{2}</tex> бит на контейнер, понадобится <tex>\sqrt{n}</tex> шаблонов для всех контейнеров. Затем поместим <tex>g < \frac{\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(\frac{n \log g}{g})</tex>, с использованием <tex>O(\frac{n}{g})</tex> памяти.
  
Для контейнеров вне групп (которых <tex>\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex>O(n/g)</tex> времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex>n</tex> контейнеров. Таким образом, все числа отсортированы.
+
Для контейнеров вне групп (которых <tex>\sqrt{n}(g - 1)</tex> штук) разбираем и собираем заново контейнеры. На это потребуется не более <tex>O(\frac{n}{g})</tex> времени и памяти. После всего этого используем карманную сортировку вновь для сортировки <tex>n</tex> контейнеров. Таким образом, все числа отсортированы.
  
  
Заметим, что когда <tex>g = O( \log n)</tex>, сортировка <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров произойдет за время <tex>O((n/g) \log\log n)</tex> с использованием <tex>O(n/g)</tex> памяти. Выгода очевидна.
+
Заметим, что когда <tex>g = O( \log n)</tex>, сортировка <tex>O(n)</tex> чисел в <tex>\frac{n}{g}</tex> контейнеров произойдет за время <tex>O((\frac{n}{g}) \log\log n)</tex> с использованием <tex>O(\frac{n}{g})</tex> памяти. Выгода очевидна.
 
}}
 
}}
  
Строка 84: Строка 84:
 
|about = № 4
 
|about = № 4
 
|statement =  
 
|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> \log m > \log n</tex> бит, и <tex>g</tex> чисел, в каждом из которых <tex>\frac{\log m}{g}</tex> бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий <tex>\frac{\log n}{2g}</tex> бит, и <tex>g</tex> маркеров упакованы в один контейнер таким же образом<tex>^*</tex>, что и числа, тогда <tex>n</tex> чисел в <tex>\frac{n}{g}</tex> контейнерах могут быть отсортированы по их маркерам за время <tex>O(\frac{n \log\log n}{g})</tex> с использованием <tex>O(\frac{n}{g})</tex> памяти.
 
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
 
(*): если число <tex>a</tex> упаковано как <tex>s</tex>-ое число в <tex>t</tex>-ом контейнере для чисел, тогда маркер для <tex>a</tex> упакован как <tex>s</tex>-ый маркер в <tex>t</tex>-ом контейнере для маркеров.
  
  
 
|proof =  
 
|proof =  
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>( \log n)/2</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.
+
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует <tex>\frac{\log n}{2}</tex> бит. Сортировка сгруппирует контейнеры для чисел как в [[#lemma3|лемме №3]]. Перемещаем каждую группу контейнеров для чисел.
 
}}
 
}}
  
Строка 96: Строка 96:
 
|about = № 5
 
|about = № 5
 
|statement =
 
|statement =
Предположим, что каждый контейнер содержит <tex>\log m \log\log n > \log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>(\log m)/g</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>(\log n)/(2g)</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <tex>n</tex> чисел в <tex>n/g</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(n/g)</tex> с использованием <tex>O(n/g)</tex> памяти.
+
Предположим, что каждый контейнер содержит <tex>\log m \log\log n > \log n</tex> бит, что <tex>g</tex> чисел, в каждом из которых <tex>\frac{\log m}{g}</tex> бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий <tex>\frac{\log n}{2g}</tex> бит, и что <tex>g</tex> маркеров упакованы в один контейнер тем же образом что и числа. Тогда <tex>n</tex> чисел в <tex>\frac{n}{g}</tex> контейнерах могут быть отсортированы по своим маркерам за время <tex>O(\frac{n}{g})</tex> с использованием <tex>O(\frac{n}{g})</tex> памяти.
  
 
|proof =  
 
|proof =  
Заметим, что несмотря на то, что длина контейнера <tex>\log m \log\log n</tex> бит, всего <tex>\log m</tex> бит используется для хранения упакованных чисел. Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью 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> бит используется для хранения упакованных чисел. Так же как в [[#lemma3|лемме №3]] и [[#lemma4|лемме №4]] сортируем контейнеры упакованных маркеров с помощью 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(\frac{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> чисел в один контейнер, тогда выбор в [[#lemma2|лемме №2]] может быть сделан за время и память <tex>O(n/g)</tex>, потому что упаковка в доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <tex>O(n/g)</tex>.
+
Заметим, что если длина контейнера <tex>\log m \log\log n</tex> и только <tex>\log m</tex> бит используется для упаковки <tex>g \leqslant \log n</tex> чисел в один контейнер, тогда выбор в [[#lemma2|лемме №2]] может быть сделан за время и память <tex>O(\frac{n}{g})</tex>, потому что упаковка в доказательстве [[#lemma2|лемме №2]] теперь может быть сделана за время <tex>O(\frac{n}{g})</tex>.
 
}}
 
}}
  
Строка 110: Строка 110:
 
|about = № 6
 
|about = № 6
 
|statement =  
 
|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>.
+
<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} < S_{j}</tex> при <tex>i < j</tex>, за время <tex>O(\frac{n \log\log n} {\log k})</tex> и место <tex>O(n)</tex> с неконсервативным преимуществом <tex>k \log\log n</tex>.
  
  
Строка 119: Строка 119:
  
  
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <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>-уровневый алгоритм, который работает следующим образом:
+
Рассмотрим проблему сортировки <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> в <tex>\sqrt{n}</tex> наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит <tex>k \log\log n \log m</tex> бит и хранит число в <tex>\log m</tex> бит. Поэтому неконсервативное преимущество {{---}} <tex>k \log \log n</tex>. Также предполагаем, что <tex>\log m \geqslant \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>\frac{i \log m} {\log n}</tex>-ого по <tex>(\frac{(i + 1) \log m} {\log n - 1})</tex>-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется <tex>2 \log n</tex>-уровневый алгоритм, который работает следующим образом:
  
  
На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только <tex>\log m/ \log n</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>n/ \log n</tex> контейнеров с <tex>\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По [[#lemma2|лемме №2]] находим медиану этих <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>\frac{\log m}{\log n}</tex> бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер <tex>\log n - 1</tex>). Предполагаем, что биты этих м.ч. упакованы в <tex>\frac{n}{\log n}</tex> контейнеров с <tex>\log n</tex> м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По [[#lemma2|лемме №2]] находим медиану этих <tex>n</tex> м.ч. за время и память <tex>O(\frac{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>\frac{\log m}{\log n}</tex> бит (наибольший блок) из каждого числа, принадлежащего <tex>S'_{2}</tex>. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только <tex>\log n</tex> блоков, для каждого числа потребуется не более <tex>\log n</tex> стадий, чтобы поместить его в набор половинного размера. За <tex>2 \log n</tex> стадий все числа будут отсортированы. Так как на каждой стадии работаем с <tex>\frac{n}{\log n}</tex> контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается <tex>O(n)</tex> времени из-за <tex>2 \log n</tex> стадий.
  
  
Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <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> для [[#lemma5|лемме №5]] Поэтому предполагается, что <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> бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O((n \log e)/ \log n)</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <tex>O((n \log e)/ \log n)</tex>.
+
Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что <tex>n</tex> чисел уже поделены в <tex>e</tex> наборов. Используем <tex>\log e</tex> битов чтобы сделать марки для каждого набора. Теперь используем [[#lemma5|лемме №5]]. Полный размер маркера для каждого контейнера должен быть <tex>\frac{\log n}{2}</tex>, и маркер использует <tex>\log e</tex> бит, значит количество маркеров <tex>g</tex> в каждом контейнере должно быть не более <tex>\frac{\log n}{2\log e}</tex>. В дальнейшем, так как <tex>g = \frac{\log n}{2 \log e}</tex>, м.ч. должны влезать в контейнер. Каждый контейнер содержит <tex>k \log\log n \log n</tex> блоков, каждое м.ч. может содержать <tex>O(\frac{k \log n}{g}) = O(k \log e)</tex> блоков. Заметим, что используется неконсервативное преимущество в <tex>\log\log n</tex> для [[#lemma5|лемме №5]] Поэтому предполагается, что <tex>\frac{\log n}{2 \log e}</tex> м.ч., в каждом из которых <tex>k \log e</tex> блоков битов числа, упакованны в один контейнер. Для каждого м.ч. используется маркер из <tex>\log e</tex> бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит <tex>\frac{\log n}{2 \log e}</tex> маркеров, то для каждого контейнера требуется <tex>\frac{\log n}{2}</tex> бит. Таким образом, [[#lemma5|лемма №5]] может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется <tex>O(\frac{n \log e}{ \log n})</tex> контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно <tex>O(\frac{n \log e}{ \log n})</tex>.
  
 
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].
 
Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из [[#lemma5|леммы №5]].
Строка 138: Строка 139:
  
  
Собственно алгоритм:
+
===Алгоритм сортировки===
 
 
  
 
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>)
 
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>)
Строка 145: Строка 145:
 
<tex>k \log\log n</tex> {{---}} это неконсервативное преимущество, <tex>a_{i}</tex>-ые это входящие целые числа в наборе, которые надо отсортировать, <tex>level</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 набора, используя [[#lemma2|лемму №2]], чтобы найти медиану, а затем используем [[#lemma5|лемму №5]] для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
+
# Если <tex>(level == 1)</tex> тогда изучаем размер набора. Если размер меньше или равен <tex>\sqrt{n}</tex>, то <tex>return</tex>. Иначе делим этот набор в <tex>\leqslant</tex> 3 набора, используя [[#lemma2|лемму №2]], чтобы найти медиану, а затем используем [[#lemma5|лемму №5]] для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
 
# От <tex>u = 1</tex> до <tex>k</tex>
 
# От <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> текущий блок это самый крупный блок.
+
## Упаковываем <tex>a^{(u)}_{i}</tex>-ый в часть из <tex>1/k</tex>-ых номеров контейнеров. Где <tex>a^{(u)}_{i}</tex> содержит несколько непрерывных блоков, которые состоят из <tex>\frac{1}{k}</tex>-ых битов <tex>a_{i}</tex>. При этом у <tex>a^{(u)}_{i}</tex> текущий блок это самый крупный блок.
 
## Вызываем Sort(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{0}</tex>, <tex>a^{(u)}_{1}</tex>, <tex>\ldots</tex>, <tex>a^{(u)}_{t}</tex>). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в <tex>a_{i}</tex>, показывающее на текущий блок в нем, так же направлено назад к <tex>a_{i}</tex>.
 
## Вызываем Sort(<tex>k \log\log n</tex>, <tex>level - 1</tex>, <tex>a^{(u)}_{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>-ые к их наборам, используя [[#lemma5|лемму №5]].
 
## Отправляем <tex>a_{i}</tex>-ые к их наборам, используя [[#lemma5|лемму №5]].
Строка 156: Строка 156:
 
от 1 до 5
 
от 1 до 5
 
# Помещаем <tex>a_{i}</tex> в соответствующий набор с помощью bucket sort, потому что наборов около <tex>\sqrt{n}</tex>.
 
# Помещаем <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>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}(\frac{\log n}{4})</tex>, <tex>a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}</tex>).
  
Время работы алгоритма <tex>O(n \log\log n/ \log k)</tex>, что доказывает лемму.
+
Время работы алгоритма <tex>O(\frac{n \log\log n}{\log k})</tex>, что доказывает лемму.
 
}}
 
}}
  
Строка 167: Строка 167:
  
  
Алгоритм: Пусть целое число <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>.
+
Алгоритм: Пусть целое число <tex>b \geqslant 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]].
 
Данный алгоритм базируется на [[#lemma1|лемме №1]].
Строка 183: Строка 183:
  
  
Также рассмотрим проблему последующего разделения. Пусть <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> бит.
+
Также рассмотрим проблему последующего разделения. Пусть <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} < a_{1} < S_{1} < a_{2} < \ldots < a_{p} < 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>\frac{\log m}{h}</tex> бит.
  
  
Строка 195: Строка 195:
 
Использование '''signature sorting''' в данном алгоритме:
 
Использование '''signature sorting''' в данном алгоритме:
  
Есть набор <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>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 = \frac{\log n}{c \log p}</tex> для константы <tex>c > 1</tex>. (<tex>\frac{h}{\log\log n \log p}</tex>)-битные числа могут храниться в одном контейнере, содержащим <tex>\frac{\log n}{c \log\log n}</tex> бит. Сначала рассматриваем биты в каждом <tex>a_{i}</tex> и каждом <tex>b_{i}</tex> как сегменты одинаковой длины <tex>\frac{h} {\log\log n}</tex>. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах (<tex>a_{i}</tex>-ом и <tex>b_{i}</tex>-ом) хешируются, и получается <tex>\frac{h}{\log\log n}</tex> хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть <tex>a'_{i}</tex> {{---}} хеш-контейнер для <tex>a_{i}</tex>, аналогично <tex>b'_{i}</tex>. В сумме хеш-значения имеют <tex>\frac{2 \log n}{c \log\log n}</tex> бит, хотя эти значения разделены на сегменты по <tex>\frac{h}{ \log\log n}</tex> бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в <tex>\frac{2 \log n}{c \log\log n}</tex> бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в <tex>a_{i}</tex> и <tex>b_{i}</tex> разрезаны на <tex>\frac{\log\log n}{h}</tex> сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в <tex>\frac{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>g</tex> раз, получится неконсервативное преимущество в <tex>(\frac{h} {\log\log n})^g</tex> раз, в то время как потрачено только <tex>O(gqt)</tex> времени, так как каждое многократное деление происходит за линейное время <tex>O(qt)</tex>.
  
  
Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, <tex>\log\log n/h</tex>-ые, <tex>(\log\log n/h)^2</tex>-ые, <tex>\ldots</tex> по счету в числе. Хеш-функцию для <tex>(\log\log n/h)^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\log\log n/h)^t</tex> сегментов. Рассматривая каждый сегмент как число, получаем <tex>p(\log\log n/h)^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex>t < \log n</tex>, то получится не более <tex>\log n</tex> хеш-функций.
+
Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, <tex>\frac{\log\log n}{h}</tex>-ые, <tex>(\frac{\log\log n}{h})^2</tex>-ые, <tex>\ldots</tex> по счету в числе. Хеш-функцию для <tex>(\frac{\log\log n}{h})^t</tex>-ых по счету сегментов, получаем нарезанием всех <tex>p</tex> чисел на <tex>(\frac{\log\log n}{h})^t</tex> сегментов. Рассматривая каждый сегмент как число, получаем <tex>p(\frac{\log\log n}{h})^t</tex> чисел. Затем получаем одну хеш-функцию для этих чисел. Так как <tex>t < \log n</tex>, то получится не более <tex>\log n</tex> хеш-функций.
  
  
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <tex>(2 \log n)/(c \log\log n)</tex> бит. Есть <tex>t</tex> наборов, в каждом из которых <tex>q + p</tex> хешированных контейнеров по <tex>(2 \log n)/(c \log\log n)</tex> бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
+
Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в <tex>\frac{2 \log n}{c \log\log n}</tex> бит. Есть <tex>t</tex> наборов, в каждом из которых <tex>q + p</tex> хешированных контейнеров по <tex>\frac{2 \log n}{c \log\log n}</tex> бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.
  
  
 
Procedure '''Linear-Time-Sort'''
 
Procedure '''Linear-Time-Sort'''
  
Входные данные: <tex>r > = n^{2/5}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}.value</tex> — значение числа <tex>d_{i}</tex>, в котором <tex>(2 \log n)/(c \log\log n)</tex> бит, <tex>d_{i}.set</tex> — набор, в котором находится <tex>d_{i}</tex>. Следует отметить, что всего есть <tex>t</tex> наборов.
+
Входные данные: <tex>r > = n^{\frac{2}{5}}</tex> чисел <tex>d_{i}</tex>, <tex>d_{i}.value</tex> — значение числа <tex>d_{i}</tex>, в котором <tex>\frac{2 \log n}{c \log\log n}</tex> бит, <tex>d_{i}.set</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>d_{i}</tex> по <tex>d_{i}.value</tex>, используя bucket sort. Пусть все отртированные числа в <tex>A[1..r]</tex>. Этот шаг занимает линейное время, так как сортируется не менее <tex>n^{\frac{2}{5}}</tex> чисел.
 
# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</tex>.
 
# Помещаем все <tex>A[j]</tex> в <tex>A[j].set</tex>.
  
Строка 217: Строка 217:
  
  
Берем <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>1/e = 5</tex> для ЭП-дерева Андерссона. Следовательно, у корня будет <tex>n^{\frac{1}{5}}</tex> детей, и каждое ЭП-дерево в каждом ребенке будет иметь <tex>n^{\frac{4}{5}}</tex> листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а <tex>d^2</tex>, где <tex>d</tex> — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все <tex>d^2</tex> чисел на один уровень. В корне опускаются <tex>n^{\frac{2}{5}}</tex> чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на <tex>t_{1} = n^{1/5}</tex> наборов <tex>S_{1}, S_{2}, \ldots, S_{t_{1}}</tex>, в каждом из которых <tex>n^{\frac{4}{5}}</tex> чисел и <tex>S_{i} < S_{j}, i < j</tex>. Затем, берутся <tex>n^{\frac{8}{25}}</tex> чисел из <tex>S_{i}</tex> и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на <tex>t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}</tex> наборов <tex>T_{1}, T_{2}, \ldots, T_{t_{2}}</tex>, аналогичных наборам <tex>S_{i}</tex>, в каждом из которых <tex>n^{\frac{16}{25}}</tex> чисел. Теперь числа опускаются дальше в ЭП-дереве.
  
 
Нетрудно заметить, что перебалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</tex> времени на уровень, аналогично стандартному ЭП-дереву Андерссона.
 
Нетрудно заметить, что перебалансирока занимает <tex>O(n \log\log n)</tex> времени с <tex>O(n)</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> чисел для всех наборов за один раз.
+
Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне <tex>s</tex>. Имеется <tex>t = n^{1 - (\frac{4}{5})^s}</tex> наборов по <tex>n^{(\frac{4}{5})^s}</tex> чисел в каждом. Так как каждый узел на данном уровне имеет <tex>p = n^{\frac{1}{5} \cdot (\frac{4}{5})^s}</tex> детей, то на <tex>s + 1</tex> уровень опускаются <tex>q = n^{\frac{2}{5} \cdot (\frac{4}{5})^s}</tex> чисел для каждого набора, или всего <tex>qt \geqslant n^{\frac{2}{5}}</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>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} < a_{1} < \ldots < a_{p} < S_{p}</tex>.
  
  
Строка 231: Строка 231:
  
  
После <tex>g</tex> сокращений бит в  [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в <tex>(h/ \log\log n)^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на [[#lemma6|лемму №6]] для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</tex>.
+
После <tex>g</tex> сокращений бит в  [[Сортировка Хана#Signature sorting|signature sorting]] получаем неконсервативное преимущество в <tex>(\frac{h}{ \log\log n})^g</tex>. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на [[#lemma6|лемму №6]] для завершения разделения <tex>q</tex> чисел с помощью <tex>p</tex> чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в <tex>w</tex> подзадач разделения на <tex>w</tex> поднаборов для какого-то числа <tex>w</tex>.
  
  
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma6|лемму №6]], делается разделение. Так как получено неконсервативное преимущество в <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> времени.
+
Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя [[#lemma6|лемму №6]], делается разделение. Так как получено неконсервативное преимущество в <tex>(\frac{h}{\log\log n})^g</tex> и работа происходит на уровнях не ниже, чем <tex>2 \log\log\log n</tex>, то алгоритм занимает <tex>O(\frac{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>q</tex> чисел <tex>p</tex> числами в каждый набор. То есть получилось, что <tex>S_{0} < e_{1} < S_{1} < \ldots < e_{p} < 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>.  
  
  
Строка 245: Строка 245:
  
  
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <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_{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> контейнеров. Считаем, что время, потраченное на один контейнер — константа.
+
Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере <tex>\log m \geqslant \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_{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> контейнеров. Считаем, что время, потраченное на один контейнер — константа.
  
 
==См. также==
 
==См. также==
Строка 255: Строка 255:
 
* А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)
 
* А. Андерссон. Fast deterministic sorting and searching in linear space. Proc. 1996 IEEE Symp. on Foundations of Computer Science. 135-141(1996)
 
* [http://dl.acm.org/citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]
 
* [http://dl.acm.org/citation.cfm?id=1236460 A. Andersson, M. Thorup. Dynamic ordered sets with exponential search trees.]
* [[wikipedia:en:Integer_sorting|Wikipedia {{---}} Integer sorting]]
+
* [[wikipedia:en:Integer_sorting|Integer_sorting]]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Сортировки]]
 
[[Категория: Сортировки]]
 +
}}

Версия 15:05, 9 июня 2014

Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью [math]O(n \log\log n)[/math], где [math]n[/math] — количество элементов для сортировки.

Данная статья писалась на основе брошюры Хана, посвященной этой сортировке.

Описание

Алгоритм построен на основе экспоненциального поискового дерева (далее — ЭП-дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в ЭП-дерево.

Andersson's exponential search tree

Определение:
ЭП-дерево - это дерево поиска, в котором все ключи хранятся в листьях этого дерева и количество детей у каждого узла уменьшается экспоненциально от глубины узла.


Общая структура ЭП-дерева

Структура ЭП-дерева:

1) Корень имеет [math]\Theta (n^e)[/math] сыновей ([math] 0 \lt e \lt 1 [/math]). Все сыновья являются ЭП-деревьями.

2) Каждое поддерево корня имеет [math]\Theta(n^{1-e})[/math] сыновей.

В этом дереве [math]O(n \log\log n)[/math] уровней. При нарушении баланса дерева необходимо балансирование, которое требует [math]O(n \log\log n)[/math] времени при [math]n[/math] вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не поодиночке, как изначально предлагал Андерссон.

Определения

Определение:
Контейнер — объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.


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


Определение:
Если сортируются целые числа из множества [math]\{0, 1, \ldots, m - 1\}[/math] с длиной контейнера [math]k \log (m + n)[/math] с [math]k[/math] [math]\geqslant[/math] 1, тогда сортировка происходит с неконсервативным преимуществом [math]k[/math].


Определение:
Для множества [math]S[/math] определим

[math]\min(S) = \min\limits_{a \in S} a[/math]

[math]\max(S) = \max\limits_{a \in S} a[/math]

Набор [math]S1 \lt S2[/math] если [math]\max(S1) \leqslant \min(S2)[/math]


Определение:
Предположим, есть набор [math]T[/math] из [math]p[/math] чисел, которые уже отсортированы как [math]a_{1}, a_{2}, \ldots, a_{p}[/math] и набор [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, \ldots, b_{q}[/math]. Тогда разделением [math]q[/math] чисел [math]p[/math] числами называется [math]p + 1[/math] набор [math]S_{0}, S_{1}, \ldots, S_{p}[/math], где [math]S_{0} \lt a_{1} \lt S_{1} \lt \ldots \lt a_{p} \lt S_{p}[/math].


Леммы

Лемма (№ 1):
Даны целые числа [math]b[/math] [math]\geqslant[/math] [math]s[/math] [math]\geqslant[/math] 0, и [math]T[/math] является подмножеством множества [math]\{0, \ldots, 2^b - 1\}[/math], содержащим [math]n[/math] элементов, и [math]t[/math] [math]\geqslant[/math] [math]2^{-s + 1}[/math]С[math]^k_{n}[/math]. Функция [math]h_{a}[/math], принадлежащая [math]H_{b,s}[/math], может быть выбрана за время [math]O(bn^2)[/math] так, что количество коллизий [math]coll(h_{a}, T)[/math] [math]\leqslant[/math] [math]t[/math].
Лемма (№ 2):
Выбор [math]s[/math]-ого наибольшего числа среди [math]n[/math] чисел, упакованных в [math]\frac{n}{g}[/math] контейнеров, может быть сделан за время [math]O(\frac{n \log g}{g})[/math] и с использованием [math]O(\frac{n}{g})[/math] памяти. В том числе, так может быть найдена медиана.
Доказательство:
[math]\triangleright[/math]
Так как возможно делать попарное сравнение [math]g[/math] чисел в одном контейнере с [math]g[/math] числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, [math]\ldots[/math], [math]g[/math]-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор [math]S[/math] из медиан теперь содержится в [math]\frac{n}{5g}[/math] контейнерах. Рекурсивно находим медиану [math]m[/math] в [math]S[/math]. Используя [math]m[/math], уберем хотя бы [math]\frac{n}{4}[/math] чисел среди [math]n[/math]. Затем упакуем оставшиеся из [math]\frac{n}{g}[/math] контейнеров в [math]\frac{3n}{4g}[/math] контейнеров и затем продолжим рекурсию.
[math]\triangleleft[/math]
Лемма (№ 3):
Если [math]g[/math] целых чисел, в сумме использующих [math]\frac{\log n}{2}[/math] бит, упакованы в один контейнер, тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы за время [math]O(\frac{n \log g}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Так как используется только [math]\frac{\log n}{2}[/math] бит в каждом контейнере для хранения [math]g[/math] чисел, используем bucket sort, чтобы отсортировать все контейнеры, представляя каждый как число, что занимает [math]O(\frac{n}{g})[/math] времени и памяти. Так как используется [math]\frac{\log n}{2}[/math] бит на контейнер, понадобится [math]\sqrt{n}[/math] шаблонов для всех контейнеров. Затем поместим [math]g \lt \frac{\log n}{2}[/math] контейнеров с одинаковым шаблоном в одну группу. Для каждого шаблона останется не более [math]g - 1[/math] контейнеров, которые не смогут образовать группу. Поэтому не более [math]\sqrt{n}(g - 1)[/math] контейнеров не смогут сформировать группу. Для каждой группы помещаем [math]i[/math]-е число во всех [math]g[/math] контейнерах в один. Таким образом берутся [math]g[/math] [math]g[/math]-целых векторов и получаются [math]g[/math] [math]g[/math]-целых векторов, где [math]i[/math]-ый вектор содержит [math]i[/math]-ое число из входящего вектора. Эта транспозиция может быть сделана за время [math]O(g \log g)[/math], с использованием [math]O(g)[/math] памяти. Для всех групп это занимает время [math]O(\frac{n \log g}{g})[/math], с использованием [math]O(\frac{n}{g})[/math] памяти.

Для контейнеров вне групп (которых [math]\sqrt{n}(g - 1)[/math] штук) разбираем и собираем заново контейнеры. На это потребуется не более [math]O(\frac{n}{g})[/math] времени и памяти. После всего этого используем карманную сортировку вновь для сортировки [math]n[/math] контейнеров. Таким образом, все числа отсортированы.


Заметим, что когда [math]g = O( \log n)[/math], сортировка [math]O(n)[/math] чисел в [math]\frac{n}{g}[/math] контейнеров произойдет за время [math]O((\frac{n}{g}) \log\log n)[/math] с использованием [math]O(\frac{n}{g})[/math] памяти. Выгода очевидна.
[math]\triangleleft[/math]
Лемма (№ 4):
Примем, что каждый контейнер содержит [math] \log m \gt \log n[/math] бит, и [math]g[/math] чисел, в каждом из которых [math]\frac{\log m}{g}[/math] бит, упакованы в один контейнер. Если каждое число имеет маркер, содержащий [math]\frac{\log n}{2g}[/math] бит, и [math]g[/math] маркеров упакованы в один контейнер таким же образом[math]^*[/math], что и числа, тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы по их маркерам за время [math]O(\frac{n \log\log n}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти. (*): если число [math]a[/math] упаковано как [math]s[/math]-ое число в [math]t[/math]-ом контейнере для чисел, тогда маркер для [math]a[/math] упакован как [math]s[/math]-ый маркер в [math]t[/math]-ом контейнере для маркеров.
Доказательство:
[math]\triangleright[/math]
Контейнеры для маркеров могут быть отсортированы с помощью bucket sort потому, что каждый контейнер использует [math]\frac{\log n}{2}[/math] бит. Сортировка сгруппирует контейнеры для чисел как в лемме №3. Перемещаем каждую группу контейнеров для чисел.
[math]\triangleleft[/math]
Лемма (№ 5):
Предположим, что каждый контейнер содержит [math]\log m \log\log n \gt \log n[/math] бит, что [math]g[/math] чисел, в каждом из которых [math]\frac{\log m}{g}[/math] бит, упакованы в один контейнер, что каждое число имеет маркер, содержащий [math]\frac{\log n}{2g}[/math] бит, и что [math]g[/math] маркеров упакованы в один контейнер тем же образом что и числа. Тогда [math]n[/math] чисел в [math]\frac{n}{g}[/math] контейнерах могут быть отсортированы по своим маркерам за время [math]O(\frac{n}{g})[/math] с использованием [math]O(\frac{n}{g})[/math] памяти.
Доказательство:
[math]\triangleright[/math]

Заметим, что несмотря на то, что длина контейнера [math]\log m \log\log n[/math] бит, всего [math]\log m[/math] бит используется для хранения упакованных чисел. Так же как в лемме №3 и лемме №4 сортируем контейнеры упакованных маркеров с помощью bucket sort. Для того, чтобы перемещать контейнеры чисел, помещаем [math]g \log\log n[/math] вместо [math]g[/math] контейнеров чисел в одну группу. Для транспозиции чисел в группе, содержащей [math]g \log\log n[/math] контейнеров, упаковываем [math]g \log\log n[/math] контейнеров в [math]g[/math], упаковывая [math]\log\log n[/math] контейнеров в один. Далее делаем транспозицию над [math]g[/math] контейнерами. Таким образом перемещение занимает всего [math]O(g \log\log n)[/math] времени для каждой группы и [math]O(\frac{n}{g})[/math] времени для всех чисел. После завершения транспозиции, распаковываем [math]g[/math] контейнеров в [math]g \log\log n[/math] контейнеров.


Заметим, что если длина контейнера [math]\log m \log\log n[/math] и только [math]\log m[/math] бит используется для упаковки [math]g \leqslant \log n[/math] чисел в один контейнер, тогда выбор в лемме №2 может быть сделан за время и память [math]O(\frac{n}{g})[/math], потому что упаковка в доказательстве лемме №2 теперь может быть сделана за время [math]O(\frac{n}{g})[/math].
[math]\triangleleft[/math]


Лемма (№ 6):
[math]n[/math] целых чисел можно отсортировать в [math]\sqrt{n}[/math] наборов [math]S_{1}[/math], [math]S_{2}[/math], [math]\ldots[/math], [math]S_{\sqrt{n}}[/math] таким образом, что в каждом наборе [math]\sqrt{n}[/math] чисел и [math]S_{i} \lt S_{j}[/math] при [math]i \lt j[/math], за время [math]O(\frac{n \log\log n} {\log k})[/math] и место [math]O(n)[/math] с неконсервативным преимуществом [math]k \log\log n[/math].
Доказательство:
[math]\triangleright[/math]

Алгоритм сортировки [math]n[/math] целых чисел в [math]\sqrt{n}[/math] наборов, представленный ниже, является доказательством данной леммы.

Постановка задачи и решение некоторых проблем:


Рассмотрим проблему сортировки [math]n[/math] целых чисел из множества [math]\{0, 1, \ldots, m - 1\}[/math] в [math]\sqrt{n}[/math] наборов, как в условии леммы. Предполагаем, что каждый контейнер содержит [math]k \log\log n \log m[/math] бит и хранит число в [math]\log m[/math] бит. Поэтому неконсервативное преимущество — [math]k \log \log n[/math]. Также предполагаем, что [math]\log m \geqslant \log n \log\log n[/math]. Иначе можно использовать radix sort для сортировки за время [math]O(n \log\log n)[/math] и линейную память. Делим [math]\log m[/math] бит, используемых для представления каждого числа, в [math]\log n[/math] блоков. Таким образом, каждый блок содержит как минимум [math]\log\log n[/math] бит. [math]i[/math]-ый блок содержит с [math]\frac{i \log m} {\log n}[/math]-ого по [math](\frac{(i + 1) \log m} {\log n - 1})[/math]-ый биты. Биты считаются с наименьшего бита, начиная с нуля. Теперь у нас имеется [math]2 \log n[/math]-уровневый алгоритм, который работает следующим образом:


На каждой стадии работаем с одним блоком бит. Назовем эти блоки маленькими числами (далее м.ч.), потому что каждое м.ч. теперь содержит только [math]\frac{\log m}{\log n}[/math] бит. Каждое число представлено и соотносится с м.ч., над которым работаем в данный момент. Положим, что нулевая стадия работает с самым большим блоком (блок номер [math]\log n - 1[/math]). Предполагаем, что биты этих м.ч. упакованы в [math]\frac{n}{\log n}[/math] контейнеров с [math]\log n[/math] м.ч. упакованными в один контейнер. Пренебрегая временем, потраченным на эту упаковку, считаем, что она бесплатна. По лемме №2 находим медиану этих [math]n[/math] м.ч. за время и память [math]O(\frac{n}{\log n})[/math]. Пусть [math]a[/math] — это найденная медиана. Тогда [math]n[/math] м.ч. могут быть разделены на не более чем три группы: [math]S_{1}[/math], [math]S_{2}[/math] и [math]S_{3}[/math]. [math]S_{1}[/math] содержит м.ч., которые меньше [math]a[/math], [math]S_{2}[/math] содержит м.ч., равные [math]a[/math], [math]S_{3}[/math] содержит м.ч., большие [math]a[/math]. Также мощность [math]S_{1}[/math] и [math]S_{3} [/math] не превосходит [math]n/2[/math]. Мощность [math]S_{2}[/math] может быть любой. Пусть [math]S'_{2}[/math] — это набор чисел, у которых наибольший блок находится в [math]S_{2}[/math]. Тогда убираем из дальнейшего рассмотрения [math]\frac{\log m}{\log n}[/math] бит (наибольший блок) из каждого числа, принадлежащего [math]S'_{2}[/math]. Таким образом, после первой стадии каждое число находится в наборе размера не большего половины размера начального набора или один из блоков в числе убран из дальнейшего рассмотрения. Так как в каждом числе только [math]\log n[/math] блоков, для каждого числа потребуется не более [math]\log n[/math] стадий, чтобы поместить его в набор половинного размера. За [math]2 \log n[/math] стадий все числа будут отсортированы. Так как на каждой стадии работаем с [math]\frac{n}{\log n}[/math] контейнерами, то игнорируя время, необходимое на упаковку м.ч. в контейнеры и помещение м.ч. в нужный набор, затрачивается [math]O(n)[/math] времени из-за [math]2 \log n[/math] стадий.


Сложная часть алгоритма заключается в том, как поместить м.ч. в набор, которому принадлежит соответствующее число, после предыдущих операций деления набора в нашем алгоритме. Предположим, что [math]n[/math] чисел уже поделены в [math]e[/math] наборов. Используем [math]\log e[/math] битов чтобы сделать марки для каждого набора. Теперь используем лемме №5. Полный размер маркера для каждого контейнера должен быть [math]\frac{\log n}{2}[/math], и маркер использует [math]\log e[/math] бит, значит количество маркеров [math]g[/math] в каждом контейнере должно быть не более [math]\frac{\log n}{2\log e}[/math]. В дальнейшем, так как [math]g = \frac{\log n}{2 \log e}[/math], м.ч. должны влезать в контейнер. Каждый контейнер содержит [math]k \log\log n \log n[/math] блоков, каждое м.ч. может содержать [math]O(\frac{k \log n}{g}) = O(k \log e)[/math] блоков. Заметим, что используется неконсервативное преимущество в [math]\log\log n[/math] для лемме №5 Поэтому предполагается, что [math]\frac{\log n}{2 \log e}[/math] м.ч., в каждом из которых [math]k \log e[/math] блоков битов числа, упакованны в один контейнер. Для каждого м.ч. используется маркер из [math]\log e[/math] бит, который показывает, к какому набору он принадлежит. Предполагаем, что маркеры так же упакованы в контейнеры, как и м.ч. Так как каждый контейнер для маркеров содержит [math]\frac{\log n}{2 \log e}[/math] маркеров, то для каждого контейнера требуется [math]\frac{\log n}{2}[/math] бит. Таким образом, лемма №5 может быть применена для помещения м.ч. в наборы, которым они принадлежат. Так как используется [math]O(\frac{n \log e}{ \log n})[/math] контейнеров, то время, необходимое для помещения м.ч. в их наборы, равно [math]O(\frac{n \log e}{ \log n})[/math].

Стоит отметить, что процесс помещения нестабилен, т.к. основан на алгоритме из леммы №5.


При таком помещении сразу возникает следующая проблема.

Рассмотрим число [math]a[/math], которое является [math]i[/math]-ым в наборе [math]S[/math]. Рассмотрим блок [math]a[/math] (назовем его [math]a'[/math]), который является [math]i[/math]-ым м.ч. в [math]S[/math]. Когда используется вышеописанный метод перемещения нескольких следующих блоков [math]a[/math] (назовем это [math]a''[/math]) в [math]S[/math], [math]a''[/math] просто перемещен на позицию в наборе [math]S[/math], но не обязательно на позицию [math]i[/math] (где расположен [math]a'[/math]). Если значение блока [math]a'[/math] одинаково для всех чисел в [math]S[/math], то это не создаст проблемы потому, что блок одинаков вне зависимости от того в какое место в [math]S[/math] помещен [math]a''[/math]. Иначе у нас возникает проблема дальнейшей сортировки. Поэтому поступаем следующим образом: На каждой стадии числа в одном наборе работают на общем блоке, который назовем "текущий блок набора". Блоки, которые предшествуют текущему блоку содержат важные биты и идентичны для всех чисел в наборе. Когда помещаем больше бит в набор, последующие блоки помещаются в набор вместе с текущим блоком. Так вот, в вышеописанном процессе помещения предполагается, что самый значимый блок среди [math]k \log e[/math] блоков — это текущий блок. Таким образом, после того, как эти [math]k \log e[/math] блоков помещены в набор, изначальный текущий блок удаляется, потому что известно, что эти [math]k \log e[/math] блоков перемещены в правильный набор, и нам не важно где находился начальный текущий блок. Тот текущий блок находится в перемещенных [math]k \log e[/math] блоках.


Стоит отметить, что после нескольких уровней деления размер наборов станет маленьким. Леммы 3, 4, 5 расчитаны на не очень маленькие наборы. Но поскольку сортируется набор из [math]n[/math] элементов в наборы размера [math]\sqrt{n}[/math], то проблем быть не должно.


Алгоритм сортировки

Algorithm Sort([math]k \log\log n[/math], [math]level[/math], [math]a_{0}[/math], [math]a_{1}[/math], [math]\ldots[/math], [math]a_{t}[/math])

[math]k \log\log n[/math] — это неконсервативное преимущество, [math]a_{i}[/math]-ые это входящие целые числа в наборе, которые надо отсортировать, [math]level[/math] это уровень рекурсии.

  1. Если [math](level == 1)[/math] тогда изучаем размер набора. Если размер меньше или равен [math]\sqrt{n}[/math], то [math]return[/math]. Иначе делим этот набор в [math]\leqslant[/math] 3 набора, используя лемму №2, чтобы найти медиану, а затем используем лемму №5 для сортировки. Для набора, где все элементы равны медиане, не рассматриваем текущий блок и текущим блоком делаем следующий. Создаем маркер, являющийся номером набора для каждого из чисел (0, 1 или 2). Затем направляем маркер для каждого числа назад к месту, где число находилось в начале. Также направляем двубитное число для каждого входного числа, указывающее на текущий блок.
  2. От [math]u = 1[/math] до [math]k[/math]
    1. Упаковываем [math]a^{(u)}_{i}[/math]-ый в часть из [math]1/k[/math]-ых номеров контейнеров. Где [math]a^{(u)}_{i}[/math] содержит несколько непрерывных блоков, которые состоят из [math]\frac{1}{k}[/math]-ых битов [math]a_{i}[/math]. При этом у [math]a^{(u)}_{i}[/math] текущий блок это самый крупный блок.
    2. Вызываем Sort([math]k \log\log n[/math], [math]level - 1[/math], [math]a^{(u)}_{0}[/math], [math]a^{(u)}_{1}[/math], [math]\ldots[/math], [math]a^{(u)}_{t}[/math]). Когда алгоритм возвращается из этой рекурсии, маркер, показывающий для каждого числа, к какому набору это число относится, уже направлен назад к месту, где число находится во входных данных. Число, имеющее наибольшее число бит в [math]a_{i}[/math], показывающее на текущий блок в нем, так же направлено назад к [math]a_{i}[/math].
    3. Отправляем [math]a_{i}[/math]-ые к их наборам, используя лемму №5.

Algorithm IterateSort Call Sort([math]k \log\log n[/math], [math]\log_{k}((\log n)/4)[/math], [math]a_{0}[/math], [math]a_{1}[/math], [math]\ldots[/math], [math]a_{n - 1}[/math]);

от 1 до 5

  1. Помещаем [math]a_{i}[/math] в соответствующий набор с помощью bucket sort, потому что наборов около [math]\sqrt{n}[/math].
  2. Для каждого набора [math]S = [/math]{[math]a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}[/math]}, если [math]t \gt \sqrt{n}[/math], вызываем Sort([math]k \log\log n[/math], [math]\log_{k}(\frac{\log n}{4})[/math], [math]a_{i_{0}}, a_{i_{1}}, \ldots, a_{i_{t}}[/math]).
Время работы алгоритма [math]O(\frac{n \log\log n}{\log k})[/math], что доказывает лемму.
[math]\triangleleft[/math]


Уменьшение числа бит в числах

Один из способов ускорить сортировку — уменьшить число бит в числе. Один из способов уменьшить число бит в числе — использовать деление пополам (эту идею впервые подал van Emde Boas). Деление пополам заключается в том, что количество оставшихся бит в числе уменьшается в 2 раза. Это быстрый способ, требующий [math]O(m)[/math] памяти. Для своего дерева Андерссон использует хеширование, что позволяет сократить количество памяти до [math]O(n)[/math]. Для того чтобы еще ускорить алгоритм, необходимо упаковать несколько чисел в один контейнер, чтобы затем за константное количество шагов произвести хеширование для всех чисел, хранимых в контейнере. Для этого используется хеш-функция для хеширования [math]n[/math] чисел в таблицу размера [math]O(n^2)[/math] за константное время без коллизий. Для этого используется модифицированная хеш-функция авторства: Dierzfelbinger и Raman.


Алгоритм: Пусть целое число [math]b \geqslant 0[/math] и пусть [math]U = \{0, \ldots, 2^b - 1\}[/math]. Класс [math]H_{b,s}[/math] хеш-функций из [math]U[/math] в [math]\{0, \ldots, 2^s - 1\}[/math] определен как [math]H_{b,s} = \{h_{a} \mid 0 \lt a \lt 2^b, a \equiv 1 (\bmod 2)\}[/math] и для всех [math]x[/math] из [math]U[/math]: [math]h_{a}(x) = (ax[/math] [math]\bmod[/math] [math]2^b)[/math] [math]div[/math] [math]2^{b - s}[/math].

Данный алгоритм базируется на лемме №1.


Взяв [math]s = 2 \log n[/math], получаем хеш-функцию [math]h_{a}[/math], которая захеширует [math]n[/math] чисел из [math]U[/math] в таблицу размера [math]O(n^2)[/math] без коллизий. Очевидно, что [math]h_{a}(x)[/math] может быть посчитана для любого [math]x[/math] за константное время. Если упаковать несколько чисел в один контейнер так, что они разделены несколькими битами нулей, то можно применить [math]h_{a}[/math] ко всему контейнеру, и в результате все хеш-значения для всех чисел в контейнере будут посчитаны. Заметим, что это возможно только потому, что в вычисление хеш-значения вовлечены только ([math]\bmod[/math] [math]2^b[/math]) и ([math]div[/math] [math]2^{b - s}[/math]).


Такая хеш-функция может быть найдена за [math]O(n^3)[/math].

Следует отметить, что, несмотря на размер таблицы [math]O(n^2)[/math], потребность в памяти не превышает [math]O(n)[/math], потому что хеширование используется только для уменьшения количества бит в числе.

Signature sorting

Предположим, что [math]n[/math] чисел должны быть отсортированы, и в каждом [math]\log m[/math] бит. Будем считаем, что в каждом числе есть [math]h[/math] сегментов, в каждом из которых [math]\log m/h[/math] бит. Теперь применяем хеширование ко всем сегментам и получаем [math]2h \log n[/math] бит хешированных значений для каждого числа. После сортировки на хешированных значениях для всех начальных чисел начальная задача по сортировке [math]n[/math] чисел по [math]\log m[/math] бит в каждом стала задачей по сортировке [math]n[/math] чисел по [math]\log m/h[/math] бит в каждом.


Также рассмотрим проблему последующего разделения. Пусть [math]a_{1}[/math], [math]a_{2}[/math], [math]\ldots[/math], [math]a_{p}[/math][math]p[/math] чисел и [math]S[/math] — множество чисeл. Необходимо разделить [math]S[/math] в [math]p + 1[/math] наборов, таких, что: [math]S_{0} \lt a_{1} \lt S_{1} \lt a_{2} \lt \ldots \lt a_{p} \lt S_{p}[/math]. Так как используется signature sorting то перед тем, как делать вышеописанное разделение, необходимо поделить биты в [math]a_{i}[/math] на [math]h[/math] сегментов и взять некоторые из них. Так же делим биты для каждого числа из [math]S[/math] и оставляем только один в каждом числе. По существу, для каждого [math]a_{i}[/math] берутся все [math]h[/math] сегментов. Если соответствующие сегменты [math]a_{i}[/math] и [math]a_{j}[/math] совпадают, то нам понадобится только один. Сегмент, который берется для числа в [math]S[/math] это сегмент, который выделяется из [math]a_{i}[/math]. Таким образом, начальная задача о разделении [math]n[/math] чисел по [math]\log m[/math] бит преобразуется в несколько задач на разделение с числами по [math]\frac{\log m}{h}[/math] бит.


Пример:

[math]a_{1}[/math] = 3, [math]a_{2}[/math] = 5, [math]a_{3}[/math] = 7, [math]a_{4}[/math] = 10, S = [math]\{1, 4, 6, 8, 9, 13, 14\}[/math].

Делим числа на 2 сегмента. Для [math]a_{1}[/math] получим верхний сегмент 0, нижний 3; [math]a_{2}[/math] — верхний 1, нижний 1; [math]a_{3}[/math] — верхний 1, нижний 3; [math]a_{4}[/math] — верхний 2, нижний 2. Для элементов из S получим: для 1 нижний 1, так как он выделяется из нижнего сегмента [math]a_{1}[/math]; для 4 нижний 0; для 8 нижний 0; для 9 нижний 1; для 13 верхний 3; для 14 верхний 3. Теперь все верхние сегменты, нижние сегменты 1 и 3, нижние сегменты 4, 5, 6, 7, нижние сегменты 8, 9, 10 формируют 4 новые задачи на разделение.


Использование signature sorting в данном алгоритме:

Есть набор [math]T[/math] из [math]p[/math] чисел, которые отсортированы как [math]a_{1}, a_{2}, \ldots, a_{p}[/math]. Используем числа в [math]T[/math] для разделения набора [math]S[/math] из [math]q[/math] чисел [math]b_{1}, b_{2}, \ldots, b_{q}[/math] в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, \ldots, S_{p}[/math]. Пусть [math]h = \frac{\log n}{c \log p}[/math] для константы [math]c \gt 1[/math]. ([math]\frac{h}{\log\log n \log p}[/math])-битные числа могут храниться в одном контейнере, содержащим [math]\frac{\log n}{c \log\log n}[/math] бит. Сначала рассматриваем биты в каждом [math]a_{i}[/math] и каждом [math]b_{i}[/math] как сегменты одинаковой длины [math]\frac{h} {\log\log n}[/math]. Рассматриваем сегменты как числа. Чтобы получить неконсервативное преимущество для сортировки, числа в этих контейнерах ([math]a_{i}[/math]-ом и [math]b_{i}[/math]-ом) хешируются, и получается [math]\frac{h}{\log\log n}[/math] хешированных значений в одном контейнере. При вычислении хеш-значений сегменты не влияют друг на друга, можно даже отделить четные и нечетные сегменты в два контейнера. Не умаляя общности считаем, что хеш-значения считаются за константное время. Затем, посчитав значения, два контейнера объединяем в один. Пусть [math]a'_{i}[/math] — хеш-контейнер для [math]a_{i}[/math], аналогично [math]b'_{i}[/math]. В сумме хеш-значения имеют [math]\frac{2 \log n}{c \log\log n}[/math] бит, хотя эти значения разделены на сегменты по [math]\frac{h}{ \log\log n}[/math] бит в каждом контейнере. Между сегментами получаются пустоты, которые забиваются нулями. Сначала упаковываются все сегменты в [math]\frac{2 \log n}{c \log\log n}[/math] бит. Потом рассматривается каждый хеш-контейнер как число, и эти хеш-контейнеры сортируются за линейное время (сортировка будет рассмотрена чуть позже). После этой сортировки биты в [math]a_{i}[/math] и [math]b_{i}[/math] разрезаны на [math]\frac{\log\log n}{h}[/math] сегментов. Таким образом, получилось дополнительное мультипликативное преимущество в [math]\frac{h} {\log\log n}[/math] (additional multiplicative advantage).

После того, как вышеописанный процесс повторится [math]g[/math] раз, получится неконсервативное преимущество в [math](\frac{h} {\log\log n})^g[/math] раз, в то время как потрачено только [math]O(gqt)[/math] времени, так как каждое многократное деление происходит за линейное время [math]O(qt)[/math].


Хеш-функция, которая используется, находится следующим образом. Будут хешироватся сегменты, [math]\frac{\log\log n}{h}[/math]-ые, [math](\frac{\log\log n}{h})^2[/math]-ые, [math]\ldots[/math] по счету в числе. Хеш-функцию для [math](\frac{\log\log n}{h})^t[/math]-ых по счету сегментов, получаем нарезанием всех [math]p[/math] чисел на [math](\frac{\log\log n}{h})^t[/math] сегментов. Рассматривая каждый сегмент как число, получаем [math]p(\frac{\log\log n}{h})^t[/math] чисел. Затем получаем одну хеш-функцию для этих чисел. Так как [math]t \lt \log n[/math], то получится не более [math]\log n[/math] хеш-функций.


Рассмотрим сортировку за линейное время, о которой было упомянуто ранее. Предполагается, что хешированные значения для каждого контейнера упакованы в [math]\frac{2 \log n}{c \log\log n}[/math] бит. Есть [math]t[/math] наборов, в каждом из которых [math]q + p[/math] хешированных контейнеров по [math]\frac{2 \log n}{c \log\log n}[/math] бит в каждом. Эти контейнеры должны быть отсортированы в каждом наборе. Комбинируя все хеш-контейнеры в один pool, сортируем следующим образом.


Procedure Linear-Time-Sort

Входные данные: [math]r \gt = n^{\frac{2}{5}}[/math] чисел [math]d_{i}[/math], [math]d_{i}.value[/math] — значение числа [math]d_{i}[/math], в котором [math]\frac{2 \log n}{c \log\log n}[/math] бит, [math]d_{i}.set[/math] — набор, в котором находится [math]d_{i}[/math]. Следует отметить, что всего есть [math]t[/math] наборов.

  1. Сортируем все [math]d_{i}[/math] по [math]d_{i}.value[/math], используя bucket sort. Пусть все отртированные числа в [math]A[1..r][/math]. Этот шаг занимает линейное время, так как сортируется не менее [math]n^{\frac{2}{5}}[/math] чисел.
  2. Помещаем все [math]A[j][/math] в [math]A[j].set[/math].

Сортировка с использованием O(n log log n) времени и памяти

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


Берем [math]1/e = 5[/math] для ЭП-дерева Андерссона. Следовательно, у корня будет [math]n^{\frac{1}{5}}[/math] детей, и каждое ЭП-дерево в каждом ребенке будет иметь [math]n^{\frac{4}{5}}[/math] листьев. В отличие от оригинального дерева, за раз вставляется не один элемент, а [math]d^2[/math], где [math]d[/math] — количество детей узла дерева, в котором числа должны спуститься вниз. Алгоритм полностью опускает все [math]d^2[/math] чисел на один уровень. В корне опускаются [math]n^{\frac{2}{5}}[/math] чисел на следующий уровень. После того, как все числа опустились на следующий уровень, они успешно разделились на [math]t_{1} = n^{1/5}[/math] наборов [math]S_{1}, S_{2}, \ldots, S_{t_{1}}[/math], в каждом из которых [math]n^{\frac{4}{5}}[/math] чисел и [math]S_{i} \lt S_{j}, i \lt j[/math]. Затем, берутся [math]n^{\frac{8}{25}}[/math] чисел из [math]S_{i}[/math] и опускаются на следующий уровень ЭП-дерева. Это повторяется, пока все числа не опустятся на следующий уровень. На этом шаге числа разделены на [math]t_{2} = n^{\frac{1}{5}}n^{\frac{4}{25}} = n^{\frac{9}{25}}[/math] наборов [math]T_{1}, T_{2}, \ldots, T_{t_{2}}[/math], аналогичных наборам [math]S_{i}[/math], в каждом из которых [math]n^{\frac{16}{25}}[/math] чисел. Теперь числа опускаются дальше в ЭП-дереве.

Нетрудно заметить, что перебалансирока занимает [math]O(n \log\log n)[/math] времени с [math]O(n)[/math] времени на уровень, аналогично стандартному ЭП-дереву Андерссона.


Нам следует нумеровать уровни ЭП-дерева с корня, начиная с нуля. Рассмотрим спуск вниз на уровне [math]s[/math]. Имеется [math]t = n^{1 - (\frac{4}{5})^s}[/math] наборов по [math]n^{(\frac{4}{5})^s}[/math] чисел в каждом. Так как каждый узел на данном уровне имеет [math]p = n^{\frac{1}{5} \cdot (\frac{4}{5})^s}[/math] детей, то на [math]s + 1[/math] уровень опускаются [math]q = n^{\frac{2}{5} \cdot (\frac{4}{5})^s}[/math] чисел для каждого набора, или всего [math]qt \geqslant n^{\frac{2}{5}}[/math] чисел для всех наборов за один раз.


Спуск вниз можно рассматривать как сортировку [math]q[/math] чисел в каждом наборе вместе с [math]p[/math] числами [math]a_{1}, a_{2}, \ldots, a_{p}[/math] из ЭП-дерева, так, что эти [math]q[/math] чисел разделены в [math]p + 1[/math] наборов [math]S_{0}, S_{1}, \ldots, S_{p}[/math] таких, что [math]S_{0} \lt a_{1} \lt \ldots \lt a_{p} \lt S_{p}[/math].


Так как [math]q[/math] чисел не надо полностью сортировать и [math]q = p^2[/math], то можно использовать лемму №6 для сортировки. Для этого необходимо неконсервативное преимущество, которое получается с помощью signature sorting. Для этого используется линейная техника многократного деления (multi-dividing technique).


После [math]g[/math] сокращений бит в signature sorting получаем неконсервативное преимущество в [math](\frac{h}{ \log\log n})^g[/math]. Мы не волнуемся об этих сокращениях до конца потому, что после получения неконсервативного преимущества мы можем переключиться на лемму №6 для завершения разделения [math]q[/math] чисел с помощью [math]p[/math] чисел на наборы. Заметим, что по природе битового сокращения начальная задача разделения для каждого набора перешла в [math]w[/math] подзадач разделения на [math]w[/math] поднаборов для какого-то числа [math]w[/math].


Теперь для каждого набора все его поднаборы в подзадачах собираются в один набор. Затем, используя лемму №6, делается разделение. Так как получено неконсервативное преимущество в [math](\frac{h}{\log\log n})^g[/math] и работа происходит на уровнях не ниже, чем [math]2 \log\log\log n[/math], то алгоритм занимает [math]O(\frac{qt \log\log n}{g(\log h - \log\log\log n) - \log\log\log n}) = O(\log\log n)[/math] времени.


В итоге разделились [math]q[/math] чисел [math]p[/math] числами в каждый набор. То есть получилось, что [math]S_{0} \lt e_{1} \lt S_{1} \lt \ldots \lt e_{p} \lt S_{p}[/math], где [math]e_{i}[/math] — сегмент [math]a_{i}[/math], полученный с помощью битового сокращения. Такое разделение получилось комбинированием всех поднаборов в подзадачах. Предполагаем, что числа хранятся в массиве [math]B[/math] так, что числа в [math]S_{i}[/math] предшествуют числам в [math]S_{j}[/math] если [math]i \lt j[/math] и [math]e_{i}[/math] хранится после [math]S_{i - 1}[/math], но до [math]S_{i}[/math].


Пусть [math]B[i][/math] находится в поднаборе [math]B[i].subset[/math]. Чтобы позволить разделению выполниться, для каждого поднабора помещаем все [math]B[j][/math] в [math]B[j].subset[/math].

На это потребуется линейное время и место.


Теперь рассмотрим проблему упаковки, которая решается следующим образом. Считается, что число бит в контейнере [math]\log m \geqslant \log\log\log n[/math], потому что в противном случае можно использовать radix sort для сортировки чисел. У контейнера есть [math]h/ \log\log n[/math] хешированных значений (сегментов) в себе на уровне [math]\log h[/math] в ЭП-дереве. Полное число хешированных бит в контейнере равно [math](2 \log n)(c \log\log n)[/math] бит. Хешированные биты в контейнере выглядят как [math]0^{i}t_{1}0^{i}t_{2} \ldots t_{h/ \log\log n}[/math], где [math]t_{k}[/math]-ые — хешированные биты, а нули — это просто нули. Сначала упаковываем [math]\log\log n[/math] контейнеров в один и получаем [math]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}[/math], где [math]t_{i, k}[/math]: элемент с номером [math]k = 1, 2, \ldots, h/ \log\log n[/math] из [math]i[/math]-ого контейнера. Используем [math]O(\log\log n)[/math] шагов, чтобы упаковать [math]w_{1}[/math] в [math]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}[/math]. Теперь упакованные хеш-биты занимают [math]2 \log n/c[/math] бит. Используем [math]O(\log\log n)[/math] времени чтобы распаковать [math]w_{2}[/math] в [math]\log\log n[/math] контейнеров [math]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[/math]. Затем, используя [math]O(\log\log n)[/math] времени, упаковываем эти [math]\log\log n[/math] контейнеров в один [math]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}[/math]. Затем, используя [math]O(\log\log n)[/math] шагов, упаковываем [math]w_{4}[/math] в [math]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}[/math]. В итоге используется [math]O(\log\log n)[/math] времени для упаковки [math]\log\log n[/math] контейнеров. Считаем, что время, потраченное на один контейнер — константа.

См. также

Источники информации

}}