76
правок
Изменения
Новая страница: «{{Задача |definition = Дана перестановка <tex>\pi</tex> множества<tex>~\{1, 2,~\dots,~n\}</tex>. Требуется найти [[З...»
{{Задача
|definition = Дана перестановка <tex>\pi</tex> множества<tex>~\{1, 2,~\dots,~n\}</tex>. Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> — длина НВП.
}}
[[Файл:Task.jpg]]
== Алгоритм за O(n log log n) ==
=== Нахождение длины НВП ===
==== Основная идея ====
Пусть <tex>\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка.
Будем последовательно обрабатывать элементы в порядке <tex>\pi_1, \pi_2,~\dots,~\pi_n\colon</tex>
Для каждой длины <tex>l = 1, 2,~\dots,~n</tex> предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины <tex>l</tex> и запишем его в массив <tex>B_l</tex>. Будем называть его наилучшим элементом для длины <tex>l</tex>.
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для полпоследовательности <tex>\pi_1, \pi_2,~\dots~,\pi_{i-1}</tex>, значит с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец <tex>B</tex>.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины, тогда мы находим наименьшее <tex>k:\colon B_k > \pi_i</tex> и заменяем его элементом <tex>\pi_i</tex>.
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <tex>\mathrm{insert}, \mathrm{next}, \mathrm{delete}</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Так как данная структура данных работает за <tex>O(\operatorname{log} k)</tex>, где k - количество битов чисел, которые позволяет хранить дерево, то полученный алгоритм работает за <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию, потому что все элементы последовательности не превосходят n.
==== Пример ====
===== Типы операций =====
* Добавление элемента, который больше всех предыдущих:
[[Файл:Operation1.jpg]]
* Замещение элемента более подходящим, т.е. добавление немаксимального элемента:
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
===== Пример последовательности =====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
|-align="center"
| 9 || 3 || 10 || 4 || 8 || 1 || 2 || 12 || 6 || 5 || 7 || 11
|}
===== Состояние очереди при каждом добавлении =====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| style="background:#FFCC00"| 9 || || || || || style="background: #77A9F4"| 9
|-align="center"
| style="background:#FFCC00"| 3 || || || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || style="background:#FFCC00"| 10 || || || || style="background: #77A9F4"| 10
|-align="center"
| 3 || style="background:#FFCC00"| 4 || || || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || style="background:#FFCC00"| 8 || || || style="background: #77A9F4"| 8
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 8 || || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 8 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || 8 || style="background:#FFCC00"| 12 || || style="background: #77A9F4"| 12
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 6 || 12 || || style="background: #77A9F4"| 6
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5
|-align="center"
| 1 || 2 || 5 || style="background:#FFCC00"| 7 || || style="background: #77A9F4"| 7
|-align="center"
| 1 || 2 || 5 || 7 || style="background:#FFCC00"| 11 || style="background: #77A9F4"| 11
|}
==== Псевдокод ====
<code>
'''int''' LIS(<tex>\pi</tex>[n])
'''PriorityQueue''' B <font color=darkgreen>// рабочая приоритетная очередь</font>
'''int''' k = 0 <font color=darkgreen>// длина НВП</font>
'''for''' i = 1 '''to''' n
x = <tex>\pi</tex>[i]
<font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
<font color=darkgreen>// устаревшие будем удалять</font>
B.insert(x)
'''if''' <tex>\exists</tex> B.next(x)
<font color=darkgreen>// добавленный элемент — не максимальный</font>
<font color=darkgreen>// удаляем следующее за x значение</font>
B.delete(B.next(x))
'''else'''
<font color=darkgreen>// добавленный элемент — максимальный</font>
<font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
k = k + 1
'''return''' k</code>
=== Расширение алгоритма до нахождения НВП ===
==== Основная идея ====
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем восстановить НВП.
==== Общий вид алгоритма ====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| 9 || || || || || style="background: #77A9F4"| 9
|-align="center"
| 3 || || || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || 10 || || || || style="background: #77A9F4"| 10
|-align="center"
| 3 || 4 || || || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || 8 || || || style="background: #77A9F4"| 8
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 8 || || || style="background: #77A9F4"| 1
|-align="center"
| style="background:#FF7F00"|1 || style="background:#FFCC00"| 2 || 8 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || style="background:#FFCC00"|2 || 8 || 12 || || style="background: #77A9F4"| 12
|-align="center"
| 1 || style="background:#FFCC00"|2 || 6 || 12 || || style="background: #77A9F4"| 6
|-align="center"
| 1 || style="background:#FF7F00"|2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5
|-align="center"
| 1 || 2 || style="background:#FF7F00"| 5 || style="background:#FFCC00"| 7 || || style="background: #77A9F4"| 7
|-align="center"
| 1 || 2 || 5 || style="background:#FF7F00"| 7 || style="background:#FF7F00"| 11 || style="background: #77A9F4"| 11
|}
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! colspan="12" | predecessor
|-align="center"
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|-align="center"
| || 1 || || 3 || 2 || 2 || 5 || 4 || || 3 || 7 || 8
|}
==== Псевдокод ====
<code>
'''int[]''' LIS(<tex>\pi</tex>[n])
'''PriorityQueue''' B
'''int''' k = 0
<font color=blue>'''int''' predecessor[n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
'''for''' i = 1 '''to''' n
x = <tex>\pi</tex>[i]
B.insert(x)
<font color=blue>predecessor[x] = B.prev(x)</font>
'''if''' <tex>\exists</tex> B.next(x)
B.delete(B.next(x))
'''else'''
k = k + 1
<font color=darkgreen>// по цепочке от последнего элемента
// восстанавливаем НВП</font>
<font color=blue>'''int''' result[k]
'''int''' cur = B.max
'''for''' i = k - 1 '''downto''' 0
result[i] = cur
cur = predecessor[cur]
'''return''' result</font>
</code>
== Оптимизация до O(n log log k) ==
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
Предположим, мы знаем такое приближение числа <tex>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.
Чтобы достичь нужной оценки, будем делить последовательность на <tex>m</tex> блоков, кроме последнего, который может быть меньше, и обрабатывать каждый блок отдельно.
=== Деление на блоки===
Последовательность <tex>S</tex> делится на блоки <tex>C_j, j=1,~\dots~,\lceil\frac{n}{m}\rceil</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> отсортированный блок <tex>C_j</tex>. Отсортированные и неотсортированные блоки будем хранить в памяти.
[[Цифровая сортировка]] каждых блоков отдельно будет давать нам время рваботы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Чтобы отсортировать их за линейное время, дополним каждый элемент номером его блока и получим пары <tex>\langle\lceil i/m\rceil,\pi_i\rangle</tex>. Цифровая сортировка этих пар, если принимать за старший разряд номер блока, а за младший значение элемента, будет работать <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
=== Обработка блока ===
Обрабатывая блоки, будем работать не со значениями элементов, а с ключами, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн, то есть мы не перейдём к обработке следующего блока, пока не закончим с текущим.
Каждому элементу <tex>x</tex> взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Если все значения ключей будут находятся в промежутке <tex>\{1,2,\dots,2m\}</tex>, то эффективней будет работать с ключами элементов в очереди <tex>B</tex>.
Чтобы определить ключи элементам так, чтобы их значения были в представленном промежутке, работая с блоком <tex>C_j</tex> будем сливать элементы, ключи которых находятся в очереди <tex>B</tex> с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>.
Сопоставим каждому элементу в списке его позицию. Это и будет наш ключ. Заметим, что элементы, чьи ключи находятся в <tex>B</tex> располагаются в возрастающеме порядке, поэтому достаточно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]]. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>.
После того, как ключи определенны, обновляем ключи в очереди <tex>B</tex>.
После этого запускаем, описанный выше алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порялке исходной последовательности.
В итоге, обработка блока делится на следующие этапы:
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{bestelems}</tex>.
* Сливаем элементы в <tex>\mathtt{bestelems}</tex> со следующим отсортированным блоком в список <tex>\mathtt{merged}</tex>.
* Присваеваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex>.
* Вставляем в <tex>B</tex> новые ключи элементов <tex>\mathtt{bestelems}</tex>.
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответсвующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
====Пример====
Предположим, что <tex>m=5</tex>. Исходно получаем:
{| class="wikitable" style="text-align:center"
| Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3
|-
|<tex>\pi</tex>||style="background:#FF8080"|9||style="background:#FF8080"|3||style="background:#FF8080"|10||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|12||style="background:#80FF80"|6||style="background:#80FF80"|5||style="background:#8080FF"|7||style="background:#8080FF"|11
|}
После сортировки:
{| class="wikitable" style="text-align:center"
|Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3
|-
|<tex>\pi</tex> ||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#FF8080"|9||style="background:#FF8080"|10||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|6||style="background:#80FF80"|12||style="background:#8080FF"|7||style="background:#8080FF"|11
|}
''' Первый блок '''
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Первый блок
|-
| <tex>\pi</tex> ||style="background:#FFA080"|9||style="background:#FFDF80"|3||style="background:#FF9580"|10||style="background:#FFD580"|4||style="background:#FFAA80"|8
|-
|key ||style="background:#FF9980"|4||style="background:#FFE680"|1||style="background:#FF8080"|5||style="background:#FFCC80"|2||style="background:#FFB380"|3
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFDF80"|3||style="background:#FFD580"|4||style="background:#FFAA80"|8||style="background:#FFA080"|9||style="background:#FF9580"|10
|-
|key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|3||style="background:#FF9980"|4||style="background:#FF8080"|5
|}
|}
Обработка блока с помощью алгоритма <tex>\mathrm{LIS}</tex>.
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 4 || || || style="background: #77A9F4"| 4 || style="background: #9ACD32"| 9
|-align="center"
| style="background:#FFCC00"| 1 || || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 3
|-align="center"
| 1 || style="background:#FFCC00"| 5 || || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 10
|-align="center"
| 1 || style="background:#FFCC00"| 2 || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 4
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || style="background: #77A9F4"| 3 || style="background: #9ACD32"| 8
|}
В результате получаем
<tex>B: \{1, 2, 3\}</tex>
<tex>\mathtt{merged}: \{3,4,8,9,10\}</tex>
'''Второй блок'''
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.
Сливаем <tex>C_2^s</tex> и восстановеленные элементы из <tex>B</tex>:
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>B</tex>
|-align="center"
| 3||4||8
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>C_2^s</tex>
|-align="center"
| 1||2||5||6||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="9"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|1||2||3||4||5||6||8||12
|-align="center"
|!key|1||2||3||4||5||6||7||8
|}
|}
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Второй блок
|-
| <tex>\pi</tex> ||style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FF8080"|12||style="background:#FFC080"|6||style="background:#FFCA80"|5
|-
| key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FF8080"|8||style="background:#FF9980"|6||style="background:#FFB380"|5
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FFCA80"|5||style="background:#FFC080"|6||style="background:#FF8080"|12
|-
| key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|5||style="background:#FF9980"|6||style="background:#FF8080"|8
|}
|}
Обновляем ключи в очереди:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 3 || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
|}
<tex>\mathrm{LIS}</tex> новых:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 7 || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 7 || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 2
|-align="center"
| 1 || 2 || 7 || style="background:#FFCC00"| 8 || style="background: #77A9F4"| 8 || style="background: #9ACD32"| 12
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 6 || 8 || style="background: #77A9F4"| 6 || style="background: #9ACD32"| 6
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 5 || 8 || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 5
|}
В результате получаем:
<tex>B: \{1, 2, 5, 8\}</tex>
<tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</tex>
'''Третий блок'''
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>\mathtt{merged}: \{1, 2, 3, 4, 5, 6, 8, 12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
Сливаем <tex>C_3^s</tex> и восстановленные элементы из <tex>B</tex>:
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>B</tex>
|-align="center"
| 1||2||5||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>C_3^s</tex>
|-align="center"
| 7||11
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="6"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|1||2||5||7||11||12
|-align="center"
|!key|1||2||3||4||5||6
|}
|}
{|
| ||
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="3"|третий блок
|-
| <tex>\pi</tex> ||style="background:#FFB580"|7||style="background:#FF8B80"|11
|-
| key ||style="background:#FFC080"|4||style="background:#FF8080"|5
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="3"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFB580"|7||style="background:#FF8B80"|11
|-
| key ||style="background:#FFC080"|4||style="background:#FF8080"|5
|}
|}
Обновление старых ключей:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 1 || || || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || || style="background: #77A9F4"| 3
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 6 || style="background: #77A9F4"| 6
|}
<tex>\mathrm{LIS}</tex> новых:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>B_5</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4 || style="background: #9ACD32"| 7
|-align="center"
| 1 || 2 || 3 || 4 || style="background:#FFCC00"| 5 || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 11
|}
Результат завершения алгоритма:
<tex>B: \{1, 2, 3, 4, 5\}</tex>
<tex>\mathtt{merged}: \{1,2,5,7,11,12\}</tex>
Получаем, что длина НВП - 5, и НВП оканчивается на <tex>\mathtt{merged_5}=11</tex>.
'''Восстановление НВП'''
{| class="wikitable" style="center"
! colspan="12"| <tex>\mathtt{predecessor}</tex>
|-align="center"
| style="background:#DCFFFF"|1||style="background:#DCDCFF"|2||3||4||style="background:#DCFFDC"|5||6||style="background:#FFDCDC"|7||8||9||10||style="background:#FFFFC8"|11||12
|-align="center"
|style="background:#FFFFC8"| ||style="background:#DCFFFF"|1|| ||3||style="background:#DCDCFF"|2||style="background:#E6E6FF"|2||style="background:#DCFFDC"|5||4|| ||3||style="background:#FFDCDC"|7||8
|}
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
{| class="wikitable" style="center"
|-align="center"
| обратный порядок||style="background:#FFFFC8"|11||style="background:#FFDCDC"|7||style="background:#DCFFDC"|5||style="background:#E6E6FF"|2||style="background:#DCFFFF"|1
|-align="center"
| НВП||style="background:#DCFFFF"|1||style="background:#E6E6FF"|2||style="background:#DCFFDC"|5||style="background:#FFDCDC"|7||style="background:#FFFFC8"|11
|}
===Оценка времени работы===
Так как размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, а количество блоков всего <tex>\lceil n/m \rceil</tex>. То количество присваиваний новых ключей элементам последовательности не больше <tex>2cm\cdot\dfrac{n}{m}=O(n)</tex>, где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(\log \log m)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m</tex>.
Докажем, что реализация данного алгоритма будет работать за время <tex>O(n \log \log m)</tex> для последовательности длины n.
Рассмотрим последовательность <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>.
Будем по порядку для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди <tex>B</tex> становится больше <tex>m_i</tex>, то условие <tex>m \geqslant k</tex> перестает выполняться, тогда останавливаем алгоритм, и переходим к следующему элементу <tex>m_{i+1}</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant k</tex>, то алгоритм успешно завершится.
Таким образом, время работы алгоритма — <tex>O(n \log \log {m_i})</tex> для <tex>0\leqslant i < j</tex>, потому что во время работы очередь <tex>B</tex> хранит не более <tex>m_i</tex> элементов, ключи которых не больше <tex>2m_i</tex>. Для значения <tex>m_j</tex> алгоритм успешно завершается, так как условие полной обработки последовательности <tex>m\geqslant k</tex> выполняется. Таким образом, время работы алгоритма для <tex>m_j</tex> также <tex>O(n\log \log {m_j})</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>
Общее время работы алгоритма — <tex>O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \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>.
== См. также ==
*[[Дерево ван Эмде Боаса]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Наибольшая общая возрастающая подпоследовательность]]
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Источники информации ==
* [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)] (07.01.2017)
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Классические задачи динамического программирования]]
|definition = Дана перестановка <tex>\pi</tex> множества<tex>~\{1, 2,~\dots,~n\}</tex>. Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> — длина НВП.
}}
[[Файл:Task.jpg]]
== Алгоритм за O(n log log n) ==
=== Нахождение длины НВП ===
==== Основная идея ====
Пусть <tex>\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка.
Будем последовательно обрабатывать элементы в порядке <tex>\pi_1, \pi_2,~\dots,~\pi_n\colon</tex>
Для каждой длины <tex>l = 1, 2,~\dots,~n</tex> предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины <tex>l</tex> и запишем его в массив <tex>B_l</tex>. Будем называть его наилучшим элементом для длины <tex>l</tex>.
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для полпоследовательности <tex>\pi_1, \pi_2,~\dots~,\pi_{i-1}</tex>, значит с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец <tex>B</tex>.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины, тогда мы находим наименьшее <tex>k:\colon B_k > \pi_i</tex> и заменяем его элементом <tex>\pi_i</tex>.
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <tex>\mathrm{insert}, \mathrm{next}, \mathrm{delete}</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Так как данная структура данных работает за <tex>O(\operatorname{log} k)</tex>, где k - количество битов чисел, которые позволяет хранить дерево, то полученный алгоритм работает за <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию, потому что все элементы последовательности не превосходят n.
==== Пример ====
===== Типы операций =====
* Добавление элемента, который больше всех предыдущих:
[[Файл:Operation1.jpg]]
* Замещение элемента более подходящим, т.е. добавление немаксимального элемента:
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
===== Пример последовательности =====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
|-align="center"
| 9 || 3 || 10 || 4 || 8 || 1 || 2 || 12 || 6 || 5 || 7 || 11
|}
===== Состояние очереди при каждом добавлении =====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| style="background:#FFCC00"| 9 || || || || || style="background: #77A9F4"| 9
|-align="center"
| style="background:#FFCC00"| 3 || || || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || style="background:#FFCC00"| 10 || || || || style="background: #77A9F4"| 10
|-align="center"
| 3 || style="background:#FFCC00"| 4 || || || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || style="background:#FFCC00"| 8 || || || style="background: #77A9F4"| 8
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 8 || || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 8 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || 8 || style="background:#FFCC00"| 12 || || style="background: #77A9F4"| 12
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 6 || 12 || || style="background: #77A9F4"| 6
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5
|-align="center"
| 1 || 2 || 5 || style="background:#FFCC00"| 7 || || style="background: #77A9F4"| 7
|-align="center"
| 1 || 2 || 5 || 7 || style="background:#FFCC00"| 11 || style="background: #77A9F4"| 11
|}
==== Псевдокод ====
<code>
'''int''' LIS(<tex>\pi</tex>[n])
'''PriorityQueue''' B <font color=darkgreen>// рабочая приоритетная очередь</font>
'''int''' k = 0 <font color=darkgreen>// длина НВП</font>
'''for''' i = 1 '''to''' n
x = <tex>\pi</tex>[i]
<font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
<font color=darkgreen>// устаревшие будем удалять</font>
B.insert(x)
'''if''' <tex>\exists</tex> B.next(x)
<font color=darkgreen>// добавленный элемент — не максимальный</font>
<font color=darkgreen>// удаляем следующее за x значение</font>
B.delete(B.next(x))
'''else'''
<font color=darkgreen>// добавленный элемент — максимальный</font>
<font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
k = k + 1
'''return''' k</code>
=== Расширение алгоритма до нахождения НВП ===
==== Основная идея ====
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем восстановить НВП.
==== Общий вид алгоритма ====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| 9 || || || || || style="background: #77A9F4"| 9
|-align="center"
| 3 || || || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || 10 || || || || style="background: #77A9F4"| 10
|-align="center"
| 3 || 4 || || || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || 8 || || || style="background: #77A9F4"| 8
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 8 || || || style="background: #77A9F4"| 1
|-align="center"
| style="background:#FF7F00"|1 || style="background:#FFCC00"| 2 || 8 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || style="background:#FFCC00"|2 || 8 || 12 || || style="background: #77A9F4"| 12
|-align="center"
| 1 || style="background:#FFCC00"|2 || 6 || 12 || || style="background: #77A9F4"| 6
|-align="center"
| 1 || style="background:#FF7F00"|2 || style="background:#FFCC00"| 5 || 12 || || style="background: #77A9F4"| 5
|-align="center"
| 1 || 2 || style="background:#FF7F00"| 5 || style="background:#FFCC00"| 7 || || style="background: #77A9F4"| 7
|-align="center"
| 1 || 2 || 5 || style="background:#FF7F00"| 7 || style="background:#FF7F00"| 11 || style="background: #77A9F4"| 11
|}
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! colspan="12" | predecessor
|-align="center"
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|-align="center"
| || 1 || || 3 || 2 || 2 || 5 || 4 || || 3 || 7 || 8
|}
==== Псевдокод ====
<code>
'''int[]''' LIS(<tex>\pi</tex>[n])
'''PriorityQueue''' B
'''int''' k = 0
<font color=blue>'''int''' predecessor[n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
'''for''' i = 1 '''to''' n
x = <tex>\pi</tex>[i]
B.insert(x)
<font color=blue>predecessor[x] = B.prev(x)</font>
'''if''' <tex>\exists</tex> B.next(x)
B.delete(B.next(x))
'''else'''
k = k + 1
<font color=darkgreen>// по цепочке от последнего элемента
// восстанавливаем НВП</font>
<font color=blue>'''int''' result[k]
'''int''' cur = B.max
'''for''' i = k - 1 '''downto''' 0
result[i] = cur
cur = predecessor[cur]
'''return''' result</font>
</code>
== Оптимизация до O(n log log k) ==
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
Предположим, мы знаем такое приближение числа <tex>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.
Чтобы достичь нужной оценки, будем делить последовательность на <tex>m</tex> блоков, кроме последнего, который может быть меньше, и обрабатывать каждый блок отдельно.
=== Деление на блоки===
Последовательность <tex>S</tex> делится на блоки <tex>C_j, j=1,~\dots~,\lceil\frac{n}{m}\rceil</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> отсортированный блок <tex>C_j</tex>. Отсортированные и неотсортированные блоки будем хранить в памяти.
[[Цифровая сортировка]] каждых блоков отдельно будет давать нам время рваботы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Чтобы отсортировать их за линейное время, дополним каждый элемент номером его блока и получим пары <tex>\langle\lceil i/m\rceil,\pi_i\rangle</tex>. Цифровая сортировка этих пар, если принимать за старший разряд номер блока, а за младший значение элемента, будет работать <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
=== Обработка блока ===
Обрабатывая блоки, будем работать не со значениями элементов, а с ключами, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн, то есть мы не перейдём к обработке следующего блока, пока не закончим с текущим.
Каждому элементу <tex>x</tex> взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Если все значения ключей будут находятся в промежутке <tex>\{1,2,\dots,2m\}</tex>, то эффективней будет работать с ключами элементов в очереди <tex>B</tex>.
Чтобы определить ключи элементам так, чтобы их значения были в представленном промежутке, работая с блоком <tex>C_j</tex> будем сливать элементы, ключи которых находятся в очереди <tex>B</tex> с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>.
Сопоставим каждому элементу в списке его позицию. Это и будет наш ключ. Заметим, что элементы, чьи ключи находятся в <tex>B</tex> располагаются в возрастающеме порядке, поэтому достаточно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]]. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>.
После того, как ключи определенны, обновляем ключи в очереди <tex>B</tex>.
После этого запускаем, описанный выше алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порялке исходной последовательности.
В итоге, обработка блока делится на следующие этапы:
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{bestelems}</tex>.
* Сливаем элементы в <tex>\mathtt{bestelems}</tex> со следующим отсортированным блоком в список <tex>\mathtt{merged}</tex>.
* Присваеваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex>.
* Вставляем в <tex>B</tex> новые ключи элементов <tex>\mathtt{bestelems}</tex>.
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответсвующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
====Пример====
Предположим, что <tex>m=5</tex>. Исходно получаем:
{| class="wikitable" style="text-align:center"
| Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3
|-
|<tex>\pi</tex>||style="background:#FF8080"|9||style="background:#FF8080"|3||style="background:#FF8080"|10||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|12||style="background:#80FF80"|6||style="background:#80FF80"|5||style="background:#8080FF"|7||style="background:#8080FF"|11
|}
После сортировки:
{| class="wikitable" style="text-align:center"
|Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3
|-
|<tex>\pi</tex> ||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#FF8080"|9||style="background:#FF8080"|10||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|6||style="background:#80FF80"|12||style="background:#8080FF"|7||style="background:#8080FF"|11
|}
''' Первый блок '''
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Первый блок
|-
| <tex>\pi</tex> ||style="background:#FFA080"|9||style="background:#FFDF80"|3||style="background:#FF9580"|10||style="background:#FFD580"|4||style="background:#FFAA80"|8
|-
|key ||style="background:#FF9980"|4||style="background:#FFE680"|1||style="background:#FF8080"|5||style="background:#FFCC80"|2||style="background:#FFB380"|3
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFDF80"|3||style="background:#FFD580"|4||style="background:#FFAA80"|8||style="background:#FFA080"|9||style="background:#FF9580"|10
|-
|key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|3||style="background:#FF9980"|4||style="background:#FF8080"|5
|}
|}
Обработка блока с помощью алгоритма <tex>\mathrm{LIS}</tex>.
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 4 || || || style="background: #77A9F4"| 4 || style="background: #9ACD32"| 9
|-align="center"
| style="background:#FFCC00"| 1 || || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 3
|-align="center"
| 1 || style="background:#FFCC00"| 5 || || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 10
|-align="center"
| 1 || style="background:#FFCC00"| 2 || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 4
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || style="background: #77A9F4"| 3 || style="background: #9ACD32"| 8
|}
В результате получаем
<tex>B: \{1, 2, 3\}</tex>
<tex>\mathtt{merged}: \{3,4,8,9,10\}</tex>
'''Второй блок'''
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.
Сливаем <tex>C_2^s</tex> и восстановеленные элементы из <tex>B</tex>:
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>B</tex>
|-align="center"
| 3||4||8
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>C_2^s</tex>
|-align="center"
| 1||2||5||6||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="9"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|1||2||3||4||5||6||8||12
|-align="center"
|!key|1||2||3||4||5||6||7||8
|}
|}
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Второй блок
|-
| <tex>\pi</tex> ||style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FF8080"|12||style="background:#FFC080"|6||style="background:#FFCA80"|5
|-
| key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FF8080"|8||style="background:#FF9980"|6||style="background:#FFB380"|5
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FFCA80"|5||style="background:#FFC080"|6||style="background:#FF8080"|12
|-
| key ||style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|5||style="background:#FF9980"|6||style="background:#FF8080"|8
|}
|}
Обновляем ключи в очереди:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 3 || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
|}
<tex>\mathrm{LIS}</tex> новых:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 7 || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 7 || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 2
|-align="center"
| 1 || 2 || 7 || style="background:#FFCC00"| 8 || style="background: #77A9F4"| 8 || style="background: #9ACD32"| 12
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 6 || 8 || style="background: #77A9F4"| 6 || style="background: #9ACD32"| 6
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 5 || 8 || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 5
|}
В результате получаем:
<tex>B: \{1, 2, 5, 8\}</tex>
<tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</tex>
'''Третий блок'''
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>\mathtt{merged}: \{1, 2, 3, 4, 5, 6, 8, 12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
Сливаем <tex>C_3^s</tex> и восстановленные элементы из <tex>B</tex>:
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>B</tex>
|-align="center"
| 1||2||5||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>C_3^s</tex>
|-align="center"
| 7||11
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="6"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|1||2||5||7||11||12
|-align="center"
|!key|1||2||3||4||5||6
|}
|}
{|
| ||
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="3"|третий блок
|-
| <tex>\pi</tex> ||style="background:#FFB580"|7||style="background:#FF8B80"|11
|-
| key ||style="background:#FFC080"|4||style="background:#FF8080"|5
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="3"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFB580"|7||style="background:#FF8B80"|11
|-
| key ||style="background:#FFC080"|4||style="background:#FF8080"|5
|}
|}
Обновление старых ключей:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 1 || || || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || || style="background: #77A9F4"| 3
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 6 || style="background: #77A9F4"| 6
|}
<tex>\mathrm{LIS}</tex> новых:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>B_5</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4 || style="background: #9ACD32"| 7
|-align="center"
| 1 || 2 || 3 || 4 || style="background:#FFCC00"| 5 || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 11
|}
Результат завершения алгоритма:
<tex>B: \{1, 2, 3, 4, 5\}</tex>
<tex>\mathtt{merged}: \{1,2,5,7,11,12\}</tex>
Получаем, что длина НВП - 5, и НВП оканчивается на <tex>\mathtt{merged_5}=11</tex>.
'''Восстановление НВП'''
{| class="wikitable" style="center"
! colspan="12"| <tex>\mathtt{predecessor}</tex>
|-align="center"
| style="background:#DCFFFF"|1||style="background:#DCDCFF"|2||3||4||style="background:#DCFFDC"|5||6||style="background:#FFDCDC"|7||8||9||10||style="background:#FFFFC8"|11||12
|-align="center"
|style="background:#FFFFC8"| ||style="background:#DCFFFF"|1|| ||3||style="background:#DCDCFF"|2||style="background:#E6E6FF"|2||style="background:#DCFFDC"|5||4|| ||3||style="background:#FFDCDC"|7||8
|}
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
{| class="wikitable" style="center"
|-align="center"
| обратный порядок||style="background:#FFFFC8"|11||style="background:#FFDCDC"|7||style="background:#DCFFDC"|5||style="background:#E6E6FF"|2||style="background:#DCFFFF"|1
|-align="center"
| НВП||style="background:#DCFFFF"|1||style="background:#E6E6FF"|2||style="background:#DCFFDC"|5||style="background:#FFDCDC"|7||style="background:#FFFFC8"|11
|}
===Оценка времени работы===
Так как размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, а количество блоков всего <tex>\lceil n/m \rceil</tex>. То количество присваиваний новых ключей элементам последовательности не больше <tex>2cm\cdot\dfrac{n}{m}=O(n)</tex>, где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(\log \log m)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m</tex>.
Докажем, что реализация данного алгоритма будет работать за время <tex>O(n \log \log m)</tex> для последовательности длины n.
Рассмотрим последовательность <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>.
Будем по порядку для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди <tex>B</tex> становится больше <tex>m_i</tex>, то условие <tex>m \geqslant k</tex> перестает выполняться, тогда останавливаем алгоритм, и переходим к следующему элементу <tex>m_{i+1}</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant k</tex>, то алгоритм успешно завершится.
Таким образом, время работы алгоритма — <tex>O(n \log \log {m_i})</tex> для <tex>0\leqslant i < j</tex>, потому что во время работы очередь <tex>B</tex> хранит не более <tex>m_i</tex> элементов, ключи которых не больше <tex>2m_i</tex>. Для значения <tex>m_j</tex> алгоритм успешно завершается, так как условие полной обработки последовательности <tex>m\geqslant k</tex> выполняется. Таким образом, время работы алгоритма для <tex>m_j</tex> также <tex>O(n\log \log {m_j})</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>
Общее время работы алгоритма — <tex>O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \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>.
== См. также ==
*[[Дерево ван Эмде Боаса]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Наибольшая общая возрастающая подпоследовательность]]
*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Источники информации ==
* [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)] (07.01.2017)
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Классические задачи динамического программирования]]
