1632
правки
Изменения
м
{{В разработке}}
Для каждой длины Будем последовательно обрабатывать элементы в порядке <tex>l = 1\pi_1, 2\pi_2, ~\dots</tex> предполагаемой НВП находим наименьший {{Acronym | элемент| назовем его лучшим элементом для заданной длины }}, что может быть последним в возрастающей подпоследовательности длины <tex>l</tex>, запишем их в массив <tex>B[l]~\pi_n\colon</tex>.
Если обрабатываемый элемент Для каждой длины <tex>l = 1, 2,~\pi(i)dots,~n</tex> больше последнего элемента какой-нибудь возрастающей последовательностипредполагаемой НВП находим наименьший элемент, он который может ее увеличитьбыть последним в возрастающей подпоследовательности длины <tex>l</tex> и запишем его в массив <tex>B_l</tex>. Будем называть его наилучшим элементом для длины <tex>l</tex>.
Будем последовательно обрабатывать элементы * Если <tex>\pi(1)pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для подпоследовательности <tex>\pi_1, \pi(2)pi_2,~\dots~,\pi_{i-1}</tex>, тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит,~записываем его в конец <tex>B</tex>.* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины и сможет улучшить только один элемент в <tex>B</tex>, тогда мы находим наименьшее <tex>k\colon B_k > \pi_i</tex> и заменяем <tex>B_k</tex> элементом <tex>\pi(n)pi_i</tex>:.
* Если Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <tex>\pi(i)</tex> больше mathrm{{Acronym | <tex>\pi(1)insert}, \pi(2)mathrm{next},~\dots~,\pi(i-1)mathrm{delete}</tex> , соответственно целесообразно использовать [[ Приоритетные очереди | всех уже полученных значений B }}приоритетную очередь]], значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательностьреализованную через [[Дерево ван Эмде Боаса]]. Записываем его в конец <tex>B</tex>* Иначе Так как данная структура данных производит описанные операции за <tex>O(\pi(ioperatorname{log} k)</tex> заменяет наименьший лучший элемент, из техгде k — количество бит чисел, что больше которые позволяет хранить дерево, то полученный алгоритм работает за <tex>O(n\operatorname{log}\pi(ioperatorname{log} n)</tex>, потому что все элементы последовательности не превосходят n.
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию.
{{Acronym |Последовательность: | именно она будет рассматриваться далее}}''' Пример последовательности '''
<code> '''int''' LIS('''vector<int>''' <tex>\pi</tex>[n]) '''PriorityQueue''' B <font color=darkgreen>// рабочая приоритетная очередь</font> '''int''' k = 0 <font color=darkgreen>// длина НВП</font> '''intfor''' n i = <tex>\pi</tex>.size 1 '''forto''' 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 значение — заменяем {{Acronym |следующий|минимальный из бóльших}}</font> B.delete(B.next(x)) '''else''' <font color=darkgreen>// добавленный элемент - — максимальный</font> <font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font> k = k + 1 '''return''' k</code>
<code>
'''vector<int>''' LIS('''vector<int>''' <tex>\pi</tex>)
'''PriorityQueue''' B
'''int''' k = 0
'''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)
<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>'''vector<int>''' result
'''int''' cur = B.max()
result += [cur]
'''while''' <tex>\exists</tex> predecessor[cur]
result += [predecessor[cur]]
cur = predecessor[cur]
'''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|приближение '''int[]''' LIS(<tex>k\pi</tex>|далее рассмотрим нахождение и насколько оно точное}} [n]) '''PriorityQueue''' B '''int''' k = 0 <texfont color=blue>m: m \ge k'''int''' predecessor[n]</texfont>. Если мы разобьем всю последовательность на блоки из {{ Acronym|<texfont color=darkgreen>m// резервируем </tex> элементов|последний блок может быть меньше}} и нам удастся обрабатывать каждый как перестановку из n</tex>mпозиций</texfont> элементов, то мы получим асимптотическое время '''for''' i = 1 '''to''' n x = <tex>O(n \operatorname{log} \operatorname{log} (k + m))pi</tex>, а т.к[i] B. insert(x) <texfont color=blue>m \ge kpredecessor[x] = B.prev(x)</texfont>, то '''if''' <tex>O(n \operatorname{log} \operatorname{log} m)exists</tex>B. next(Мы будем обрабатывать блоки последовательно, тx) B.еdelete(B. с предыдущего блока у нас может остаться next(x)) '''else''' k = k + 1 <texfont color=darkgreen>k</tex> значений в очереди, которые дополняются <tex>m/ по цепочке от последнего элемента // восстанавливаем НВП</texfont> значениями очередного блока - получаем верхнее ограничение в <texfont color=blue>'''int''' result[k] '''int''' cur = B.max '''for''' i = k + m- 1 '''downto''' 0 result[i] = cur cur = predecessor[cur] '''return''' result</texfont> обрабатываемых возможных значений.)
'''''Описанный здесь алгоритм подбора <tex>m_i</tex> и получение асимптотической оценки == Оптимизация до O(n log log k) =====Основная идея===Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(n\operatorname{log}\operatorname{log}k)</tex> в других подразделах рассмотрено не будет, тнеобходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.к. в основном это доказательство, сложного для понимания/реализации ничего нет'''''
Рассмотрим последовательность Предположим, мы знаем такое приближение числа <tex>\{m_0,~m_1,~m_2,~\dots\}k</tex>, где числом <tex> m_{i+1} = m_i ^{m: m \operatorname{log}m_i} = 2^{\operatorname{log}^2m_i}</tex>, <tex>m_0geqslant k</tex> - некоторое значение. Мы обсудим, меньшее как найти такое <tex>km</tex>позже.
Будем последовательно для Во время обработки ключей элементов этой последовательности запускать {описанный выше алгоритм <tex>\mathrm{Acronym|алгоритм|о котором ниже}LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, которые не находятся в очереди. Если условие Поэтому, если мы разобьем всю последовательность на блоки из <tex>m \ge k</tex> перестает выполнятьсяэлементов (последний блок может быть меньше), прерываем выполнение. Таким образоми нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, время работы для каждого сохраняя очередь <tex>m_jB</tex> будет для вычисленных ранее блоков, то мы получим асимптотическое время <tex>O(n\operatorname{log}\operatorname{log}m_j(k + m))</tex>. , а так как <tex>m \geqslant k</tex>, то <tex>O(n \operatorname{log} \operatorname{Acronym|Найдется|первый из подобныхlog}} такой m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>m_ik</tex>значений в очереди, который окажется больше которые дополняются <tex>m</tex> значениями очередного блока — получаем верхнее ограничение в <tex>k+ m</tex>, и алгоритм успешно завершитсяобрабатываемых возможных значений. )
{{Acronym|Общее [[Цифровая сортировка]] каждого блока отдельно будет давать нам время|для всех обработанных значений m}} работы - <tex>O\left(n(\sum\limits_dfrac{j = 0n}\limits^{im}2^{1-j})n \operatorname{log}\operatorname{log}m_iright) = O\left(n\operatornamedfrac{logn^2}\operatorname{logm}m_i\right)</tex>. Заметим, что Дополним каждый элемент <tex>m_i < k^{\operatorname{log}k}pi</tex>номером блока, тв котором он находится и смещением в этом блоке.к. в противном случае <tex>m_{i-1} > k</tex>Теперь, рассматривая номер блока как старший разряд, что противоречит томуэлемент как младший разряд (по смещению внутри блока не сортируем), что можно сортировать цифровой сортировкой за линейное время <tex>m_iO(n)</tex> - первый из тех, потому что больше значения элементов и номера блоков не превосходят <tex>k</tex>. Следовательно, <tex>\operatorname{log}\operatorname{log}m_i < 2\operatorname{log}\operatorname{log}k \n</tex>.
Получаем время работы Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки <tex>O(n\operatorname{log}\operatorname{log}k)xi</tex>=== Деление на блоки ======= Основная идея ====Разделим исходную перестановку , элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент <tex>\pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на блоки позиции <tex>i</tex>, то в блоке <tex>C_j = \{\pi_{(j-1)m + 1},~\pi_{(j-1)m + 2},~\dots, ~\pi_{(j-1)m + m}^s</tex> он на позиции <tex>\}xi_i</tex>.
Получим сортированные варианты этих блоков <tex>C_j^S====Пример====Предположим, что </tex>. При лобовой {{Acronym|цифровой|radix}} сортировке мы получим <tex>O(\frac{n}{m}n)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)=5</tex>.Исходно получаем:
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>
==== Пример ====
Пусть <tex>m = 5</tex>. Исходно:
* Классический [[Сортировка слиянием#Принцип работы#Слияние двух массивов | merge]] только что полученных элементов Оставшиеся ключи, которые входят в <tex>\pimathtt{merged}</tex> с элементами нового блока, но с модификацией: генерируются 2 массива - индексы не являются ключами элементов исходных массивов в новомобрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
* На массив индексов, относящиеся к новому блокуЗатем запускаем алгоритм <tex>\mathrm{LIS}</tex>, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений {{Acronym|для ключей|смещений}} к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне <tex>O(m)C_j</tex>в порядке исходной последовательности.
[[Файл:blockHandle.jpg]]''' Первый блок '''
Для первого блока содержательным является лишь веткаТак как очередь <tex>B</tex> в начале пуста, начинающаяся с то <tex>C_j\mathtt{merged}=C_1^S \longrightarrow merge \longrightarrow ind's</tex>. Присвоим ключи элементам в списке <tex>\#1mathtt{merged}</tex>как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, что не противоречит представленной схемедействуя перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке.
==== Пример ====
===== Первый блок =====
''' Результат работы '''В результате получаем
| ! colspan="89"|<tex>\mathtt{merged}</tex>|-align="center"|<tex>\pi</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>||<tex>12</tex>
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="5"| новые ключи
|-align="center"
| 1||2||8||6||5
Обновление старых ключейОбновляем ключи в очереди:{| class="wikitable" style="center"style="background: #ffffcc"! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</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> и присваиваем ключи элементам:
| ! colspan="87"|<tex>\mathtt{merged}</tex>|-align="center"|<tex>\pi</tex>||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>7</tex>||<tex>11</tex>||<tex>12</tex>
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="2"| новые ключи
|-align="center"
| 4||5
''' Результат работы '''завершения алгоритма:
rollbackEdits.php mass rollback
{{Задача
|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <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]]
== Алгоритм <tex>за O(n\operatorname{log}\operatorname{log}n)</tex> ==
=== Нахождение длины НВП ===
==== Основная идея ====
Пусть <tex>\pi(n){\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка.
==== Пример ====
''' Типы операций''' * Добавление элемента, который больше всех предыдущих:
[[Файл: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"
| <tex>9 </tex> || <tex>3 </tex> || <tex>10 </tex> || <tex>4 </tex> || <tex>8 </tex> || <tex>1 </tex> || <tex>2 </tex> || <tex>12 </tex> || <tex>6 </tex> || <tex>5 </tex> || <tex>7 </tex> || <tex>11</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"
| style="background:#FFCC00FFCFCF"| <tex>9 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>9</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>3 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3 </tex> || style="background:#FFCC00FFCFCF"| <tex>10 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>10</tex>
|-align="center"
| <tex>3 </tex> || style="background:#FFCC00FFCFCF"| <tex>4 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3 </tex> || <tex>4 </tex> || style="background:#FFCC00FFCFCF"| <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>8</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>1 </tex> || <tex>4 </tex> || <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFCFCF"| <tex>2 </tex> || <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>8 </tex> || style="background:#FFCC00FFCFCF"| <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>12</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFCFCF"| <tex>6 </tex> || <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFCFCF"| <tex>5 </tex> || <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>5</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>5 </tex> || style="background:#FFCC00FFCFCF"| <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>5 </tex> || <tex>7 </tex> || style="background:#FFCC00FFCFCF"| <tex>11 </tex> || style="background: #77A9F4CFCFFF"| <tex>11</tex>
|}
==== Псевдокод ====
=== Расширение алгоритма до нахождения НВП ===
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, выбрав какой-нибудь лучший элемент для максимальной длиныпройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем легко {{Acronym | восстановить НВП | вообще говоря, не все }}.
==== Общий вид алгоритма ====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
! <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"
| <tex>9 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>9</tex>
|-align="center"
| <tex>3 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3 </tex> || <tex>10 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>10</tex>
|-align="center"
| <tex>3 </tex> || <tex>4 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3 </tex> || <tex>4 </tex> || <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>8</tex>
|-align="center"
| style="background:#FFCC00FFDF90"| <tex>1 </tex> || <tex>4 </tex> || <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| style="background:#FF7F00FFCFCF"|<tex>1 </tex> || style="background:#FFCC00FFDF90"| <tex>2 </tex> || <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFDF90"|<tex>2 </tex> || <tex>8 </tex> || <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>12</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFDF90"|<tex>2 </tex> || <tex>6 </tex> || <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FF7F00FFCFCF"|<tex>2 </tex> || style="background:#FFCC00FFDF90"| <tex>5 </tex> || <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>5</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FF7F00FFCFCF"| <tex>5 </tex> || style="background:#FFCC00FFDF90"| <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>5 </tex> || style="background:#FF7F00FFCFCF"| <tex>7 </tex> || style="background:#FF7F00FFCFCF"| <tex>11 </tex> || style="background: #77A9F4CFCFFF"| <tex>11</tex>
|}
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! colspan="12" | predecessor
|-align="center"
! <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || <tex>4 </tex> || <tex>5 </tex> || <tex>6 </tex> || <tex>7 </tex> || <tex>8 </tex> || <tex>9 </tex> || <tex>10 </tex> || <tex>11 </tex> || <tex>12 </tex>
|-align="center"
| || <tex>1 </tex> || || <tex>3 </tex> || <tex>2 </tex> || <tex>2 </tex> || <tex>5 </tex> || <tex>4 </tex> || || <tex>3 </tex> || <tex>7 </tex> || <tex>8</tex>
|}
==== Псевдокод ====
=== Деление на блоки===Последовательность <tex>S</tex> делится на блоки <tex>C_j,~j=1,~\operatorname{log}dots,~\operatorname{log}m_{i+1} = lceil\operatornamefrac{logn}\operatorname{logm}2^{\operatorname{log}^2m_i} rceil</tex>:<tex>C_j= (\operatornamepi_{log(j-1)m+1},\operatornamepi_{log(j-1)m+2}^2m_i = 2,~\operatorname{log}dots~,\operatornamepi_{log(j-1)m+m)}m_i)</tex>
Обозначим за <tex>\operatorname{log}\operatorname{log}m_j = 2C_j^{j-i}\operatorname{log}\operatorname{log}m_is</tex>отсортированный блок <tex>C_j</tex>. Отсортированные и неотсортированные блоки будем хранить в памяти.
{| class="wikitable" style="text-align:center"
| Блок ||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#8080FFCFCFFF"|<tex>3</tex>||style="background:#8080FFCFCFFF"|<tex>3</tex>
|-
|<tex>\pi</tex>||style="background:#FF8080FFC9C9"|<tex>9</tex>||style="background:#FF8080FFC9C9"|<tex>3</tex>||style="background:#FF8080FFC9C9"|<tex>10</tex>||style="background:#FF8080FFC9C9"|<tex>4</tex>||style="background:#FF8080FFC9C9"|<tex>8</tex>||style="background:#80FF80B9FFB9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>12</tex>||style="background:#80FF80B9FFB9"|<tex>6</tex>||style="background:#80FF80B9FFB9"|<tex>5</tex>||style="background:#8080FFCFCFFF"|<tex>7</tex>||style="background:#8080FFCFCFFF"|<tex>11</tex>
|-
|Смещение||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>2</tex>||style="background:#FF8080FFC9C9"|<tex>3</tex>||style="background:#FF8080FFC9C9"|<tex>4</tex>||style="background:#FF8080FFC9C9"|<tex>5</tex>||style="background:#80FF80B9FFB9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>3</tex>||style="background:#80FF80B9FFB9"|<tex>4</tex>||style="background:#80FF80B9FFB9"|<tex>5</tex>||style="background:#8080FFCFCFFF"|<tex>1</tex>||style="background:#8080FFCFCFFF"|<tex>2</tex>
|}
После сортировки:
{| class="wikitable" style="text-align:center"
|Блок ||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#8080FFCFCFFF"|<tex>3</tex>||style="background:#8080FFCFCFFF"|<tex>3</tex>
|-
|<tex>\pi</tex> ||style="background:#FF8080FFC9C9"|<tex>3</tex>||style="background:#FF8080FFC9C9"|<tex>4</tex>||style="background:#FF8080FFC9C9"|<tex>8</tex>||style="background:#FF8080FFC9C9"|<tex>9</tex>||style="background:#FF8080FFC9C9"|<tex>10</tex>||style="background:#80FF80B9FFB9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>5</tex>||style="background:#80FF80B9FFB9"|<tex>6</tex>||style="background:#80FF80B9FFB9"|<tex>12</tex>||style="background:#8080FFCFCFFF"|<tex>7</tex>||style="background:#8080FFCFCFFF"|<tex>11</tex>
|-
|Смещение ||style="background:#FF8080FFC9C9"|<tex>2</tex>||style="background:#FF8080FFC9C9"|<tex>4</tex>||style="background:#FF8080FFC9C9"|<tex>5</tex>||style="background:#FF8080FFC9C9"|<tex>1</tex>||style="background:#FF8080FFC9C9"|<tex>3</tex>||style="background:#80FF80B9FFB9"|<tex>1</tex>||style="background:#80FF80B9FFB9"|<tex>2</tex>||style="background:#80FF80B9FFB9"|<tex>5</tex>||style="background:#80FF80B9FFB9"|<tex>4</tex>||style="background:#80FF80B9FFB9"|<tex>3</tex>||style="background:#8080FFCFCFFF"|<tex>1</tex>||style="background:#8080FFCFCFFF"|<tex>2</tex>
|}
Обратные перестановки (<tex>\xi</tex>):
{| class="wikitable" style="center" style="background:#FFCC80"
! colspan="5"|<tex>1 </tex> || colspan="5"|<tex>2 </tex> || colspan="3"|<tex>3</tex>
|-align="center"
| style="background:#FFD0D0"|<tex>4</tex>||style="background:#FFD0D0"|<tex>1</tex>||style="background:#FFD0D0"|<tex>5</tex>||style="background:#FFD0D0"|<tex>2</tex>||style="background:#FFD0D0"|<tex>3 </tex>| style="background:#D0FFD0"|<tex>1</tex>||style="background:#D0FFD0"|<tex>2</tex>||style="background:#D0FFD0"|<tex>5</tex>||style="background:#D0FFD0"|<tex>4</tex>||style="background:#D0FFD0"|<tex>3 </tex> | style="background:#D0D0FF"|<tex>1</tex>||style="background:#D0D0FF"|<tex>2</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>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{Acronym|Достаем из очереди 1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключинаходятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов |если это первый блок - ничего не делаемслияния]] за <tex>O(m)</tex>. В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливы утверждения, что <tex>\mathtt{elt}(x)=\mathtt{merged} [x]</tex> и конвертируем их в элементы <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов. Находим последовательность ключей, соответствующую элементам блока <tex>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>\pixi_j</tex>, получаем последовательность ключей в порядке исходного блока.
В итоге, обработка блока делится на следующие этапы:* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.* Первый массив индексовСливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>, который соответствует элементамгенерируя два вспомогательных массива <tex>\mathtt{ind_0}</tex> и <tex>\mathtt{ind_1}</tex>, ранее находящимся хранящих индексы элементов списков <tex>C_j^s</tex> и <tex>\mathtt{elems}</tex> соответственно в списке <tex>\mathtt{merged}</tex>.* Действуя на последовательность ключей в списке <tex>\mathtt{ind_0}</tex> перестановкой <tex>\xi_j</tex> получим ключи в очереди, вновь кладутся порядке исходной последовательности.* Вставляем в очередь <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex> (обычными элементы <tex>insert\mathtt{ind_1}</tex>-ами). Второй * Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив обрабатывается описанным выше алгоритмом "предшественников", который будет работать с соответствующими ключам элементами <tex>LIS\mathtt{elt}(x)</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'''.
{|
| ||
{| class="wikitable" style="text-align:center"! colspan="56"|Первый блокСортированный|-align="center"|style="background:#FFA080"|9<tex>\pi</tex> ||style="background:#FFDF80"|<tex>3</tex>||style="background:#FF9580"<tex>4</tex>|10|<tex>8</tex>|style="background:#FFD580"|4<tex>9</tex>||style="background:#FFAA80"|8<tex>10</tex>|-align="center"|style="background:#FFE680"<tex>key</tex> ||<tex>1</tex>||style="background:#FFCC80"|<tex>2</tex>||style="background:#FFB380"|<tex>3</tex>||style="background:#FF9980"|<tex>4</tex>||style="background:#FF8080"|<tex>5</tex>
|}
| ||
{| class="wikitable" style="text-align:center"! colspan="56"|CортированныйПервый блок|-align="center"|style="background:#FFDF80"<tex>\pi</tex> ||<tex>9</tex>||<tex>3</tex>||<tex>10</tex>|style="background:#FFD580"|<tex>4</tex>||style="background:#FFAA80"<tex>8</tex>|-| <tex>key</tex> ||<tex>4</tex>||8<tex>1</tex>||style="background:#FFA080"<tex>5</tex>|9|<tex>2</tex>|style="background:#FF9580"|10<tex>3</tex>|-align="center"|style="background:#FFCC80"<tex>\xi_1</tex> |2|<tex>4</tex>|style="background:#FF9980"|4<tex>1</tex>||style="background:#FF8080"|<tex>5</tex>||style="background:#FFE680"|1|<tex>2</tex>|style="background:#FFB380"|<tex>3</tex>
|}
|}
Обработка блока с помощью алгоритма <tex>merged\mathrm{LIS}</tex> аналогичен сортированному, т.к. предыдущих ключей нет. {| class="wikitable" style="center"! colspan="5"|Ключи сортированного блока|-align="center"| 2||4||5||1||3|}{| class="wikitable" ; style="centerbackground: #ffffcc"! colspan="5"| <tex>\xiB_1</tex>|-align="center"| 4<tex>B_2</tex>||1<tex>B_3</tex>||5||2<tex>key</tex>||3|}Пропускаем их через <tex>LIS\pi</tex>:{| class="wikitable" style="center"
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>4</tex> || style="background: #B9FFB9"| <tex>9</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>1 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>3</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || || style="background: #77A9F4CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>10</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || || style="background: #77A9F4CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>4</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFC9C9"| <tex>3 </tex> || style="background: #77A9F4CFCFFF"| <tex>3</tex> || style="background: #B9FFB9"| <tex>8</tex>
|}
<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> в <tex>\mathtt{merged}</tex> и присваиваем элементам ключи как индексы элементов в полученном списке:
{|
| ||
{| styleclass="centerwikitable"! colspanstyle="5center"|Второй блок
|-align="center"
|stylecolspan="background:#FFF4803"|1||style="background:#FFEA80"|2||style="background:#FF8080"|12||style="background:#FFC080"|6||style="background:#FFCA80"|5<tex>B</tex>
|-align="center"
|style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|<tex>3</tex>||style="background:#FF9980"|<tex>4</tex>||style="background:#FF8080"|5<tex>8</tex>
|}
| ||
{| styleclass="centerwikitable"! colspanstyle="5center"|Cортированный
|-align="center"
|stylecolspan="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FFCA80"|5||style="background:#FFC080"|6||style="background:#FF8080"|12<tex>C_2^s</tex>
|-align="center"
|style="background:#FFE680"|<tex>1</tex>||style="background:#FFCC80"|<tex>2</tex>||style="background:#FF8080"|<tex>5</tex>||style="background:#FF9980"|4|<tex>6</tex>|style="background:#FFB380"|3<tex>12</tex>
|}
|}
{| class="wikitable" style="center"
|-align="center"
|-align="center"
| <tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||8<tex>7</tex>||12<tex>8</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>ind's\#0mathtt{ind_1}</tex> - индексы текущих
|-align="center"
| <tex>3</tex>||<tex>4</tex>||<tex>7</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>ind's\#1mathtt{ind_0}</tex> - индексы новых
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>
|}
|}
Получаем ключи элементов в <tex>C_2^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_2</tex>: {|| ||{| class="wikitable" style="text-align:center"! colspan="6"|Сортированный|-| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5"</tex>||<tex>6</tex>||Ключи сортированного блока<tex>12</tex>|-align="center"| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||4<tex>6</tex>||3<tex>8</tex>
|}
| ||{| class="wikitable" style="text-align:center"! colspan="56"|Второй блок|-| <tex>\xipi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>12</tex>||<tex>6</tex>||<tex>5</tex>|-| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>8</tex>||<tex>6</tex>||<tex>5</tex>|-align="center"| <tex>\xi_2</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>4</tex>||<tex>3</tex>
|}
|}
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>3 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3 </tex> || style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3 </tex> || <tex>4 </tex> || style="background:#FFCC00FFC9C9"| <tex>7 </tex> || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|}
запускаем <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:#FFCC00FFC9C9"| <tex>1 </tex> || <tex>4 </tex> || <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>1</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>2</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>7 </tex> || style="background:#FFCC00FFC9C9"| <tex>8 </tex> || style="background: #77A9F4CFCFFF"| <tex>8</tex> || style="background: #B9FFB9"| <tex>12</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFC9C9"| <tex>6 </tex> || <tex>8 </tex> || style="background: #77A9F4CFCFFF"| <tex>6</tex> || style="background: #B9FFB9"| <tex>6</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || <tex>8 </tex> || style="background: #77A9F4CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>5</tex>
|}
<tex>B: \{1, 2, 5, 8\}</tex>
<tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</tex>
{|
| ||
{| styleclass="centerwikitable"! colspanstyle="5center"|Первый блок
|-align="center"
|stylecolspan="background:#FFB5804"|7||style="background:#FF8B80"|11<tex>B</tex>
|-align="center"
|style="background:#FFC080"<tex>1</tex>||<tex>2</tex>|1|<tex>5</tex>|style="background:#FF8080"|2<tex>12</tex>
|}
| ||
{| styleclass="centerwikitable"! colspanstyle="5center"|Cортированный
|-align="center"
|stylecolspan="background:#FFB5802"|7||style="background:#FF8B80"|11<tex>C_3^s</tex>
|-align="center"
|style="background:#FFC080"<tex>7</tex>|1||style="background:#FF8080"|2<tex>11</tex>
|}
|}
{| class="wikitable" style="center"
|-align="center"
|-align="center"
| <tex>key</tex>||<tex>1</tex>||<tex>2</tex>||5<tex>3</tex>||7<tex>4</tex>||11<tex>5</tex>||12<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>ind's\#0mathtt{ind_1}</tex> - индексы текущих
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>ind's\#1mathtt{ind_0}</tex> - индексы новых
|-align="center"
| <tex>4</tex>||<tex>5</tex>
|}
|}
Получаем ключи элементов в <tex>C_3^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_3</tex>: {|| ||{|| ||{| class="wikitable" style="text-align:center"! colspan="53"|Ключи сортированного блокаТретий блок|-| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>|-align="center"| 1<tex>key</tex> ||<tex>4</tex>||2<tex>5</tex>
|}
| ||{| class="wikitable" style="text-align:center"! colspan="53"|Cортированный|-| <tex>\xipi</tex> ||<tex>7</tex>||<tex>11</tex>|-| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>|-align="center"| <tex>\xi_3</tex> ||<tex>1</tex>||<tex>2</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>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>1 </tex> || 4 || 7 || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || 7 || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00FFC9C9"| <tex>3 </tex> || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || style="background:#FFCC00FFC9C9"| <tex>6 </tex> || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|}
запускаем <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"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || style="background: #77A9F4CFCFFF"| <tex>4</tex> || style="background: #B9FFB9"| <tex>7</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || <tex>4 </tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || style="background: #77A9F4CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>11</tex>
|}
<tex>B: \{1, 2, 3, 4, 5\}</tex>
<tex>\mathtt{merged}: \{1,2,5,7,11,12\}</tex>
Получаем, что длина НВП — <tex>5</tex>, и НВП оканчивается на <tex>\mathtt{merged}[5]===== 11</tex>. '''Восстановление НВП ====='''
{| class="wikitable" style="center"
! colspan="12"| <tex>\mathtt{predecessor}</tex>
|-align="center"
| style="background:#DCFFFF"|<tex>1</tex>||style="background:#DCDCFF"|<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>6</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8</tex>||<tex>9</tex>||<tex>10</tex>||style="background:#FFFFC8"|<tex>11</tex>||<tex>12</tex>
|-align="center"
|style="background:#FFFFC8"| ||style="background:#DCFFFF"|<tex>1</tex>|| ||<tex>3</tex>||style="background:#DCDCFF"|<tex>2</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>4</tex>|| ||<tex>3</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8 </tex>
|}
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
{| class="wikitable" style="center"
|+ -align="center"| обратный порядок| |style="background:#FFFFC8"|<tex>11</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFFF"|<tex>1</tex>|}{| class-align="wikitablecenter" | НВП||style="centerbackground:#DCFFFF"|+ НВП| <tex>1</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#FFFFC8"|<tex>11</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>. Будем последовательно для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди <tex>B</tex> становится больше <tex>m_i</tex>, то условие <tex>m \geqslant k</tex> перестает выполняться, тогда останавливаем алгоритм и переходим к следующему значению <tex>m_{i+1}</tex>. Для каждого <tex>m_i</tex> размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m_i</tex>, а количество блоков всего <tex>\lceil n/m_i \rceil</tex>. То общее количество присваиваний новых ключей элементам последовательности, также как и количество операций слияния списков, не больше <tex>2cm_i\cdot\dfrac{n}{m_i}=O(n)</tex>, где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(\log \log m_i)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m_i</tex>. Таким образом, время работы запущенного алгоритма для каждого <tex>m_i</tex> — <tex>O(n \log \log {m_i})</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant 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> Общее время работы алгоритма для всех обработанных значений <tex>m_i</tex> — <tex>O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \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>. == См. также ==*[[Дерево ван Эмде Боаса]]*[[Задача о наибольшей возрастающей подпоследовательности]]*[[Задача о наибольшей общей подпоследовательности]]*[[Наибольшая общая возрастающая подпоследовательность]]*[[Задача о наибольшей общей палиндромной подпоследовательности]] == Источники информации ==* [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) [[Категория: Дискретная математика и алгоритмы]][[Категория: Динамическое программирование]][[Категория: Классические задачи динамического программирования]]
