81
правка
Изменения
Нет описания правки
ЭП-дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> (0<<tex>e</tex><1) ЭП-поддеревьев, в каждом из которых <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> вставленных целых числах. Такое время достигается за счет вставки чисел группами, а не по одиночке, как изначально предлагает Андерссон.
==Необходимая информацияОпределения=={{Определение|id=def1. |definition=# Контейнер {{---}} объект определенного типа, содержащий обрабатываемый элемент. Например __int32, __int64, и т.д.}}{{Определение|id=def2. |definition=# Алгоритм сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex> называется консервативным, если длина контейнера (число бит в контейнере), является <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм неконсервативный.}}{{Определение|id=def3. |definition=# Если мы сортируем целые числа из множества {0, 1, ..., <tex>m</tex> - 1} с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда мы сортируем с неконсервативным преимуществом <tex>k</tex>.}}{{Определение|id=def4. |definition=# Для множества <tex>S</tex> определим<tex>\min(S) = \min\limits_{a \in S} a</tex>
==Уменьшение числа бит в числах==
