Изменения

Перейти к: навигация, поиск

Участник:Artem.ustinov/НВП

97 байт добавлено, 21:42, 19 января 2018
→‎Деление на блоки
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для подпоследовательности <tex>\pi_1, \pi_2,~\dots~,\pi_{i-1}</tex>, тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец <tex>B</tex>.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длиныи сможет улучшить только один элемент в <tex>B</tex>, тогда мы находим наименьшее <tex>k\colon B_k > \pi_i</tex> и заменяем <tex>B_k</tex> элементом <tex>\pi_i</tex>.
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <tex>\mathrm{insert}, \mathrm{next}, \mathrm{delete}</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Так как данная структура данных производит описанные операции за <tex>O(\operatorname{log} k)</tex>, где k — количество бит чисел, которые позволяет хранить дерево, то полученный алгоритм работает за <tex>O(n\operatorname{log}\operatorname{log} n)</tex>, потому что все элементы последовательности не превосходят n.
 
==== Доказательство оптимальности ====
{{
Утверждение|statement=
Пусть <tex>S=\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка. В результате описанного алгоритма размер массива <tex>B</tex> равен длине НВП последовательности <tex>S</tex>
 
|proof=
Докажем, что перед обработкой и после обработки элемента последовательности алгоритмом сохраняется инвариант, что в массиве <tex>B</tex> хранятся наилучшие элементы для каждой возможной длины возрастающих подпоследовательностей обработанной последовательности.
* Пусть перед обработкой элемента <tex>\pi_i</tex> соблюдается описанное выражение инварианта.
* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для последовательности <tex>S_{i-1}=\{\pi_1,\pi_2,~\dots,~\pi_{i-1}\}</tex>, то он не может обновить любой из наилучших элементов, вычисленных ранее. С <tex>\pi_i</tex> можно составить возрастающую последовательность длины <tex>l+1</tex>, где <tex>l</tex> — длина НВП последовательности <tex>S_{i-1}</tex>, добавив <tex>\pi_i</tex> в конец этой НВП. Значит, <tex>\pi_i</tex> — наилучший элемент длины <tex>l+1</tex>. По предположению, размер <tex>B</tex> равен длине НВП последовательности <tex>S_{i-1}</tex>, потому что в <tex>B</tex> хранятся наилучшие элементы всех возможных длин возрастающих подпоследовательностей <tex>S_{i-1}</tex>. Тогда, добавив в конец очереди <tex>B</tex> элемент <tex>\pi_i</tex>, инвариант будет сохраняться.
* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины. Заметим, что <tex>\pi_i</tex> может обновить только один элемент. В обратном случае, если <tex>\exists l_1,l_2\colon l_2>l_1</tex>, для которых <tex>\pi_i</tex> может быть наилучшим элементом, то существует такая подпоследовательность длины <tex>l_2</tex>, в которой <tex>\pi_i</tex> является наибольшим элементом, но из этой последовательности можно составить подпоследовательность длины <tex>l_1</tex>, в которой наибольший элемент меньше <tex>\pi_i</tex>, что противоречит предположению. Таким образом, <tex>\pi_i</tex> может обновить только наименьшее <tex>k\colon B_k > \pi_i</tex>. Тогда, заменив <tex>B_k</tex> элементом <tex>\pi_i</tex>, инвариант также будет сохраняться.
* После завершения алгоритма, в очереди <tex>B</tex> будут храниться наилучшие элементы для всех возможных длин возрастающих подпоследовательностей последовательности <tex>S</tex>. Тогда размер <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.
}}
==== Пример ====
===== ''' Типы операций ====='''
* Добавление элемента, который больше всех предыдущих:
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
===== ''' Пример последовательности ====='''
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
|}
===== ''' Состояние очереди при каждом добавлении ====='''
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>9 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>9</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>3 </tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3</tex> || style="background:#FFCC00FFCFCF"| <tex>10 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>10</tex>
|-align="center"
| <tex>3</tex> || style="background:#FFCC00FFCFCF"| <tex>4 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3</tex> || <tex>4</tex> || style="background:#FFCC00FFCFCF"| <tex>8 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>8</tex>
|-align="center"
| style="background:#FFCC00FFCFCF"| <tex>1 </tex> || <tex>4</tex> || <tex>8</tex> || || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFCFCF"| <tex>2 </tex> || <tex>8</tex> || || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>8</tex> || style="background:#FFCC00FFCFCF"| <tex>12 </tex> || || style="background: #77A9F4CFCFFF"| <tex>12</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFCFCF"| <tex>6 </tex> || <tex>12</tex> || || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFCFCF"| <tex>5 </tex> || <tex>12</tex> || || style="background: #77A9F4CFCFFF"| <tex>5</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || style="background:#FFCC00FFCFCF"| <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || <tex>7</tex> || style="background:#FFCC00FFCFCF"| <tex>11 </tex> || style="background: #77A9F4CFCFFF"| <tex>11</tex>
|}
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем восстановить НВП.
==== Общий вид алгоритма ====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
|-align="center"
| <tex>9</tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>9</tex>
|-align="center"
| <tex>3</tex> || || || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3</tex> || <tex>10</tex> || || || || style="background: #77A9F4CFCFFF"| <tex>10</tex>
|-align="center"
| <tex>3</tex> || <tex>4</tex> || || || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3</tex> || <tex>4</tex> || <tex>8</tex> || || || style="background: #77A9F4CFCFFF"| <tex>8</tex>
|-align="center"
| style="background:#FFCC00FFDF90"| <tex>1 </tex> || <tex>4</tex> || <tex>8</tex> || || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| style="background:#FF7F00FFCFCF"| <tex>1 </tex> || style="background:#FFCC00FFDF90"| <tex>2 </tex> || <tex>8</tex> || || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFDF90"| <tex>2 </tex> || <tex>8</tex> || <tex>12</tex> || || style="background: #77A9F4CFCFFF"| <tex>12</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFDF90"| <tex>2 </tex> || <tex>6</tex> || <tex>12</tex> || || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|-align="center"
| <tex>1</tex> || style="background:#FF7F00FFCFCF"| <tex>2 </tex> || style="background:#FFCC00FFDF90"| <tex>5 </tex> || <tex>12</tex> || || style="background: #77A9F4CFCFFF"| <tex>5</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FF7F00FFCFCF"| <tex>5 </tex> || style="background:#FFCC00FFDF90"| <tex>7 </tex> || || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || style="background:#FF7F00FFCFCF"| <tex>7 </tex> || style="background:#FF7F00FFCFCF"| <tex>11 </tex> || style="background: #77A9F4CFCFFF"| <tex>11</tex>
|}
== Оптимизация до O(n log log k) ==
===Основная идея===
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
Предположим, мы знаем такое приближение числа <tex>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.
Чтобы достичь нужной оценкиВо время обработки ключей элементов описанный выше алгоритм <tex>\mathrm{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, которые не находятся в очереди. Поэтому, будем делить если мы разобьем всю последовательность на блоки длины из <tex>m</tex>, кроме последнего, который элементов (последний блок может быть меньше), и нам удастся обрабатывать каждый блок отдельнокак перестановку из <tex>m</tex> элементов, сохраняя очередь <tex>B</tex> для вычисленных ранее блоков, то мы получим асимптотическое время <tex>O(n \operatorname{log} \operatorname{log} (k + m))</tex>, а так как <tex>m \geqslant k</tex>, то <tex>O(n \operatorname{log} \operatorname{log} m)</tex>. (Мы будем обрабатывать блоки последовательно, т.е. с предыдущего блока у нас может остаться <tex>k</tex> значений в очереди, которые дополняются <tex>m</tex> значениями очередного блока — получаем верхнее ограничение в <tex>k + m</tex> обрабатываемых возможных значений.)
=== Деление на блоки===
Последовательность <tex>S</tex> делится на блоки <tex>C_j,~j=1,~\dots,~\lceil\frac{n}{m}\rceil</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>C_j</tex>. Отсортированные и неотсортированные блоки будем хранить в памяти.
[[Цифровая сортировка]] каждого блока отдельно будет давать нам время рваботы работы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Чтобы отсортировать их за линейное время, дополним Дополним каждый элемент номером его блока и получим пары <tex>\langle\lceil i/m\rceil,\pi_i\ranglepi</tex>номером блока, в котором он находится и смещением в этом блоке. Цифровая сортировка этих парТеперь, если принимать за рассматривая номер блока как старший разряд номер блока, а за элемент как младший значение элементаразряд (по смещению внутри блока не сортируем), будет работать можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>. Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки <tex>\xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент <tex>\pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на позиции <tex>i</tex>, то в блоке <tex>C_j^s</tex> он на позиции <tex>\xi_i</tex>. ====Пример====Предположим, что <tex>m=5</tex>. Исходно получаем: {| class="wikitable" style="text-align:center"| Блок ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#CFCFFF"|<tex>3</tex>||style="background:#CFCFFF"|<tex>3</tex>|-|<tex>\pi</tex>||style="background:#FFC9C9"|<tex>9</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>10</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>8</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>12</tex>||style="background:#B9FFB9"|<tex>6</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#CFCFFF"|<tex>7</tex>||style="background:#CFCFFF"|<tex>11</tex>|-|Смещение ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>2</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>3</tex>||style="background:#B9FFB9"|<tex>4</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#CFCFFF"|<tex>1</tex>||style="background:#CFCFFF"|<tex>2</tex>|} После сортировки:{| class="wikitable" style="text-align:center"|Блок ||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#CFCFFF"|<tex>3</tex>||style="background:#CFCFFF"|<tex>3</tex>|-|<tex>\pi</tex> ||style="background:#FFC9C9"|<tex>3</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>8</tex>||style="background:#FFC9C9"|<tex>9</tex>||style="background:#FFC9C9"|<tex>10</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>6</tex>||style="background:#B9FFB9"|<tex>12</tex>||style="background:#CFCFFF"|<tex>7</tex>||style="background:#CFCFFF"|<tex>11</tex>|-|Смещение ||style="background:#FFC9C9"|<tex>2</tex>||style="background:#FFC9C9"|<tex>4</tex>||style="background:#FFC9C9"|<tex>5</tex>||style="background:#FFC9C9"|<tex>1</tex>||style="background:#FFC9C9"|<tex>3</tex>||style="background:#B9FFB9"|<tex>1</tex>||style="background:#B9FFB9"|<tex>2</tex>||style="background:#B9FFB9"|<tex>5</tex>||style="background:#B9FFB9"|<tex>4</tex>||style="background:#B9FFB9"|<tex>3</tex>||style="background:#CFCFFF"|<tex>1</tex>||style="background:#CFCFFF"|<tex>2</tex>|} Обратные перестановки (<tex>\xi</tex>):{| class="wikitable" style="center" style="background:#FFCC80"! colspan="5"|<tex>1</tex> || colspan="5"|<tex>2</tex> || colspan="3"|<tex>3</tex>|-align="center" | style="background:#FFD0D0"|<tex>4</tex>||style="background:#FFD0D0"|<tex>1</tex>||style="background:#FFD0D0"|<tex>5</tex>||style="background:#FFD0D0"|<tex>2</tex>||style="background:#FFD0D0"|<tex>3</tex>| style="background:#D0FFD0"|<tex>1</tex>||style="background:#D0FFD0"|<tex>2</tex>||style="background:#D0FFD0"|<tex>5</tex>||style="background:#D0FFD0"|<tex>4</tex>||style="background:#D0FFD0"|<tex>3</tex> | style="background:#D0D0FF"|<tex>1</tex>||style="background:#D0D0FF"|<tex>2</tex>|}
=== Обработка блока ===
Обрабатывая блокиблок, будем работать не со значениями элементовкаждому элементу <tex>x</tex> внутри этого блока взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex> так, а с ключамичтобы их значения находились в промежутке <tex>\{1, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн2, то есть мы не перейдём к обработке следующего блока\dots, пока не закончим 2m\}</tex>. Очередь <tex>B</tex> будет работать непосредственно с текущимключами элементов.
Каждому элементу Работая с блоком <tex>xC_j</tex> взаимно однозначно сопоставим ключ , будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>y = \mathtt{keymerged}(x);~x=</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{eltmerged}(y)</tex>. Все значения ключей расположим в промежутке не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, и элементы, чьи ключи находятся в очереди <tex>B</tex> будем работать со значениями ключей элементов, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.
Чтобы определить ключи элементов так, чтобы их значения были в представленном промежутке, будем, работая с блоком <tex>C_j</tex>, сливать элементы, ключи которых находятся в очереди <tex>B</tex>В итоге, с <tex>C_j^s</tex> в получим отсортированный список <tex>\mathtt{merged}</tex>.Получим ключи, сопоставив Сопоставим ключ каждому элементу в <tex>\mathtt{merged}</tex> как его позицию в этом списке. Как было замечено ранее, элементытогда справедливы утверждения, чьи ключи находятся в что <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [\mathtt{elt}(x)=\mathtt{merged}[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]x]. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в и <tex>B(\pi_{i}</tex> не больше <tex>m</tex>, тогда длина \pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<tex>\mathtt{mergedkey}(\pi_{k}</tex> не больше <tex>2m))</tex>, что позволяет однозначно определить ключи на множестве где <tex>\pi_{1,2i},\dots,2mpi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
После тогоНаходим последовательность ключей, как мы определили новые ключи для элементов, обновим ключи в очереди соответствующую элементам блока <tex>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>B\xi_j</tex>, получаем последовательность ключей в порядке исходного блока.
Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами. Затем запускаем описанный выше алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности.
В итоге, обработка блока делится на следующие этапы:
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.
* Сливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>, генерируя два вспомогательных массива <tex>\mathtt{ind_0}</tex> и <tex>\mathtt{ind_1}</tex>, хранящих индексы элементов списков <tex>C_j^s</tex> и <tex>\mathtt{elems}</tex> соответственно в списке <tex>\mathtt{merged}</tex>.* Присваеваем новые ключи элементам Действуя на последовательность ключей в порядке списка списке <tex>\mathtt{mergedind_0}</tex>перестановкой <tex>\xi_j</tex> получим ключи в порядке исходной последовательности.* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex>(элементы <tex>\mathtt{ind_1}</tex>).
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
=== Доказательство оптимальности =Пример=={{Утверждение|statement=Пусть имеется последовательность <tex>S=\{\pi_1,~\dots,~\pi_n\}</tex>, разбитая на <tex>\lceil n/m \rceil</tex> блоков <tex>C_i</tex> длины <tex>m</tex>. В результате описанного выше алгоритма получается очередь <tex>B</tex>, размер которой равен длине НВП последовательности <tex>S</tex>.|proof=Докажем, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь <tex>B</tex> хранит ключи наилучших элементов для всех возможных длин возрастающих подпоследовательностей обработанной последовательности элементов.* Пусть перед обработкой блока <tex>C_i</tex> соблюдается описанное выражение инварианта для последовательности <tex>S_{(i-1)m}=\{\pi_1,~\dots,~\pi_{(i-1)m}\}</tex>.* После слияния элементов очереди <tex>B</tex> и блока <tex>C_i^s</tex> получаем отсортированный список <tex>\mathtt{merged}</tex>. Сопоставив ключи элементам в списке, как их позиции в нём, будет выполняться условие <tex>(\pi_{u_j}<\pi_{u_k} \Longleftrightarrow \mathtt{key}(\pi_{u_j})<\mathtt{key}(\pi_{u_k}))</tex>, где <tex>\pi_{u_j},\pi_{u_k}\in \mathtt{merged}</tex>. Тогда справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов.* Во время обработки ключей элементов алгоритм <tex>\mathtt{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, ключи которых не находятся в очереди. Так как на каждой итерации алгоритма <tex>\mathrm{LIS}</tex> сохраняется выражение инварианта, что в очереди <tex>B</tex> хранятся наилучшие значения ключей элементов, которые соответствуют наилучшим элементам, для всех возможных длин возрастающих подпоследовательностей обработанной подпоследовательности, то в результате работы <tex>\mathrm{LIS}</tex> будет очередь <tex>B</tex> с ключами, соответствующими наилучшим элементам всех возможных длин возрастающих подпоследовательностей последовательности <tex>S_{im}</tex>.* Таким образом, после обработки последнего блока, в очереди <tex>B</tex> будут храниться ключи наилучших элементов для каждой длины возрастающих подпоследовательностей последовательности <tex>S_n=S</tex>. Тогда последний элемент в очереди <tex>B</tex> соответствует наилучшему элементу длины НВП последовательности <tex>S</tex>, а так как в очереди <tex>B</tex> хранятся наилучшие элементы всех возможных длин возрастающих подпоследовательностей <tex>S</tex>, то размер очереди <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.}}
===Пример===Предположим, что <tex>m=5</tex>. Исходно получаем: {| class="wikitable" style="text-align:center"| Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3|-|<tex>\pi</tex>||style="background:#FF8080"|9||style="background:#FF8080"|3||style="background:#FF8080"|10||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|12||style="background:#80FF80"|6||style="background:#80FF80"|5||style="background:#8080FF"|7||style="background:#8080FF"|11|}''' Первый блок '''
После сортировки:Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{| classmerged}="wikitable" style="text-align:center"|Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3|-|C_1^s</tex>. Присвоим ключи элементам в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя перестановкой смещений <tex>\pixi_1</tex> ||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#FF8080"|9||style="background:#FF8080"|10||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|6||style="background:#80FF80"|12||style="background:#8080FF"|7||style="background:#8080FF"|11|}на последовательность ключей в отсортированном блоке.
''' Первый блок '''
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Первый блокСортированный
|-
| <tex>\pi</tex> ||style="background:#FFA080"|9||style="background:#FFDF80"|<tex>3</tex>||style="background:#FF9580"<tex>4</tex>|10|<tex>8</tex>|style="background:#FFD580"|4<tex>9</tex>||style="background:#FFAA80"|8<tex>10</tex>
|-
|<tex>key </tex> ||style="background:#FF9980"|4||style="background:#FFE680"|<tex>1</tex>||style="background:#FF8080"<tex>2</tex>|5|<tex>3</tex>|style="background:#FFCC80"|2<tex>4</tex>||style="background:#FFB380"|3<tex>5</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|CортированныйПервый блок
|-
| <tex>\pi</tex> ||style="background:#FFDF80"<tex>9</tex>||<tex>3</tex>||<tex>10</tex>|style="background:#FFD580"|<tex>4</tex>||style="background:#FFAA80"|<tex>8||style="background:#FFA080"|9||style="background:#FF9580"|10</tex>
|-
|<tex>key </tex> ||style="background:#FFE680"<tex>4</tex>||<tex>1</tex>||<tex>5</tex>|style="background:#FFCC80"|<tex>2</tex>||style="background:#FFB380"<tex>3</tex>|3-|<tex>\xi_1</tex> |style="background:#FF9980"|<tex>4</tex>||<tex>1</tex>|style="background:#FF8080"|<tex>5</tex>||<tex>2</tex>||<tex>3</tex>
|}
|}
Обработка блока с помощью алгоритма <tex>\mathrm{LIS}</tex>.
{| class="wikitable" style="center" ; style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>4 </tex> || style="background: #9ACD32B9FFB9"| <tex>9</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>1 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>1 </tex> || style="background: #9ACD32B9FFB9"| <tex>3</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || || style="background: #77A9F4CFCFFF"| <tex>5 </tex> || style="background: #9ACD32B9FFB9"| <tex>10</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || || style="background: #77A9F4CFCFFF"| <tex>2 </tex> || style="background: #9ACD32B9FFB9"| <tex>4</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFC9C9"| <tex>3 </tex> || style="background: #77A9F4CFCFFF"| <tex>3 </tex> || style="background: #9ACD32B9FFB9"| <tex>8</tex>
|}
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.
Сливаем <tex>C_2^s</tex> и восстановленные элементы из <tex>B</tex>в <tex>\mathtt{merged}</tex> и присваиваем элементам ключи как индексы элементов в полученном списке:
{|
| ||
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
|}
|}
 
{|
| ||
{| class="wikitable" style="center"
|-align="center"
! colspan="9"|<tex>\mathtt{merged}</tex>
|-align="center"
|<tex>\pi</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>||<tex>12</tex>
|-align="center"
|<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>7</tex>||<tex>8</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="93"|<tex>\mathtt{mergedind_1}</tex>
|-align="center"
|!\pi|<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>57</tex>||<tex>6</tex>}||<tex>8</tex>|{|<tex>12</tex>class="wikitable" style="center"
|-align="center"
|!keycolspan="5"|<tex>1\mathtt{ind_0}</tex>|-align="center"|<tex>21</tex>||<tex>3</tex>||<tex>42</tex>||<tex>5</tex>||<tex>6</tex>||<tex>7</tex>||<tex>8</tex>
|}
|}
 
Получаем ключи элементов в <tex>C_2^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_2</tex>:
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Второй блокСортированный
|-
| <tex>\pi</tex> ||style="background:#FFF480"|<tex>1</tex>||style="background:#FFEA80"|<tex>2</tex>||style="background:#FF8080"<tex>5</tex>|12||style="background:#FFC080"|<tex>6</tex>||style="background:#FFCA80"|5<tex>12</tex>
|-
| <tex>key </tex> ||style="background:#FFE680"|<tex>1</tex>||style="background:#FFCC80"|<tex>2</tex>||style="background:#FF8080"<tex>5</tex>|8||style="background:#FF9980"|<tex>6</tex>||style="background:#FFB380"|5<tex>8</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|CортированныйВторой блок
|-
| <tex>\pi</tex> ||style="background:#FFF480"|<tex>1</tex>||style="background:#FFEA80"|<tex>2</tex>||style="background:#FFCA80"<tex>12</tex>|5||style="background:#FFC080"|<tex>6</tex>||style="background:#FF8080"|12<tex>5</tex>
|-
| <tex>key </tex> ||style="background:#FFE680"<tex>1</tex>|1|<tex>2</tex>||style="background:#FFCC80"<tex>8</tex>|2|<tex>6</tex>|style="background:#FFB380"|<tex>5</tex>|-| <tex>\xi_2</tex> ||<tex>1</tex>|style="background:#FF9980"|6<tex>2</tex>||<tex>5</tex>||<tex>4</tex>|style="background:#FF8080"|8<tex>3</tex>
|}
|}
Обновляем ключи в очереди:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pikey</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>3 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>3</tex> || style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || style="background: #77A9F4CFCFFF"| <tex>4</tex>
|-align="center"
| <tex>3</tex> || <tex>4</tex> || style="background:#FFCC00FFC9C9"| <tex>7 </tex> || style="background: #77A9F4CFCFFF"| <tex>7</tex>
|}
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>1 </tex> || <tex>4</tex> || <tex>7</tex> || || style="background: #77A9F4CFCFFF"| <tex>1 </tex> || style="background: #9ACD32B9FFB9"| <tex>1</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || <tex>7</tex> || || style="background: #77A9F4CFCFFF"| <tex>2 </tex> || style="background: #9ACD32B9FFB9"| <tex>2</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>7</tex> || style="background:#FFCC00FFC9C9"| <tex>8 </tex> || style="background: #77A9F4CFCFFF"| <tex>8 </tex> || style="background: #9ACD32B9FFB9"| <tex>12</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFC9C9"| <tex>6 </tex> || <tex>8</tex> || style="background: #77A9F4CFCFFF"| <tex>6 </tex> || style="background: #9ACD32B9FFB9"| <tex>6</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || <tex>8</tex> || style="background: #77A9F4CFCFFF"| <tex>5 </tex> || style="background: #9ACD32B9FFB9"| <tex>5</tex>
|}
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>\mathtt{merged}: \{1, 2, 3, 4, 5, 6, 8, 12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
Сливаем <tex>C_3^s</tex> и восстановленные элементы из <tex>B</tex>и присваиваем ключи элементам:
{|
| ||
| <tex>7</tex>||<tex>11</tex>
|}
|}
 
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| ! colspan="67"|<tex>\mathtt{merged}</tex>
|-align="center"
|!<tex>\pi</tex>||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>7</tex>||<tex>11</tex>||<tex>12</tex>
|-align="center"
|!<tex>key</tex>||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>\mathtt{ind_1}</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>6</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>\mathtt{ind_0}</tex>
|-align="center"
| <tex>4</tex>||<tex>5</tex>
|}
|}
 
Получаем ключи элементов в <tex>C_3^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_3</tex>:
{|
! colspan="3"| Третий блок
|-
| <tex>\pi</tex> ||style="background:#FFB580"|<tex>7</tex>||style="background:#FF8B80"|<tex>11</tex>
|-
| <tex>key </tex> ||style="background:#FFC080"|<tex>4</tex>||style="background:#FF8080"|<tex>5</tex>
|}
| ||
! colspan="3"|Cортированный
|-
| <tex>\pi</tex> ||style="background:#FFB580"<tex>7</tex>||<tex>11</tex>|-| <tex>key</tex> |7|<tex>4</tex>|style="background:#FF8B80"|11<tex>5</tex>
|-
| key <tex>\xi_3</tex> ||style="background:#FFC080"<tex>1</tex>|4||style="background:#FF8080"|5<tex>2</tex>
|}
|}
Обновление старых ключей:
{| class="wikitable" style="center" style="background: #ffffcc"
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pikey</tex>
|-align="center"
| style="background:#FFCC00FFC9C9"| <tex>1 </tex> || || || || style="background: #77A9F4CFCFFF"| <tex>1</tex>
|-align="center"
| <tex>1</tex> || style="background:#FFCC00FFC9C9"| <tex>2 </tex> || || || style="background: #77A9F4CFCFFF"| <tex>2</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCC00FFC9C9"| <tex>3 </tex> || || style="background: #77A9F4CFCFFF"| <tex>3</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || style="background:#FFCC00FFC9C9"| <tex>6 </tex> || style="background: #77A9F4CFCFFF"| <tex>6</tex>
|}
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>B_5</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || style="background:#FFCC00FFC9C9"| <tex>4 </tex> || || style="background: #77A9F4CFCFFF"| <tex>4 </tex> || style="background: #9ACD32B9FFB9"| <tex>7</tex>
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || style="background:#FFCC00FFC9C9"| <tex>5 </tex> || style="background: #77A9F4CFCFFF"| <tex>5 </tex> || style="background: #9ACD32B9FFB9"| <tex>11</tex>
|}
Результат завершения алгоритма:
|}
===Оценка времени работыНахождение размера блоков ===Так как размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, а количество блоков всего <tex>\lceil n/m \rceil</tex>. То общее количество присваиваний новых ключей элементам последовательности, также как и количество операций слияния списков, не больше <tex>2cm\cdot\dfrac{n}{m}=O(n)</tex>, где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(\log \log m)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m</tex>.
Рассмотрим последовательность <tex>\{m_0,~m_1,~m_2,~\dots\}</tex>, где <tex> m_{i+1} = m_i ^{\operatorname{log}m_i} = 2^{\operatorname{log}^2m_i}</tex>, <tex>m_0</tex> — некоторое значение, меньшее <tex>k</tex>.
Будем по порядку последовательно для элементов этой последовательности запускать алгоритм, представленный выше. Если размер очереди <tex>B</tex> становится больше <tex>m_i</tex>, то условие <tex>m \geqslant k</tex> перестает выполняться, тогда останавливаем алгоритм и переходим к следующему значению <tex>m_{i+1}</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant k</tex>, то алгоритм успешно завершится.
Таким образомДля каждого <tex>m_i</tex> размер списка <tex>\mathtt{merged}</tex> не больше <tex>2m_i</tex>, а количество блоков всего <tex>\lceil n/m_i \rceil</tex>. То общее количество присваиваний новых ключей элементам последовательности, также как и количество операций слияния списков, не больше <tex>2cm_i\cdot\dfrac{n}{m_i}=O(n)</tex>, время работы запущенного алгоритма где c — некоторая константа. Каждая операция с приоритетной очередью требует <tex>O(n \log \log {m_i})</tex> для времени, так как элементы в <tex>B</tex> не больше <tex>0\leqslant i \leqslant j2m_i</tex>.
ЗаметимТаким образом, что время работы запущенного алгоритма для каждого <tex>m_i</tex> — <tex>O(n \log \log {m_i})</tex>. Когда найдётся первое <tex>m_j:m_j\geqslant k</tex>, то алгоритм успешно завершится.
<tex>\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</tex>.
<tex>\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i</tex>
Общее время работы алгоритма по всем для всех обработанных значений <tex>m_i</tex> — <tex>O(n(\sum_{i=0}\limits^{j}{2^{-(i-1)}})\log \log m_i) = O(n\operatorname{log}\operatorname{log}m_i)</tex>. Обратим вниманиеЗаметим, что <tex>m_i < k^{\operatorname{log}k}</tex>, так как в противном случае <tex>m_{i-1} > k</tex>, что противоречит тому, что <tex>m_i</tex> — первый из тех, которые больше <tex>k</tex>. Следовательно, <tex>\operatorname{log}\operatorname{log}m_i < 2\operatorname{log}\operatorname{log}k \</tex>.
Тогда алгоритм также работает за Получаем время работы <tex>O(n\operatorname{log}\operatorname{log}k)</tex>.
== См. также ==
Artem.ustinov
76
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/63356...63629»

Навигация