| Задача: |
| Дана перестановка [math]\pi[/math] множества [math]~\{1, 2,~\dots,~n\}[/math]. Требуется найти НВП [math]\pi[/math] за [math]O(n\operatorname{log}\operatorname{log}k)[/math], где [math]k[/math] — длина НВП. |
Алгоритм за O(n log log n)
Нахождение длины НВП
Основная идея
Пусть [math]\{\pi_1,\pi_2,~\dots,~\pi_n\}[/math] — входная перестановка.
Будем последовательно обрабатывать элементы в порядке [math]\pi_1, \pi_2,~\dots,~\pi_n\colon[/math]
Для каждой длины [math]l = 1, 2,~\dots,~n[/math] предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины [math]l[/math] и запишем его в массив [math]B_l[/math]. Будем называть его наилучшим элементом для длины [math]l[/math].
- Если [math]\pi_i[/math] больше каждого элемента [math]B[/math], вычисленного для подпоследовательности [math]\pi_1, \pi_2,~\dots~,\pi_{i-1}[/math], тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец [math]B[/math].
- Иначе [math]\pi_i[/math] будет наилучшим элементом для уже существующей длины и сможет улучшить только один элемент в [math]B[/math], тогда мы находим наименьшее [math]k\colon B_k \gt \pi_i[/math] и заменяем [math]B_k[/math] элементом [math]\pi_i[/math].
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции [math]\mathrm{insert}, \mathrm{next}, \mathrm{delete}[/math], соответственно целесообразно использовать приоритетную очередь, реализованную через Дерево ван Эмде Боаса. Так как данная структура данных производит описанные операции за [math]O(\operatorname{log} k)[/math], где k — количество бит чисел, которые позволяет хранить дерево, то полученный алгоритм работает за [math]O(n\operatorname{log}\operatorname{log} n)[/math], потому что все элементы последовательности не превосходят n.
Пример
Типы операций
- Добавление элемента, который больше всех предыдущих:
- Замещение элемента более подходящим, т.е. добавление немаксимального элемента:
[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]
|
| [math]9[/math] |
[math]3[/math] |
[math]10[/math] |
[math]4[/math] |
[math]8[/math] |
[math]1[/math] |
[math]2[/math] |
[math]12[/math] |
[math]6[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math]
|
Состояние очереди при каждом добавлении
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]B_4[/math] |
[math]B_5[/math] |
[math]~\pi_i~[/math]
|
| [math]9[/math] |
|
|
|
|
[math]9[/math]
|
| [math]3[/math] |
|
|
|
|
[math]3[/math]
|
| [math]3[/math] |
[math]10[/math] |
|
|
|
[math]10[/math]
|
| [math]3[/math] |
[math]4[/math] |
|
|
|
[math]4[/math]
|
| [math]3[/math] |
[math]4[/math] |
[math]8[/math] |
|
|
[math]8[/math]
|
| [math]1[/math] |
[math]4[/math] |
[math]8[/math] |
|
|
[math]1[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]8[/math] |
|
|
[math]2[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]8[/math] |
[math]12[/math] |
|
[math]12[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]6[/math] |
[math]12[/math] |
|
[math]6[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]12[/math] |
|
[math]5[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
|
[math]7[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math] |
[math]11[/math]
|
Псевдокод
int LIS([math]\pi[/math][n])
PriorityQueue B // рабочая приоритетная очередь
int k = 0 // длина НВП
for i = 1 to n
x = [math]\pi[/math][i]
// в любом случае добавляем в очередь очередной элемент
// устаревшие будем удалять
B.insert(x)
if [math]\exists[/math] B.next(x)
// добавленный элемент — не максимальный
// удаляем следующее за x значение
B.delete(B.next(x))
else
// добавленный элемент — максимальный
// предыдущие значения не трогаем, очередь увеличилась
k = k + 1
return k
Расширение алгоритма до нахождения НВП
Основная идея
Будем запоминать пары: для каждого элемента записываем его "предшественника".
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди [math]B[/math], мы можем восстановить НВП.
Общий вид алгоритма
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]B_4[/math] |
[math]B_5[/math] |
[math]~\pi_i~[/math]
|
| [math]9[/math] |
|
|
|
|
[math]9[/math]
|
| [math]3[/math] |
|
|
|
|
[math]3[/math]
|
| [math]3[/math] |
[math]10[/math] |
|
|
|
[math]10[/math]
|
| [math]3[/math] |
[math]4[/math] |
|
|
|
[math]4[/math]
|
| [math]3[/math] |
[math]4[/math] |
[math]8[/math] |
|
|
[math]8[/math]
|
| [math]1[/math] |
[math]4[/math] |
[math]8[/math] |
|
|
[math]1[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]8[/math] |
|
|
[math]2[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]8[/math] |
[math]12[/math] |
|
[math]12[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]6[/math] |
[math]12[/math] |
|
[math]6[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]12[/math] |
|
[math]5[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
|
[math]7[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math] |
[math]11[/math]
|
| predecessor
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]6[/math] |
[math]7[/math] |
[math]8[/math] |
[math]9[/math] |
[math]10[/math] |
[math]11[/math] |
[math]12[/math]
|
| |
[math]1[/math] |
|
[math]3[/math] |
[math]2[/math] |
[math]2[/math] |
[math]5[/math] |
[math]4[/math] |
|
[math]3[/math] |
[math]7[/math] |
[math]8[/math]
|
Псевдокод
int[] LIS([math]\pi[/math][n])
PriorityQueue B
int k = 0
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
// по цепочке от последнего элемента
// восстанавливаем НВП
int result[k]
int cur = B.max
for i = k - 1 downto 0
result[i] = cur
cur = predecessor[cur]
return result
Оптимизация до O(n log log k)
Основная идея
Чтобы Дерево ван Эмде Боаса выполняло операции за [math]O(\operatorname{log}\operatorname{log}k)[/math], необходимо алфавит обрабатываемых значений уменьшить до [math]O(k)[/math].
Предположим, мы знаем такое приближение числа [math]k[/math] числом [math]m: m \geqslant k[/math]. Мы обсудим, как найти такое [math]m[/math] позже.
Во время обработки ключей элементов описанный выше алгоритм [math]\mathrm{LIS}[/math] работает только с очередью [math]B[/math] и не зависит от предыдущих элементов последовательности, которые не находятся в очереди. Поэтому, если мы разобьем всю последовательность на блоки из [math]m[/math] элементов (последний блок может быть меньше), и нам удастся обрабатывать каждый как перестановку из [math]m[/math] элементов, сохраняя очередь [math]B[/math] для вычисленных ранее блоков, то мы получим асимптотическое время [math]O(n \operatorname{log} \operatorname{log} (k + m))[/math], а так как [math]m \geqslant k[/math], то [math]O(n \operatorname{log} \operatorname{log} m)[/math]. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться [math]k[/math] значений в очереди, которые дополняются [math]m[/math] значениями очередного блока — получаем верхнее ограничение в [math]k + m[/math] обрабатываемых возможных значений.)
Деление на блоки
Последовательность [math]S[/math] делится на блоки [math]C_j,~j=1,~\dots,~\lceil\frac{n}{m}\rceil[/math]:
[math]C_j=(\pi_{(j-1)m+1},\pi_{(j-1)m+2},~\dots~,\pi_{(j-1)m+m)})[/math]
Обозначим за [math]C_j^s[/math] отсортированный блок [math]C_j[/math]. Отсортированные и неотсортированные блоки будем хранить в памяти.
Цифровая сортировка каждого блока отдельно будет давать нам время работы [math]O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)[/math]. Дополним каждый элемент [math]\pi[/math] номером блока, в котором он находится и смещением в этом блоке. Теперь, рассматривая номер блока как старший разряд, элемент как младший разряд (по смещению внутри блока не сортируем), можно сортировать цифровой сортировкой за линейное время [math]O(n)[/math], потому что значения элементов и номера блоков не превосходят [math]n[/math].
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки [math]\xi[/math], элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент [math]\pi[/math] находится в исходной перестановке в блоке [math]C_j[/math] на позиции [math]i[/math], то в блоке [math]C_j^s[/math] он на позиции [math]\xi_i[/math].
Пример
Предположим, что [math]m=5[/math]. Исходно получаем:
| Блок |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]3[/math] |
[math]3[/math]
|
| [math]\pi[/math] |
[math]9[/math] |
[math]3[/math] |
[math]10[/math] |
[math]4[/math] |
[math]8[/math] |
[math]1[/math] |
[math]2[/math] |
[math]12[/math] |
[math]6[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math]
|
| Смещение |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]1[/math] |
[math]2[/math]
|
После сортировки:
| Блок |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]1[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]2[/math] |
[math]3[/math] |
[math]3[/math]
|
| [math]\pi[/math] |
[math]3[/math] |
[math]4[/math] |
[math]8[/math] |
[math]9[/math] |
[math]10[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]6[/math] |
[math]12[/math] |
[math]7[/math] |
[math]11[/math]
|
| Смещение |
[math]2[/math] |
[math]4[/math] |
[math]5[/math] |
[math]1[/math] |
[math]3[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]4[/math] |
[math]3[/math] |
[math]1[/math] |
[math]2[/math]
|
Обратные перестановки ([math]\xi[/math]):
| [math]1[/math] |
[math]2[/math] |
[math]3[/math]
|
| [math]4[/math] |
[math]1[/math] |
[math]5[/math] |
[math]2[/math] |
[math]3[/math]
|
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]4[/math] |
[math]3[/math]
|
[math]1[/math] |
[math]2[/math]
|
Обработка блока
Обрабатывая блок, каждому элементу [math]x[/math] внутри этого блока взаимно однозначно сопоставим ключ [math]y = \mathtt{key}(x);~x=\mathtt{elt}(y)[/math] так, чтобы их значения находились в промежутке [math]\{1,2,\dots,2m\}[/math]. Очередь [math]B[/math] будет работать непосредственно с ключами элементов.
Работая с блоком [math]C_j[/math], будем сливать элементы, ключи которых находятся в очереди [math]B[/math], с [math]C_j^s[/math] в список [math]\mathtt{merged}[/math]. Поскольку мы предположили, что [math]m\geqslant k[/math], то количество ключей в [math]B[/math] не больше [math]m[/math], тогда длина [math]\mathtt{merged}[/math] не больше [math]2m[/math], что позволяет однозначно определить ключи на множестве [math]\{1,2,\dots,2m\}[/math]. Как было замечено ранее, элементы, чьи ключи находятся в [math]B[/math], располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию слияния за [math]O(m)[/math].
В итоге, получим отсортированный список [math]\mathtt{merged}[/math]. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливы утверждения, что [math]\mathtt{elt}(x)=\mathtt{merged}[x][/math] и [math](\pi_{i}\lt \pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})\lt \mathtt{key}(\pi_{k}))[/math], где [math]\pi_{i},\pi_{k}\in \mathtt{merged}[/math], поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
Находим последовательность ключей, соответствующую элементам блока [math]C_j^s[/math]. Действуя на эту последовательность перестановкой [math]\xi_j[/math], получаем последовательность ключей в порядке исходного блока.
Оставшиеся ключи, которые входят в [math]\mathtt{merged}[/math], но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди [math]B[/math]. Обновляем очередь [math]B[/math] этими ключами.
Затем запускаем алгоритм [math]\mathrm{LIS}[/math], для ключей элементов [math]C_j[/math] в порядке исходной последовательности.
В итоге, обработка блока делится на следующие этапы:
- Достаем из очереди [math]B[/math] ключи [math]x[/math], конвертируем их в элементы [math]\mathtt{elt}(x)[/math] и кладём в список [math]\mathtt{elems}[/math].
- Сливаем элементы в [math]\mathtt{elems}[/math] со следующим отсортированным блоком [math]C_j^s[/math] в список [math]\mathtt{merged}[/math], генерируя два вспомогательных массива [math]\mathtt{ind_0}[/math] и [math]\mathtt{ind_1}[/math], хранящих индексы элементов списков [math]C_j^s[/math] и [math]\mathtt{elems}[/math] соответственно в списке [math]\mathtt{merged}[/math].
- Действуя на последовательность ключей в списке [math]\mathtt{ind_0}[/math] перестановкой [math]\xi_j[/math] получим ключи в порядке исходной последовательности.
- Вставляем в [math]B[/math] новые ключи элементов списка [math]\mathtt{elems}[/math] (элементы [math]\mathtt{ind_1}[/math]).
- Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма [math]\mathrm{LIS}[/math]. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами [math]\mathtt{elt}(x)[/math].
Пример
Первый блок
Так как очередь [math]B[/math] в начале пуста, то [math]\mathtt{merged}=C_1^s[/math]. Присвоим ключи элементам в списке [math]\mathtt{merged}[/math] как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя перестановкой смещений [math]\xi_1[/math] на последовательность ключей в отсортированном блоке.
| |
| Сортированный
|
| [math]\pi[/math] |
[math]3[/math] |
[math]4[/math] |
[math]8[/math] |
[math]9[/math] |
[math]10[/math]
|
| [math]key[/math] |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math]
|
|
|
| Первый блок
|
| [math]\pi[/math] |
[math]9[/math] |
[math]3[/math] |
[math]10[/math] |
[math]4[/math] |
[math]8[/math]
|
| [math]key[/math] |
[math]4[/math] |
[math]1[/math] |
[math]5[/math] |
[math]2[/math] |
[math]3[/math]
|
| [math]\xi_1[/math] |
[math]4[/math] |
[math]1[/math] |
[math]5[/math] |
[math]2[/math] |
[math]3[/math]
|
|
Обработка блока с помощью алгоритма [math]\mathrm{LIS}[/math].
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]key[/math] |
[math]\pi[/math]
|
| [math]4[/math] |
|
|
[math]4[/math] |
[math]9[/math]
|
| [math]1[/math] |
|
|
[math]1[/math] |
[math]3[/math]
|
| [math]1[/math] |
[math]5[/math] |
|
[math]5[/math] |
[math]10[/math]
|
| [math]1[/math] |
[math]2[/math] |
|
[math]2[/math] |
[math]4[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]3[/math] |
[math]8[/math]
|
В результате получаем
[math]B: \{1, 2, 3\}[/math]
[math]\mathtt{merged}: \{3,4,8,9,10\}[/math]
Второй блок
Восстанавливаем элементы [math]B: \{1, 2, 3\}[/math] из [math]\mathtt{merged}: \{3, 4, 8, 9, 10\}[/math]: [math]\{3, 4, 8\}[/math].
Сливаем [math]C_2^s[/math] и восстановленные элементы из [math]B[/math] в [math]\mathtt{merged}[/math] и присваиваем элементам ключи как индексы элементов в полученном списке:
| |
| [math]B[/math]
|
| [math]3[/math] |
[math]4[/math] |
[math]8[/math]
|
|
|
| [math]C_2^s[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]6[/math] |
[math]12[/math]
|
|
| |
| [math]\mathtt{merged}[/math]
|
| [math]\pi[/math] |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]6[/math] |
[math]8[/math] |
[math]12[/math]
|
| [math]key[/math] |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]6[/math] |
[math]7[/math] |
[math]8[/math]
|
|
|
| [math]\mathtt{ind_1}[/math]
|
| [math]3[/math] |
[math]4[/math] |
[math]7[/math]
|
|
|
| [math]\mathtt{ind_0}[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]6[/math] |
[math]8[/math]
|
|
Получаем ключи элементов в [math]C_2^s[/math] и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой [math]\xi_2[/math]:
| |
| Сортированный
|
| [math]\pi[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]6[/math] |
[math]12[/math]
|
| [math]key[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]6[/math] |
[math]8[/math]
|
|
|
| Второй блок
|
| [math]\pi[/math] |
[math]1[/math] |
[math]2[/math] |
[math]12[/math] |
[math]6[/math] |
[math]5[/math]
|
| [math]key[/math] |
[math]1[/math] |
[math]2[/math] |
[math]8[/math] |
[math]6[/math] |
[math]5[/math]
|
| [math]\xi_2[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]4[/math] |
[math]3[/math]
|
|
Обновляем ключи в очереди:
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]key[/math]
|
| [math]3[/math] |
|
|
[math]3[/math]
|
| [math]3[/math] |
[math]4[/math] |
|
[math]4[/math]
|
| [math]3[/math] |
[math]4[/math] |
[math]7[/math] |
[math]7[/math]
|
запускаем [math]\mathrm{LIS}[/math] для блока:
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]B_4[/math] |
[math]key[/math] |
[math]\pi[/math]
|
| [math]1[/math] |
[math]4[/math] |
[math]7[/math] |
|
[math]1[/math] |
[math]1[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]7[/math] |
|
[math]2[/math] |
[math]2[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]7[/math] |
[math]8[/math] |
[math]8[/math] |
[math]12[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]6[/math] |
[math]8[/math] |
[math]6[/math] |
[math]6[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]8[/math] |
[math]5[/math] |
[math]5[/math]
|
В результате получаем:
[math]B: \{1, 2, 5, 8\}[/math]
[math]\mathtt{merged}: \{1,2,3,4,5,6,8,12\}[/math]
Третий блок
Восстанавливаем элементы [math]B: \{1, 2, 5, 8\}[/math] из [math]\mathtt{merged}: \{1, 2, 3, 4, 5, 6, 8, 12\}[/math]: [math]\{1, 2, 5, 12\}[/math].
Сливаем [math]C_3^s[/math] и восстановленные элементы из [math]B[/math] и присваиваем ключи элементам:
| |
| [math]B[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]12[/math]
|
|
|
| [math]C_3^s[/math]
|
| [math]7[/math] |
[math]11[/math]
|
|
| |
| [math]\mathtt{merged}[/math]
|
| [math]\pi[/math] |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math] |
[math]12[/math]
|
| [math]key[/math] |
[math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]6[/math]
|
|
|
| [math]\mathtt{ind_1}[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]6[/math]
|
|
|
| [math]\mathtt{ind_0}[/math]
|
| [math]4[/math] |
[math]5[/math]
|
|
Получаем ключи элементов в [math]C_3^s[/math] и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой [math]\xi_3[/math]:
| |
| |
| Третий блок
|
| [math]\pi[/math] |
[math]7[/math] |
[math]11[/math]
|
| [math]key[/math] |
[math]4[/math] |
[math]5[/math]
|
|
|
| Cортированный
|
| [math]\pi[/math] |
[math]7[/math] |
[math]11[/math]
|
| [math]key[/math] |
[math]4[/math] |
[math]5[/math]
|
| [math]\xi_3[/math] |
[math]1[/math] |
[math]2[/math]
|
|
Обновление старых ключей:
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]B_4[/math] |
[math]key[/math]
|
| [math]1[/math] |
|
|
|
[math]1[/math]
|
| [math]1[/math] |
[math]2[/math] |
|
|
[math]2[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
|
[math]3[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]6[/math] |
[math]6[/math]
|
запускаем [math]\mathrm{LIS}[/math] для блока:
| [math]B_1[/math] |
[math]B_2[/math] |
[math]B_3[/math] |
[math]B_4[/math] |
[math]B_5[/math] |
[math]key[/math] |
[math]\pi[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
|
[math]4[/math] |
[math]7[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]5[/math] |
[math]11[/math]
|
Результат завершения алгоритма:
[math]B: \{1, 2, 3, 4, 5\}[/math]
[math]\mathtt{merged}: \{1,2,5,7,11,12\}[/math]
Получаем, что длина НВП — [math]5[/math], и НВП оканчивается на [math]\mathtt{merged}[5]=11[/math].
Восстановление НВП
| [math]\mathtt{predecessor}[/math]
|
| [math]1[/math] |
[math]2[/math] |
[math]3[/math] |
[math]4[/math] |
[math]5[/math] |
[math]6[/math] |
[math]7[/math] |
[math]8[/math] |
[math]9[/math] |
[math]10[/math] |
[math]11[/math] |
[math]12[/math]
|
| |
[math]1[/math] |
|
[math]3[/math] |
[math]2[/math] |
[math]2[/math] |
[math]5[/math] |
[math]4[/math] |
|
[math]3[/math] |
[math]7[/math] |
[math]8[/math]
|
Начинаем восстановление с [math]\mathtt{merged}[5] = 11[/math]:
| обратный порядок |
[math]11[/math] |
[math]7[/math] |
[math]5[/math] |
[math]2[/math] |
[math]1[/math]
|
| НВП |
[math]1[/math] |
[math]2[/math] |
[math]5[/math] |
[math]7[/math] |
[math]11[/math]
|
Нахождение размера блоков
Рассмотрим последовательность [math]\{m_0,~m_1,~m_2,~\dots\}[/math], где [math] m_{i+1} = m_i ^{\operatorname{log}m_i} = 2^{\operatorname{log}^2m_i}[/math], [math]m_0[/math] — некоторое значение, меньшее [math]k[/math].
Будем последовательно для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди [math]B[/math] становится больше [math]m_i[/math], то условие [math]m \geqslant k[/math] перестает выполняться, тогда останавливаем алгоритм и переходим к следующему значению [math]m_{i+1}[/math].
Для каждого [math]m_i[/math] размер списка [math]\mathtt{merged}[/math] не больше [math]2m_i[/math], а количество блоков всего [math]\lceil n/m_i \rceil[/math]. То общее количество присваиваний новых ключей элементам последовательности, также как и количество операций слияния списков, не больше [math]2cm_i\cdot\dfrac{n}{m_i}=O(n)[/math], где c — некоторая константа. Каждая операция с приоритетной очередью требует [math]O(\log \log m_i)[/math] времени, так как элементы в [math]B[/math] не больше [math]2m_i[/math].
Таким образом, время работы запущенного алгоритма для каждого [math]m_i[/math] — [math]O(n \log \log {m_i})[/math]. Когда найдётся первое [math]m_j:m_j\geqslant k[/math], то алгоритм успешно завершится.
[math]\operatorname{log}\operatorname{log}m_{i+1} = \operatorname{log}\operatorname{log}2^{\operatorname{log}^2m_i} = \operatorname{log}\operatorname{log}^2m_i = 2\operatorname{log}\operatorname{log}m_i[/math].
[math]\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i[/math]
Общее время работы алгоритма для всех обработанных значений [math]m_i[/math] — [math]O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \log m_i) = O(n\operatorname{log}\operatorname{log}m_i)[/math]. Заметим, что [math]m_i \lt k^{\operatorname{log}k}[/math], так как в противном случае [math]m_{i-1} \gt k[/math], что противоречит тому, что [math]m_i[/math] — первый из тех, которые больше [math]k[/math]. Следовательно, [math]\operatorname{log}\operatorname{log}m_i \lt 2\operatorname{log}\operatorname{log}k \[/math].
Получаем время работы [math]O(n\operatorname{log}\operatorname{log}k)[/math].
См. также
Источники информации
|
