Изменения

Во время обработки ключей элементов описанный выше алгоритм <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>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>\mathtt{merged}xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливо утверждение, что Т.е. если элемент <tex>(\pi_{i}pi<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})/tex> находится в исходной перестановке в блоке <\mathtt{key}(\pi_{k}))tex>C_j</tex>, где на позиции <tex>\pi_{i}</tex>,то в блоке <tex>C_j^s</tex> он на позиции <tex>\pi_{k}\in \mathtt{merged}xi_i</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>\mathtt{merged}</tex>.* Присваиваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex>.* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex>.* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>. ====Пример====

! 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>

! colspan="6"|CортированныйПервый блок|-| <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>C_2^s</tex> и восстановленные элементы из <tex>B</tex>в <tex>\mathtt{merged}</tex> и присваиваем элементам ключи как индексы элементов в полученном списке:

! 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>

! colspan="6"|CортированныйВторой блок

| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>12</tex>||<tex>6</tex>||<tex>5</tex>|-| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>8</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>

! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>\pikey</tex>

Сливаем <tex>C_3^s</tex> и восстановленные элементы из <tex>B</tex>и присваиваем ключи элементам:

! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>\pikey</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_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>.