47
правок
Изменения
м
Нет описания правки
</code>
== Оптимизация до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==
=== Основная идея ===
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
Предположим, мы знаем такое {{Acronym|приближение <tex>k</tex>|далее рассмотрим нахождение и насколько оно точное}} <tex>m: m \ge k</tex>. Если мы разобьем всю последовательность на блоки из {{ Acronym|<tex>m</tex> элементов|последний блок может быть меньше}} и нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а т.к. <tex>m \ge k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока - получаем врехнее ограничение в <tex>k + m</tex> обрабатываемых возможных значений.)
Рассмотрим последовательность <tex>m_0, m_0 ^{\operatorname{log}m_0}</tex>
==== ====
=== Деление на блоки ===
