47
правок
Изменения
м
{{В разработке}}
Снята с разработки
{{Задача
|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> — длина НВП.
==== Псевдокод ====
<code>
'''vector<int>[]''' LIS(<tex>\pi</tex>[n])
'''PriorityQueue''' B
'''int''' k = 0
Разделим исходную перестановку <tex>\pi</tex> на блоки <tex>C_j = \{\pi_{(j-1)m + 1},~\pi_{(j-1)m + 2},~\dots, ~\pi_{(j-1)m + m}\}</tex>.
Получим сортированные варианты этих блоков <tex>C_j^S</tex>. Лобовая [[цифровая сортировка]] дает нам время работы <tex>O\left(\dfrac{n}{m}n\right) = O \left(\dfrac{n^2}{m} \right)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>.
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Классические задачи динамического программирования]]
