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

Эта статья находится в разработке!

Задача:

Дана перестановка . Требуется найти НВП за , где — длина НВП.

Содержание

1 Алгоритм [math]O(n\operatorname{log}\operatorname{log}n)[/math]
- 1.1 Нахождение длины НВП
- 1.2 Расширение алгоритма до нахождения НВП
2 Оптимизация до [math]O(n\operatorname{log}\operatorname{log}k)[/math]

Алгоритм

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

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

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

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

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

Будем последовательно обрабатывать элементы :

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

Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции [math]insert, next, delete[/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(vector<int> [math]\pi[/math])
       PriorityQueue B // рабочая приоритетная очередь
       int k = 0       // длина НВП
       int n = [math]\pi[/math].size
       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

Псевдокод


   vector<int> LIS(vector<int> [math]\pi[/math])
       PriorityQueue B
       int k = 0
       int n = [math]\pi[/math].size
       vector<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
       // по цепочке от последнего элемента 
       // восстанавливаем НВП
       vector<int> result
       int cur = B.max()
       result += [cur]
       while [math]\exists[/math] predecessor[cur] 
           result += [predecessor[cur]]
           cur = predecessor[cur]
       return result

Оптимизация до

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

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

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

Описанный здесь алгоритм подбора [math]m_i[/math] и получение асимптотической оценки в других подразделах рассмотрено не будет, т.к. в основном это доказательство, сложного для понимания/реализации ничего нет

Рассмотрим последовательность [math]\{m_0,~m_1,~m_2,~\dots\}[/math], где , [math]m_0[/math] - некоторое значение, меньшее [math]k[/math].

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

Общее время работы - . Заметим, что , т.к. в противном случае [math]m_{i-1} \gt k[/math], что противоречит тому, что [math]m_i[/math] - первый из тех, что больше [math]k[/math]. Следовательно, .

Получаем время работы

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

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

Разделим исходную перестановку [math]\pi[/math] на блоки .

Получим сортированные варианты этих блоков [math]C_j^S[/math]. При лобовой цифровой сортировке мы получим [math]O(\frac{n}{m}n)[/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]merged[/math].

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

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

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

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

Для первого блока содержательным является лишь ветка, начинающаяся с , что не противоречит представленной схеме.

Пример

Первый блок

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

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

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

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

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

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

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

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

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

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

Второй блок

Восстанавливаем элементы [math]B: \{1, 2, 3\}[/math] из [math]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]merged[/math]
1	2	3	4	5	6	8	12

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

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

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

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

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

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

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

3			3
3	4		4
3	4	7	7

[math]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]B: \{1, 2, 5, 8\}[/math] из : [math]\{1, 2, 5, 12\}[/math]

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

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

[math]merged[/math]
1	2	5	7	11	12

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

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

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

[math]\xi[/math]
1	2

Восстанавливаем порядок новых из [math]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]merged: \{1,2,5,7,11,12\}[/math]

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

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

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

обратный порядок
11	7	5	2	1

НВП
1	2	5	7	11

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

Содержание

Алгоритм

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

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

Пример

Псевдокод

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

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

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

Псевдокод

Оптимизация до

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

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

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

Пример

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

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

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

Пример

Первый блок

Второй блок

Третий блок

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты

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

Содержание

Алгоритм [math]O(n\operatorname{log}\operatorname{log}n)[/math]

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

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

Пример

Псевдокод

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

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

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

Псевдокод

Оптимизация до [math]O(n\operatorname{log}\operatorname{log}k)[/math]

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

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

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

Пример

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

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

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

Пример

Первый блок

Второй блок

Третий блок

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

Навигация

Поиск

Алгоритм

Оптимизация до