76
правок
Изменения
→Деление на блоки
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем восстановить НВП.
==== Общий вид алгоритма ====
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
|-align="center"
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || style="background:#FFCFCF"| <tex>7</tex> || style="background:#FFCFCF"| <tex>11</tex> || style="background: #CFCFFF"| <tex>11</tex>
|}
{| class="wikitable" style="color: black; background-color:#ffffcc;" cellpadding="10"
Обозначим за <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>x</tex> взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Очередь <tex>B</tex> будет работать непосредственно с ключами элементов. Определим ключи элементов так, чтобы их значения были в промежутке <tex>\{1,2,\dots,2m\}</tex>. Работая с блоком <tex>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.
Предположим, что <tex>m=5</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>
|}
|-
|<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>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.
В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливы утверждения, что <tex>\mathtt{elt}(x)=\mathtt{merged}[x]</tex> и <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
Находим последовательность ключей, соответствующую элементам блока <tex>C_j^s</tex>. Действуя на эту последовательность перестановкой <tex>\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{ind_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>.
====Пример====
''' Первый блок '''
Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Тогда, присвоив Присвоим ключи элементов элементам в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, получим:действуя перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке.
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Первый блокСортированный
|-
| <tex>\pi</tex> ||<tex>93</tex>||<tex>34</tex>||<tex>108</tex>||<tex>49</tex>||<tex>810</tex>
|-
| <tex>key</tex> ||<tex>41</tex>||<tex>12</tex>||<tex>53</tex>||<tex>24</tex>||<tex>35</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|СортированныйПервый блок|-| <tex>\pi</tex> ||<tex>9</tex>||<tex>3</tex>||<tex>10</tex>||<tex>4</tex>||<tex>8</tex>
|-
| <tex>\pikey</tex> ||<tex>34</tex>||<tex>41</tex>||<tex>85</tex>||<tex>92</tex>||<tex>103</tex>
|-
| <tex>key\xi_1</tex> ||<tex>14</tex>||<tex>21</tex>||<tex>35</tex>||<tex>42</tex>||<tex>53</tex>
|}
|}
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
|}
|}
{|
| ||
{| class="wikitable" style="center"
|-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="3"|<tex>\mathtt{ind_1}</tex>
|-align="center"
| <tex>3</tex>||<tex>4</tex>||<tex>7</tex>
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>\mathtt{ind_0}</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>
|}
|}
Получаем ключи элементов в <tex>C_2^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_2</tex>:
{|
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|Второй блокСортированный
|-
| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>125</tex>||<tex>6</tex>||<tex>512</tex>
|-
| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>85</tex>||<tex>6</tex>||<tex>58</tex>
|}
| ||
{| class="wikitable" style="text-align:center"
! colspan="6"|CортированныйВторой блок|-| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>12</tex>||<tex>6</tex>||<tex>5</tex>
|-
| <tex>\pikey</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>58</tex>||<tex>6</tex>||<tex>125</tex>
|-
| <tex>key\xi_2</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>64</tex>||<tex>83</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:#FFC9C9"| <tex>3</tex> || || || style="background: #CFCFFF"| <tex>3</tex>
| <tex>7</tex>||<tex>11</tex>
|}
|}
{|
| ||
{| class="wikitable" style="center"
|-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>:
{|
|-
| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>
|-
| <tex>\xi_3</tex> ||<tex>1</tex>||<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:#FFC9C9"| <tex>1</tex> || || || || style="background: #CFCFFF"| <tex>1</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_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(\log \log m_i)</tex> времени, так как элементы в <tex>B</tex> не больше <tex>2m_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_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>.
