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

2017-01-05T13:04:49Z

95.140.92.75: Новая страница.

{{В разработке}}

{{Задача
|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> - длина НВП.
}}

== Алгоритм <tex>O(n\operatorname{log}\operatorname{log}n)</tex> ==
=== Нахождение длины НВП ===
==== Основная идея ====
Пусть <tex>\pi(n)</tex> - входная перестановка.

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

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

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

* Если <tex>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <tex>B</tex>
* Иначе <tex>\pi(i)</tex> становится лучшим элементом для такой длины <tex>l</tex>, что: {{Acronym | <tex>B[l]</tex> | предыдущее значение}}<tex> = \min \{ B[j] > \pi(i),~j < i \}</tex>

Следует отметить, что полученный массив также образует возрастающую последовательность, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени.
==== Пример ====
Типы операций:

Последовательность:
{| 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>
|-align="center"
| 9 || 2 || 1 || 3 || 7 || 5 || 6 || 8 || 4
|}
Состояние очереди при каждом добавлении:
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| style="background:#FFCC00"| 9 || || || || || style="background:#9886ff"|9
|-align="center"
| style="background:#FFCC00"| 2 || || || || || style="background:#9886ff"|2
|-align="center"
| style="background:#FFCC00"| 1 || || || || || style="background:#9886ff"|1
|-align="center"
| 1 || style="background:#FFCC00"| 3 || || || || style="background:#9886ff"|3
|-align="center"
| 1 || 3 || style="background:#FFCC00"| 7 || || || style="background:#9886ff"|7
|-align="center"
| 1 || 3 || style="background:#FFCC00"| 5 || || || style="background:#9886ff"|5
|-align="center"
| 1 || 3 || 5 || style="background:#FFCC00"| 6 || || style="background:#9886ff"|6
|-align="center"
| 1 || 3 || 5 || 6 || style="background:#FFCC00"| 8 || style="background:#9886ff"|8
|-align="center"
| 1 || 3 || style="background:#FFCC00"| 4 || 6 || 8 || style="background:#9886ff"|4

|}

==== Псевдокод ====
<code>
'''function''' LIS(<tex>\pi</tex>[])
B = priorityQueue()
k = 0
n = <tex>\pi</tex>.size
'''for''' i = 1..n:
x = <tex>\pi</tex>[i]
B.insert(x) // в любом случае добавляем в очередь
'''if''' B.next(x) '''exists''' '''then'''
B.delete(B.next(x)) // удаляем предыдущее значение - заменяем {{Acronym | следующий | минимальный из бОльших}}
'''else'''
k = k + 1 // добавляем максимальный - уже добавлен, ничего не удаляем
'''return''' k</code>
=== Расширение алгоритма на нахождение НВП ===
==== Основная идея ====
Будем запоминать пары: для каждого элемента записываем его "предшественника".

Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко восстановить все НВП.
==== Псевдокод ====
<code>
'''function''' LIS(<tex>\pi</tex>[])
B = priorityQueue()
k = 0
n = <tex>\pi</tex>.size
<color = 'red'>predecessors = [n]</color>
'''for''' i = 1 to n
x = <tex>\pi</tex>[i]
B.insert(x)
predecessor[x] = B.prev(x)
'''if''' B.next(x) '''exists''' '''then'''
B.delete(B.next(x))
'''else'''
k = k + 1
result = []
cur = B.max()
result += [cur]
'''while''' predecessor[cur] '''exists'''
result += [predecessor[cur]]
cur = predecessor[cur]
'''return''' result
</code>
== Переименование до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==

Викиконспекты - Вклад участника [ru]

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