Быстрый поиск наибольшей возрастающей подпоследовательности

Задача:

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

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

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

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

Пусть [math]\pi(n)[/math] — входная перестановка.

Для каждой длины [math]l = 1, 2, \dots[/math] предполагаемой НВП находим наименьший элемент, что может быть последним в возрастающей подпоследовательности длины [math]l[/math], запишем их в массив [math]B[l][/math].

Если обрабатываемый элемент [math]\pi(i)[/math] больше последнего элемента какой-нибудь возрастающей последовательности, он может ее увеличить.

Будем последовательно обрабатывать элементы [math]\pi(1), \pi(2),~\dots,~\pi(n)[/math]:

• Если [math]\pi(i)[/math] больше [math]\pi(1), \pi(2),~\dots~,\pi(i-1)[/math] , значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец [math]B[/math].
• Иначе [math]\pi(i)[/math] заменяет наименьший лучший элемент, из тех, что больше [math]\pi(i)[/math].

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

Пример

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

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

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

[math]\longrightarrow[/math]

Последовательность

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

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

[math]B_1[/math]	[math]B_2[/math]	[math]B_3[/math]	[math]B_4[/math]	[math]B_5[/math]	[math]~\pi_i~[/math]
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)
               // добавленный элемент — не максимальный
               // удаляем предыдущее значение — заменяем следующий
               B.delete(B.next(x))
           else
               // добавленный элемент — максимальный
               // предыдущие значения не трогаем, очередь увеличилась
               k = k + 1           
       return k

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

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

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

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

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

[math]B_1[/math]	[math]B_2[/math]	[math]B_3[/math]	[math]B_4[/math]	[math]B_5[/math]	[math]~\pi_i~[/math]
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)

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

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

Предположим, мы знаем такое приближение числа [math]k[/math] числом [math]m: m \geqslant k[/math]. Если мы разобьем всю последовательность на блоки из [math]m[/math] элементов и нам удастся обрабатывать каждый как перестановку из [math]m[/math] элементов, то мы получим асимптотическое время [math]O(n \operatorname{log} \operatorname{log} (k + m))[/math], а т.к. [math]m \geqslant k[/math], то [math]O(n \operatorname{log} \operatorname{log} m)[/math]. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться [math]k[/math] значений в очереди, которые дополняются [math]m[/math] значениями очередного блока — получаем верхнее ограничение в [math]k + m[/math] обрабатываемых возможных значений.)

Описанный здесь алгоритм подбора [math]m_i[/math] и получение асимптотической оценки [math]O(n\operatorname{log}\operatorname{log}k)[/math] в других подразделах рассмотрено не будет, т.к. в основном это доказательство, сложного для понимания/реализации ничего нет

Рассмотрим последовательность [math]\{m_0,~m_1,~m_2,~\dots\}[/math], где [math] m_{i+1} = m_i ^{\operatorname{log}m_i} = 2^{\operatorname{log}^2m_i}[/math], [math]m_0[/math] — некоторое значение, меньшее [math]k[/math].

Будем последовательно для элементов этой последовательности запускать алгоритм. Если условие [math]m \geqslant k[/math] перестает выполняться, прерываем выполнение. Таким образом, время работы для каждого [math]m_j[/math] будет [math]O(n\operatorname{log}\operatorname{log}m_j)[/math]. Найдется такой [math]m_i[/math], который окажется больше [math]k[/math], и алгоритм успешно завершится.

[math]\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[/math]

[math]\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i[/math]

Общее время работы — [math]O(n(\sum\limits_{j = 0}\limits^{i}2^{1-j})\operatorname{log}\operatorname{log}m_i) = O(n\operatorname{log}\operatorname{log}m_i)[/math]. Заметим, что [math]m_i \lt k^{\operatorname{log}k}[/math], т.к. в противном случае [math]m_{i-1} \gt k[/math], что противоречит тому, что [math]m_i[/math] — первый из тех, что больше [math]k[/math]. Следовательно, [math]\operatorname{log}\operatorname{log}m_i \lt 2\operatorname{log}\operatorname{log}k \[/math].

Получаем время работы [math]O(n\operatorname{log}\operatorname{log}k)[/math].

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

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

Разделим исходную перестановку [math]\pi[/math] на блоки [math]C_j = \{\pi_{(j-1)m + 1},~\pi_{(j-1)m + 2},~\dots, ~\pi_{(j-1)m + m}\}[/math].

Получим сортированные варианты этих блоков [math]C_j^S[/math]. Лобовая цифровая сортировка дает нам время работы [math]O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)[/math]. Дополним каждый элемент [math]\pi[/math] номером блока, в котором он находится и смещением в этом блоке. Теперь, рассматривая номер блока как старший разряд, элемент как младший разряд, можно сортировать цифровой сортировкой за линейное время [math]O(n)[/math].

Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее [math]\xi[/math].

Пример

Пусть [math]m = 5[/math]. Исходно:

Блок	1	1	1	1	1	2	2	2	2	2	3	3
[math]\pi[/math]	9	3	10	4	8	1	2	12	6	5	7	11
Смещение	1	2	3	4	5	1	2	3	4	5	1	2

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

Блок	1	1	1	1	1	2	2	2	2	2	3	3
[math]\pi[/math]	3	4	8	9	10	1	2	5	6	12	7	11
Смещение	2	4	5	1	3	1	2	5	4	3	1	2

Обратные перестановки ([math]\xi[/math]):

1					2					3
4	1	5	2	3	1	2	5	4	3	1	2

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

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

• Достаем из очереди ключи и конвертируем их в элементы [math]\pi[/math].

• Классический merge только что полученных элементов [math]\pi[/math] с элементами нового блока, но с модификацией: генерируются 2 дополнительных массива - индексы элементов исходных массивов в новом. Слияние массивов назовем [math]\mathtt{merged}[/math].

• На массив индексов, относящиеся к новому блоку, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений ключей к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне [math]O(m)[/math].

• Первый массив индексов, который соответствует элементам, ранее находящимся в очереди, вновь кладутся в очередь (обычными [math]\mathrm{insert}[/math]-ами). Второй массив обрабатывается описанным выше алгоритмом [math]\mathrm{LIS}[/math], при том массив [math]\mathtt{predecessor}[/math] строится из ключей с помощью [math]\mathtt{merged}[/math].

Визуализация

Помеченные зеленым — условные данные. Остальное — условные операции. Например [math]\mathtt{keys} \longrightarrow \mathtt{merged}[/math] значит взять элементы из массива [math]\mathtt{merged}[/math] c индексами из [math]\mathtt{keys}[/math]. [math]\mathrm{merge} \longrightarrow \mathtt{merged}[/math] — здесь [math]\mathtt{merged}[/math] обозначает результат операции [math]\mathrm{merge}[/math].

Для первого блока содержательной является лишь ветка, начинающаяся с [math]C_j^S \longrightarrow \mathrm{merge} \longrightarrow \mathtt{ind's\#1}[/math], что не противоречит представленной схеме.

Пример

Первый блок

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

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

[math]\mathtt{merged}[/math] аналогичен сортированному, т.к. предыдущих ключей нет.

Ключи сортированного блока					[math]\xi[/math]
2	4	5	1	3	4	1	5	2	3

Пропускаем их через [math]\mathrm{LIS}[/math]:

[math]B_1[/math]	[math]B_2[/math]	[math]B_3[/math]	[math]\pi[/math]
4			4
1			1
1	5		5
1	2		2
1	2	3	3

Результат работы

[math]B: \{1, 2, 3\}[/math]

[math]\mathtt{merged}: \{3, 4, 8, 9, 10\}[/math]

Второй блок

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

Второй блок 1 2 12 6 5 1 2 3 4 5

Cортированный 1 2 5 6 12 1 2 5 4 3

[math]\mathtt{merged}[/math] 1 2 3 4 5 6 8 12

[math]\mathtt{ind's\#0}[/math] — индексы текущих 3 4 7

[math]\mathtt{ind's\#1}[/math] — индексы новых 1 2 5 6 8

Ключи сортированного блока
1	2	5	4	3

[math]\xi[/math]
1	2	5	4	3

Восстанавливаем порядок новых из [math]\mathtt{ind's\#1}[/math] и [math]\xi[/math]:

новые ключи
1	2	8	6	5

Обновление старых ключей:

3			3
3	4		4
3	4	7	7

[math]\mathrm{LIS}[/math] новых:

1	4	7		1
1	2	7		2
1	2	7	8	8
1	2	6	8	6
1	2	5	8	5

Результат работы

[math]B: \{1, 2, 5, 8\}[/math]

[math]\mathtt{merged}: \{1,2,3,4,5,6,8,12\}[/math]

Третий блок

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

Первый блок 7 11 1 2

Cортированный 7 11 1 2

[math]\mathtt{merged}[/math] 1 2 5 7 11 12

[math]\mathtt{ind's\#0}[/math] — индексы текущих 1 2 3 6

[math]\mathtt{ind's\#1}[/math] — индексы новых 4 5

Ключи сортированного блока
1	2

[math]\xi[/math]
1	2

Восстанавливаем порядок новых из [math]\mathtt{ind's\#1}[/math] и [math]\xi[/math]:

новые ключи
4	5

Обновление старых ключей:

1	4	7		1
1	2	7		2
1	2	3		3
1	2	3	6	6

[math]LIS[/math] новых:

1	2	3	4		4
1	2	3	4	5	5

Результат работы

[math]B: \{1, 2, 3, 4, 5\}[/math]

[math]\mathtt{merged}: \{1,2,5,7,11,12\}[/math]

Восстановление НВП

[math]\mathtt{predecessor}[/math]
1	2	3	4	5	6	7	8	9	10	11	12
	1		3	2	2	5	4		3	7	8

Начинаем восстановление с [math]\mathtt{merged}[5] = 11[/math]:

обратный порядок

11

7

5

2

1

НВП

1

2

5

7

11

См. также

• Дерево ван Эмде Боаса
• Задача о наибольшей возрастающей подпоследовательности
• Задача о наибольшей общей подпоследовательности
• Наибольшая общая возрастающая подпоследовательность
• Задача о наибольшей общей палиндромной подпоследовательности

Источники информации

• Computing a Longest Increasing Subsequence of Length k in Time O(n log log k) (07.01.2017)