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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!


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


Алгоритм [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]l[/math], что: [math]B[l][/math] [math] = \min \{ B[j] \gt \pi(i),~j \lt i \}[/math]

Следует отметить, что полученный массив также образует возрастающую последовательность, соответственно целесообразно использовать приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Таким образом получаем [math]O(\operatorname{log}\operatorname{log} n)[/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]
9 2 1 3 7 5 6 8 4

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

[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
2 2
1 1
1 3 3
1 3 7 7
1 3 5 5
1 3 5 6 6
1 3 5 6 8 8
1 3 4 6 8 4

Псевдокод

   function LIS([math]\pi[/math][])
       B = PriorityQueue()
       k = 0
       n = [math]\pi[/math].size
       for i = 1..n:
           x = [math]\pi[/math][i]
           B.insert(x)             // в любом случае добавляем в очередь
           if B.next(x) exists then
               B.delete(B.next(x)) // удаляем предыдущее значение - заменяем  следующий  
           else
               k = k + 1           // добавляем максимальный - уже добавлен, ничего не удаляем
       return k

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

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

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

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

Псевдокод

   function LIS([math]\pi[/math][])
       B = priorityQueue()
       k = 0
       n = [math]\pi[/math].size
       <color = 'red'>predecessors = [n]</color>
       for i = 1 to n
           x = [math]\pi[/math][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

Переименование до [math]O(n\operatorname{log}\operatorname{log}k)[/math]