748
правок
Изменения
→Псевдокод
{{Задача
|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>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 k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательнообсудим, т.е. с предыдущего блока у нас может остаться как найти такое <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока - получаем верхнее ограничение в <tex>k + m</tex> обрабатываемых возможных значенийпозже.)
[[Цифровая сортировка]] каждого блока отдельно будет давать нам время работы <tex>O \operatorname{log}left(\operatornamedfrac{logn}m_{i+1m} n \right) = O \operatorname{log}left(\operatornamedfrac{log}n^2^{\operatorname{log}^2m_i} = \operatorname{logm}\operatorname{log}^2m_i = 2right)</tex>. Дополним каждый элемент <tex>\operatorname{log}\operatorname{log}m_ipi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, рассматривая номер блока как старший разряд, элемент как младший разряд (по смещению внутри блока не сортируем), можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки <tex>\operatorname{log}xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент <tex>\operatorname{log}m_j = 2pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на позиции <tex>i</tex>, то в блоке <tex>C_j^{j-i}\operatorname{log}s</tex> он на позиции <tex>\operatorname{log}m_ixi_i</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>\{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>\xi_j</tex>, получаем последовательность ключей в порядке исходного блока. Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</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{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>\mathtt{ind_1}</tex>).* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>. ====Пример== Основная идея == ''' Первый блок ''' Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Присвоим ключи элементам в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке. {|| ||{| class="wikitable" style="text-align:center"! colspan="6"|Сортированный|-| <tex>\pi</tex> ||<tex>3</tex>||<tex>4</tex>||<tex>8</tex>||<tex>9</tex>||<tex>10</tex>|-| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>|}| ||{| class="wikitable" style="text-align:center"! colspan="6"|Первый блок|-* | <tex>\pi</tex> ||<tex>9</tex>||<tex>3</tex>||<tex>10</tex>||<tex>4</tex>||<tex>8</tex>|-| <tex>key</tex> ||<tex>4</tex>||<tex>1</tex>||<tex>5</tex>||<tex>2</tex>||<tex>3</tex>|-| <tex>\xi_1</tex> ||<tex>4</tex>||<tex>1</tex>||<tex>5</tex>||<tex>2</tex>||<tex>3</tex>|}|} Обработка блока с помощью алгоритма <tex>\mathrm{LIS}</tex>. {Acronym|Достаем 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:#FFC9C9"| <tex>4</tex> || || || style="background: #CFCFFF"| <tex>4</tex> || style="background: #B9FFB9"| <tex>9</tex>|-align="center" | style="background:#FFC9C9"| <tex>1</tex> || || || style="background: #CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>3</tex>|-align="center" | <tex>1</tex> || style="background:#FFC9C9"| <tex>5</tex> || || style="background: #CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>10</tex>|-align="center" | <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> || || style="background: #CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>4</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>3</tex> || style="background: #CFCFFF"| <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> и присваиваем элементам ключи как индексы элементов в полученном списке:{|| ||{| class="wikitable" style="center"|-align="center"| colspan="3"|<tex>B</tex>|-align="center"| <tex>3</tex>||<tex>4</tex>||<tex>8</tex>|}| ||{| class="wikitable" style="center"|-align="center"| colspan="5"|<tex>C_2^s</tex>|-align="center"| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>|}|} {|| ||{| class="wikitable" style="center"|-align="center"! colspan="9"|<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>|-align="center"|<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>7</tex>||<tex>8</tex>|}| ||{| class="wikitable" style="center"|-align="center"| colspan="3"|<tex>\mathtt{ind_1}</tex>|-align="center"| <tex>3</tex>||<tex>4</tex>||<tex>7</tex>|}| ||{| class="wikitable" style="center"|-align="center"| colspan="5"|<tex>\mathtt{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>|-| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>|}| ||{| class="wikitable" style="text-align:center"! colspan="6"|Второй блок|-| <tex>\pi</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>|-| <tex>\xi_2</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>4</tex>||<tex>3</tex>|}|} Обновляем ключи в очереди :{| class="wikitable" style="center" style="background: #ffffcc"! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>|-align="center" | style="background:#FFC9C9"| <tex>3</tex> || || || style="background: #CFCFFF"| <tex>3</tex>|-align="center" | <tex>3</tex> || style="background:#FFC9C9"| <tex>4</tex> || || style="background: #CFCFFF"| <tex>4</tex>|-align="center" | <tex>3</tex> || <tex>4</tex> || style="background:#FFC9C9"| <tex>7</tex> || style="background: #CFCFFF"| <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:#FFC9C9"| <tex>1</tex> || <tex>4</tex> || <tex>7</tex> || || style="background: #CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>1</tex>|-align="center" | <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> || <tex>7</tex> || || style="background: #CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>2</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || <tex>7</tex> || style="background:#FFC9C9"| <tex>8</tex> || style="background: #CFCFFF"| <tex>8</tex> || style="background: #B9FFB9"| <tex>12</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>6</tex> || <tex>8</tex> || style="background: #CFCFFF"| <tex>6</tex> || style="background: #B9FFB9"| <tex>6</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>5</tex> || <tex>8</tex> || style="background: #CFCFFF"| <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> '''Третий блок''' Восстанавливаем элементы <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"| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>12</tex>|}| ||{| class="wikitable" style="center"|-align="center"| colspan="2"|<tex>C_3^s</tex>|-align="center"| <tex>7</tex>||<tex>11</tex>|}|} {|| ||{| class="wikitable" style="center"|-align="center"! colspan="7"|<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>|-align="center"|<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>|}| ||{| class="wikitable" style="center"|-align="center"| colspan="4"|<tex>\mathtt{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>\mathtt{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="3"| Третий блок |-| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>|-| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>|}| ||{| class="wikitable" style="text-align:center"! colspan="3"|Cортированный|-| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>|-| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>|-| <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:#FFC9C9"| <tex>1</tex> || || || || style="background: #CFCFFF"| <tex>1</tex>|-align="center" | <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> || || || style="background: #CFCFFF"| <tex>2</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>3</tex> || || style="background: #CFCFFF"| <tex>3</tex>|-align="center" | <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || style="background:#FFC9C9"| <tex>6</tex> || style="background: #CFCFFF"| <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:#FFC9C9"| <tex>4</tex> || || style="background: #CFCFFF"| <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:#FFC9C9"| <tex>5</tex> || style="background: #CFCFFF"| <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>|-align="center"| НВП||style="background:#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>\pioperatorname{log}\operatorname{log}m_i < 2\operatorname{log}\operatorname{log}k \</tex>.
== См. также ==*[[Дерево ван Эмде Боаса]]*[[Задача о наибольшей возрастающей подпоследовательности]]* На массив индексов, относящиеся к новому блоку, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений {{Acronym|ключей|смещений}} к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне <tex>O(m)</tex>. [[Задача о наибольшей общей подпоследовательности]]*[[Наибольшая общая возрастающая подпоследовательность]]*[[Задача о наибольшей общей палиндромной подпоследовательности]]
== Источники информации ==* Первый массив индексов, который соответствует элементам, ранее находящимся в очереди, вновь кладутся в очередь [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf Computing a Longest Increasing Subsequence of Length k in Time O(обычными <tex>insert</tex>-амиn log log k)] (07. Второй массив обрабатывается описанным выше алгоритмом <tex>LIS</tex>01.2017)