47
правок
Изменения
→Оптимизация до O(n\operatorname{log}\operatorname{log}k): Подраздел "Основная идея" написан
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <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_1,~m_2,~\dots\}</tex>, где <tex> m_{i+1} =m_i ^{\operatorname{log}m_i} === ====2^{\operatorname{log}^2m_i}</tex>, <tex>m_0</tex> - некоторое значение, меньшее <tex>k</tex>.
Будем последовательно для элементов этой последовательности запускать {{Acronym|алгоритм|о котором ниже}}. Если условие <tex>m \ge k</tex> перестает выполняться, прерываем выполнение. Таким образом, время работы для каждого <tex>m_j</tex> будет <tex>O(n\operatorname{log}\operatorname{log}m_j)</tex>. {{Acronym|Найдется|первый из подобных}} такой <tex>m_i</tex>, который окажется больше <tex>k</tex>, и алгоритм успешно завершится.
<tex>\operatorname{log}\operatorname{log}m_{i+1} = \operatorname{log}\operatorname{log}2^{\operatorname{log}^2m_i} = \operatorname{log}\operatorname{log}^2m_i = 2\operatorname{log}\operatorname{log}m_i</tex>
<tex>\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i</tex>
{{Acronym|Общее время|для всех обработанных значений m}} работы - <tex>O(n(\sum\limits_{j = 0}\limits^{i}2^{1-j})\operatorname{log}\operatorname{log}m_i) = O(n\operatorname{log}\operatorname{log}m_i)</tex>. Заметим, что <tex>m_i < k^{\operatorname{log}k}</tex>, т.к. в противном случае <tex>m_{i-1} > k</tex>, что противоречит тому, что <tex>m_i</tex> - первый из тех, что больше <tex>k</tex>. Следовательно, <tex>\operatorname{log}\operatorname{log}m_i < 2\operatorname{log}\operatorname{log}k \</tex>.
Получаем время работы <tex>O(n\operatorname{log}\operatorname{log}k)</tex>
=== Деление на блоки ===
==== Основная идея ====
Разделим исходную перестановку <tex>\pi</tex> на блоки <tex>C_j = {\pi_{(j-1)m + 1},~\pi_{(j-1)m + 2},~\dots, ~\pi_{(j-1)m + m}}</tex>
