47
правок
Изменения
м
Тире, to, dfrac, radix interwiki, точки, geqslant, неясность некоторых формулировок, tex в заголовках, см также, источники, категории
[[Файл:Task.jpg]]
== Алгоритм <tex>O(n\operatorname{log}\operatorname{log}n)</tex> ==
=== Нахождение длины НВП ===
==== Основная идея ====
Будем последовательно обрабатывать элементы <tex>\pi(1), \pi(2),~\dots,~\pi(n)</tex>:
* Если <tex>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <tex>B</tex>.
* Иначе <tex>\pi(i)</tex> заменяет наименьший лучший элемент, из тех, что больше <tex>\pi(i)</tex>.
'''int''' k = 0 <font color=darkgreen>// длина НВП</font>
'''int''' n = <tex>\pi</tex>.size
'''for''' i = 1 '''to ''' n
x = <tex>\pi</tex>[i]
<font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
B.delete(B.next(x))
'''else'''
<font color=darkgreen>// добавленный элемент - — максимальный</font>
<font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
k = k + 1
'''int''' n = <tex>\pi</tex>.size
<font color=blue>'''vector<int>''' predecessor(n)</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
'''for''' i = 1 '''to ''' n
x = <tex>\pi</tex>[i]
B.insert(x)
'''return''' result</font>
</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 geqslant k</tex>. Если мы разобьем всю последовательность на блоки из {{ Acronym|<tex>m</tex> элементов|последний блок может быть меньше}} и нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а т.к. <tex>m \ge geqslant k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока - — получаем верхнее ограничение в <tex>k + m</tex> обрабатываемых возможных значений.)
'''''Описанный здесь алгоритм подбора <tex>m_i</tex> и получение асимптотической оценки <tex>O(n\operatorname{log}\operatorname{log}k)</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 geqslant 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>.
Получим сортированные варианты этих блоков <tex>C_j^S</tex>. При лобовой {{Acronym|цифровой|radix}} сортировке мы получим Лобовая [[цифровая сортировка]] дает нам время работы <tex>O(\fracdfrac{n}{m}n)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>.
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>.
==== Пример ====
Пусть <tex>m = 5</tex>. Исходно:
=== Обработка блока ===
==== Основная идея ====
* {{Acronym|Достаем из очереди ключи|если это первый блок - — ничего не делаем}} и конвертируем их в элементы <tex>\pi</tex>.
* Классический [[Сортировка слиянием#Принцип работы#Слияние двух массивов | merge]] только что полученных элементов <tex>\pi</tex> с элементами нового блока, но с модификацией: генерируются 2 дополнительных массива - индексы элементов исходных массивов в новом. Слияние массивов назовем <tex>merged</tex>.
* На массив индексов, относящиеся к новому блоку, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений {{Acronym|ключей|смещений}} к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне <tex>O(m)</tex>.
* Первый массив индексов, который соответствует элементам, ранее находящимся в очереди, вновь кладутся в очередь (обычными <tex>insert</tex>-ами). Второй массив обрабатывается описанным выше алгоритмом <tex>LIS</tex>, при том массив <tex>predecessor</tex> строится из ключей с помощью <tex>merged</tex>.
==== Визуализация ====
Помеченные <font color=green>зеленым</font> - — условные данные. Остальное - — условные операции. Например <tex>keys \longrightarrow merged</tex> значит взять элементы из массива <tex>merged</tex> c индексами из <tex>keys</tex>. <tex>merge \longrightarrow merged</tex> - — здесь <tex>merged</tex> обозначает результат операции '''merge'''.
[[Файл:blockHandle.jpg]]
<tex>merged: \{3, 4, 8, 9, 10\}</tex>
===== Второй блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>merged: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>ind's\#0</tex> - — индексы текущих
|-align="center"
| 3||4||7
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>ind's\#1</tex> - — индексы новых
|-align="center"
| 1||2||5||6||8
===== Третий блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>merged: \{1,2,3,4,5,6,8,12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>ind's\#0</tex> - — индексы текущих
|-align="center"
| 1||2||3||6
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>ind's\#1</tex> - — индексы новых
|-align="center"
| 4||5
| 1||2||5||7||11
|}
== См. также ==
*[[Дерево ван Эмде Боаса]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Наибольшая общая возрастающая подпоследовательность]]
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Источники информации ==
* [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf] (07.01.2017)
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
