Участник:Artem.ustinov/НВП

Задача:

Дана перестановка $\pi$ множества$~\{1, 2,~\dots,~n\}$. Требуется найти НВП $\pi$ за $O(n\operatorname{log}\operatorname{log}k)$, где $k$ — длина НВП.

Алгоритм за O(n log log n)

Нахождение длины НВП

Основная идея

Пусть $\{\pi_1,\pi_2,~\dots,~\pi_n\}$ — входная перестановка.

Будем последовательно обрабатывать элементы в порядке $\pi_1, \pi_2,~\dots,~\pi_n\colon$

Для каждой длины $l = 1, 2,~\dots,~n$ предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины $l$ и запишем его в массив $B_l$. Будем называть его наилучшим элементом для длины $l$.

• Если $\pi_i$ больше каждого элемента $B$, вычисленного для подпоследовательности $\pi_1, \pi_2,~\dots~,\pi_{i-1}$, тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец $B$.
• Иначе $\pi_i$ будет наилучшим элементом для уже существующей длины, тогда мы находим наименьшее $k\colon B_k \gt \pi_i$ и заменяем $B_k$ элементом $\pi_i$.

Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции $\mathrm{insert}, \mathrm{next}, \mathrm{delete}$, соответственно целесообразно использовать приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Так как данная структура данных производит описанные операции за $O(\operatorname{log} k)$, где k — количество бит чисел, которые позволяет хранить дерево, то полученный алгоритм работает за $O(n\operatorname{log}\operatorname{log} n)$, потому что все элементы последовательности не превосходят n.

Пример

Типы операций

• Добавление элемента, который больше всех предыдущих:

• Замещение элемента более подходящим, т.е. добавление немаксимального элемента:

$\longrightarrow$

Пример последовательности

$\pi_1$	$\pi_2$	$\pi_3$	$\pi_4$	$\pi_5$	$\pi_6$	$\pi_7$	$\pi_8$	$\pi_9$	$\pi_{10}$	$\pi_{11}$	$\pi_{12}$
9	3	10	4	8	1	2	12	6	5	7	11

Состояние очереди при каждом добавлении

$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$~\pi_i~$
9					9
3					3
3	10				10
3	4				4
3	4	8			8
1	4	8			1
1	2	8			2
1	2	8	12		12
1	2	6	12		6
1	2	5	12		5
1	2	5	7		7
1	2	5	7	11	11

Псевдокод

int LIS([math]\pi[/math][n])

   PriorityQueue B // рабочая приоритетная очередь
   int k = 0       // длина НВП
   for i = 1 to n
       x = [math]\pi[/math][i]
       // в любом случае добавляем в очередь очередной элемент
       // устаревшие будем удалять
       B.insert(x)
       if [math]\exists[/math] B.next(x)
           // добавленный элемент — не максимальный
           // удаляем следующее за x значение
           B.delete(B.next(x))
       else
           // добавленный элемент — максимальный
           // предыдущие значения не трогаем, очередь увеличилась
           k = k + 1           
   return k

Расширение алгоритма до нахождения НВП

Основная идея

Будем запоминать пары: для каждого элемента записываем его "предшественника".

Тогда, пройдя по предшественникам, начиная с последнего элемента очереди $B$, мы можем восстановить НВП.

Общий вид алгоритма

$B_1$	$B_2$	$B_3$	$B_4$	$B_5$	$~\pi_i~$
9					9
3					3
3	10				10
3	4				4
3	4	8			8
1	4	8			1
1	2	8			2
1	2	8	12		12
1	2	6	12		6
1	2	5	12		5
1	2	5	7		7
1	2	5	7	11	11

predecessor
1	2	3	4	5	6	7	8	9	10	11	12
	1		3	2	2	5	4		3	7	8

Псевдокод

int[] LIS([math]\pi[/math][n])

   PriorityQueue B
   int k = 0
   int predecessor[n] // резервируем [math]n[/math] позиций
   for i = 1 to n
       x = [math]\pi[/math][i]
       B.insert(x)
       predecessor[x] = B.prev(x)
       if [math]\exists[/math] B.next(x)
           B.delete(B.next(x))
       else
           k = k + 1
   // по цепочке от последнего элемента 
   // восстанавливаем НВП
   int result[k]
   int cur = B.max
   for i = k - 1 downto 0
       result[i] = cur
       cur = predecessor[cur]
   return result

Оптимизация до O(n log log k)

Чтобы Дерево ван Эмде Боаса выполняло операции за $O(\operatorname{log}\operatorname{log}k)$, необходимо алфавит обрабатываемых значений уменьшить до $O(k)$.

Предположим, мы знаем такое приближение числа $k$ числом $m: m \geqslant k$. Мы обсудим, как найти такое $m$ позже.

Чтобы достичь нужной оценки, будем делить последовательность на блоки длины $m$, кроме последнего, который может быть меньше, и обрабатывать каждый блок отдельно.

Деление на блоки

Последовательность $S$ делится на блоки $C_j,~j=1,~\dots,~\lceil\frac{n}{m}\rceil$ элементов: $C_j=(\pi_{(j-1)m+1},\pi_{(j-1)m+2},~\dots~,\pi_{(j-1)m+m)})$

Обозначим за $C_j^s$ отсортированный блок $C_j$. Отсортированные и неотсортированные блоки будем хранить в памяти.

Цифровая сортировка каждых блоков отдельно будет давать нам время рваботы $O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)$. Чтобы отсортировать их за линейное время, дополним каждый элемент номером его блока и получим пары $\langle\lceil i/m\rceil,\pi_i\rangle$. Цифровая сортировка этих пар, если принимать за старший разряд номер блока, а за младший значение элемента, будет работать за $O(n)$, потому что значения элементов и номера блоков не превосходят $n$.

Обработка блока

Обрабатывая блоки, будем работать не со значениями элементов, а с ключами, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн, то есть мы не перейдём к обработке следующего блока, пока не закончим с текущим.

Каждому элементу $x$ взаимно однозначно сопоставим ключ $y = \mathtt{key}(x);~x=\mathtt{elt}(y)$. Все значения ключей расположим в промежутке $\{1,2,\dots,2m\}$, и в очереди $B$ будем работать со значениями ключей элементов.

Чтобы определить ключи элементов так, чтобы их значения были в представленном промежутке, будем, работая с блоком $C_j$, сливать элементы, ключи которых находятся в очереди $B$, с $C_j^s$ в список $\mathtt{merged}$. Получим ключи, сопоставив каждому элементу в $\mathtt{merged}$ его позицию в этом списке. Как было замечено ранее, элементы, чьи ключи находятся в $B$ располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию слияния. Поскольку мы предположили, что $m\geqslant k$, то количество ключей в $B$ не больше $m$, тогда длина $\mathtt{merged}$ не больше $2m$, что позволяет однозначно определить ключи на множестве $\{1,2,\dots,2m\}$.

После того, как мы определили новые ключи для элементов, обновим ключи в очереди $B$.

Затем запускаем описанный выше алгоритм $\mathrm{LIS}$, для ключей элементов $C_j$ в порядке исходной последовательности.

В итоге, обработка блока делится на следующие этапы:

• Достаем из очереди $B$ ключи $x$, конвертируем их в элементы $\mathtt{elt}(x)$ и кладём в список $\mathtt{elems}$.
• Сливаем элементы в $\mathtt{elems}$ со следующим отсортированным блоком в список $\mathtt{merged}$.
• Присваеваем новые ключи элементам в порядке списка $\mathtt{merged}$.
• Вставляем в $B$ новые ключи элементов списка $\mathtt{elems}$.
• Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма $\mathrm{LIS}$. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключами элементов $\mathtt{elt}(x)$.

Доказательство оптимальности

Утверждение:

Пусть имеется последовательность $S=\{\pi_1,~\dots,~\pi_n\}$, разбитая на $\lceil n/m \rceil$ блоков $C_i$ длины $m$. В результате описанного выше алгоритма получается очередь $B$, размер которой равен длине НВП последовательности $S$.

$\triangleright$

Докажем по индукции, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь $B$ хранит ключи наилучших элементов для каждой длины возрастающих подпоследовательностей, входящих в уже обработанную последовательность элементов. Пусть перед обработкой блока $C_i$ в очереди $B$ хранятся ключи наилучших элементов, вычисленные для подпоследовательности $S_{(i-1)m}=\{\pi_1,~\dots,~\pi_{(i-1)m}\}$. После слияния элементов очереди $B$ и блока $C_i^s$ получаем отсортированный список $\mathtt{merged}$. Cопоставив ключи элементам в списке, как их позиции в нём, выполняется условие $(\pi_{u_j}\lt \pi_{u_k} \Longleftrightarrow \mathtt{key}(\pi_{u_j})\lt \mathtt{key}(\pi_{u_k}))$, где $\pi_{u_j},\pi_{u_k}\in \mathtt{merged}$. Тогда справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Во время обработки ключей элементов алгоритм $\mathtt{LIS}$ работает только с очередью $B$ и не зависит от предыдущих элементов последовательности, ключи которых не находятся в очереди. Так как на каждой итерации алгоритма $\mathtt{LIS}$ сохраняется описанный инвариант для наилучших значений ключей элементов каждой длины возрастающих подпоследовательностей обработанной последовательности $S_j$, которые соответствуют ключам наилучших элементов $S_j$. то по завершению работы алгоритма $\mathtt{LIS}$ на блоке $C_i$ результатом его работы будет очередь, в которой хранятся ключи, соответствующие наилучшим элементам каждой длины возрастающих подпоследовательностей, входящих в $S_{im}$. Таким образом, после обработки последнего блока, в очереди $B$ будут храниться ключи наилучших элементов для каждой длины возрастающих подпоследовательностей последовательности $S_n=S$. Тогда последний элемент в очереди $B$ соответствует наилучшему элементу длины НВП последовательности $S$, а так как в очереди $B$ хранятся наилучшие элементы длин всех возрастающих подпоследовательностей $S$, то размер очереди $B$ равен длине НВП последовательности $S$.

$\triangleleft$

Пример

Предположим, что $m=5$. Исходно получаем:

Блок	1	1	1	1	1	2	2	2	2	2	3	3
$\pi$	9	3	10	4	8	1	2	12	6	5	7	11

После сортировки:

Блок	1	1	1	1	1	2	2	2	2	2	3	3
$\pi$	3	4	8	9	10	1	2	5	6	12	7	11

Первый блок

Первый блок $\pi$ 9 3 10 4 8 key 4 1 5 2 3

Cортированный $\pi$ 3 4 8 9 10 key 1 2 3 4 5

Обработка блока с помощью алгоритма $\mathrm{LIS}$.

$B_1$	$B_2$	$B_3$	$key$	$\pi$
4			4	9
1			1	3
1	5		5	10
1	2		2	4
1	2	3	3	8

В результате получаем

$B: \{1, 2, 3\}$

$\mathtt{merged}: \{3,4,8,9,10\}$

Второй блок

Восстанавливаем элементы $B: \{1, 2, 3\}$ из $\mathtt{merged}: \{3, 4, 8, 9, 10\}$: $\{3, 4, 8\}$.

Сливаем $C_2^s$ и восстановленные элементы из $B$:

$B$ 3 4 8

$C_2^s$ 1 2 5 6 12

$\mathtt{merged}$ 1 2 3 4 5 6 8 12 1 2 3 4 5 6 7 8

Второй блок $\pi$ 1 2 12 6 5 key 1 2 8 6 5

Cортированный $\pi$ 1 2 5 6 12 key 1 2 5 6 8

Обновляем ключи в очереди:

$B_1$	$B_2$	$B_3$	$\pi$
3			3
3	4		4
3	4	7	7

запускаем $\mathrm{LIS}$ для блока:

$B_1$	$B_2$	$B_3$	$B_4$	$key$	$\pi$
1	4	7		1	1
1	2	7		2	2
1	2	7	8	8	12
1	2	6	8	6	6
1	2	5	8	5	5

В результате получаем:

$B: \{1, 2, 5, 8\}$

$\mathtt{merged}: \{1,2,3,4,5,6,8,12\}$

Третий блок

Восстанавливаем элементы $B: \{1, 2, 5, 8\}$ из $\mathtt{merged}: \{1, 2, 3, 4, 5, 6, 8, 12\}$: $\{1, 2, 5, 12\}$.

Сливаем $C_3^s$ и восстановленные элементы из $B$:

$B$ 1 2 5 12

$C_3^s$ 7 11

$\mathtt{merged}$ 1 2 5 7 11 12 1 2 3 4 5 6

третий блок $\pi$ 7 11 key 4 5 Cортированный $\pi$ 7 11 key 4 5 Обновление старых ключей: $B_1$ $B_2$ $B_3$ $B_4$ $\pi$ 1 1 1 2 2 1 2 3 3 1 2 3 6 6 запускаем $\mathrm{LIS}$ для блока: $B_1$ $B_2$ $B_3$ $B_4$ $B_5$ $key$ $\pi$ 1 2 3 4 4 7 1 2 3 4 5 5 11 Результат завершения алгоритма: $B: \{1, 2, 3, 4, 5\}$ $\mathtt{merged}: \{1,2,5,7,11,12\}$ Получаем, что длина НВП — $5$, и НВП оканчивается на $\mathtt{merged}[5]=11$. Восстановление НВП $\mathtt{predecessor}$ 1 2 3 4 5 6 7 8 9 10 11 12 1 3 2 2 5 4 3 7 8 Начинаем восстановление с $\mathtt{merged}[5] = 11$: обратный порядок 11 7 5 2 1 НВП 1 2 5 7 11 Оценка времени работы Так как размер списка $\mathtt{merged}$ не больше $2m$, а количество блоков всего $\lceil n/m \rceil$. То общее количество присваиваний новых ключей элементам последовательности, также как и количество операций слияния списков, не больше $2cm\cdot\dfrac{n}{m}=O(n)$, где c — некоторая константа. Каждая операция с приоритетной очередью требует $O(\log \log m)$ времени, так как элементы в $B$ не больше $2m$. Рассмотрим последовательность $\{m_0,~m_1,~m_2,~\dots\}$, где $m_{i+1} = m_i ^{\operatorname{log}m_i} = 2^{\operatorname{log}^2m_i}$, $m_0$ — некоторое значение, меньшее $k$. Будем по порядку для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди $B$ становится больше $m_i$, то условие $m \geqslant k$ перестает выполняться, тогда останавливаем алгоритм и переходим к следующему значению $m_{i+1}$. Когда найдётся первое $m_j:m_j\geqslant k$, то алгоритм успешно завершится. Таким образом, время работы запущенного алгоритма — $O(n \log \log {m_i})$ для $0\leqslant i \leqslant j$. Заметим, что $\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$. $\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i$ Общее время работы алгоритма по всем $m_i$ — $O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \log m_i)$. Обратим внимание, что $m_i \lt k^{\operatorname{log}k}$, так как в противном случае $m_{i-1} \gt k$, что противоречит тому, что $m_i$ — первый из тех, которые больше $k$. Следовательно, [math]\operatorname{log}\operatorname{log}m_i \lt 2\operatorname{log}\operatorname{log}k \[/math]. Тогда алгоритм также работает за время $O(n\operatorname{log}\operatorname{log}k)$. См. также Дерево ван Эмде Боаса Задача о наибольшей возрастающей подпоследовательности Задача о наибольшей общей подпоследовательности Наибольшая общая возрастающая подпоследовательность Задача о наибольшей общей палиндромной подпоследовательности Источники информации Computing a Longest Increasing Subsequence of Length k in Time O(n log log k) (07.01.2017)