Быстрый поиск наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 156: Строка 156:
 
</code>
 
</code>
 
== Оптимизация до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==
 
== Оптимизация до <tex>O(n\operatorname{log}\operatorname{log}k)</tex> ==
 +
=== Основная идея ===
 +
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
 +
 +
Предположим, мы знаем такое {{Acronym|приближение <tex>k</tex>|далее рассмотрим нахождение и насколько оно точное}} <tex>m: m \ge k</tex>. Если мы разобьем всю последовательность на блоки из {{ Acronym|<tex>m</tex> элементов|последний блок может быть меньше}} и нам удастся обрабатывать каждый как перестановку из <tex>m</tex> элементов, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а т.к. <tex>m \ge k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока - получаем врехнее ограничение в <tex>k + m</tex> обрабатываемых возможных значений.)
 +
 +
Рассмотрим последовательность <tex>m_0, m_0 ^{\operatorname{log}m_0}</tex>
 +
 +
====  ====
 +
 +
 
=== Деление на блоки ===
 
=== Деление на блоки ===

Версия 16:20, 6 января 2017

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


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


Task.jpg

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

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

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

Пусть [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]insert, next, delete[/math], соответственно целесообразно использовать приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Таким образом получаем [math]O(\operatorname{log}\operatorname{log} n)[/math] амортизированного времени на одну операцию.

Пример

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

Operation1.jpg

Operation2 1.jpg [math]\longrightarrow[/math] Operation2 2.jpg

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

[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(n\operatorname{log}\operatorname{log}k)[/math]

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

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

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

Рассмотрим последовательность [math]m_0, m_0 ^{\operatorname{log}m_0}[/math]

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