Изменения

* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для подпоследовательности <tex>\pi_1, \pi_2,~\dots~,\pi_{i-1}</tex>, тогда с ним можно сделать возрастающую подпоследовательность максимальной длины из уже рассмотренных, в которой он будет последним элементом. Значит, записываем его в конец <tex>B</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.

==== Пример ====

Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <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>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.

=== Деление на блоки===

Обозначим за <tex>C_j^s</tex> отсортированный блок <tex>C_j</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>

|}

|-

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

|}

''' Первый блок '''

{|

| ||

{| class="wikitable" style="text-align:center"

|-

|-

|}

| ||

{| class="wikitable" style="text-align:center"

|-

|-

|}

|}

Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.

{|

| ||

| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>

|}

| ||

{| class="wikitable" style="center"

|-align="center"

|-align="center"

|-align="center"

|}

|}

{|

| ||

{| class="wikitable" style="text-align:center"

|-

|-

|}

| ||

{| class="wikitable" style="text-align:center"

|-

|-

|}

|}

Обновляем ключи в очереди:

{| class="wikitable" style="center" style="background: #ffffcc"

|-align="center"

| style="background:#FFC9C9"| <tex>3</tex> || || || style="background: #CFCFFF"| <tex>3</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>7</tex>||<tex>11</tex>

|}

| ||

{| class="wikitable" style="center"

|-align="center"

|-align="center"

|-align="center"

|}

|}

{|

| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>

|-

|}

| ||

| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>

|-

|}

|}

Обновление старых ключей:

{| class="wikitable" style="center" style="background: #ffffcc"

|-align="center"

| style="background:#FFC9C9"| <tex>1</tex> || || || || style="background: #CFCFFF"| <tex>1</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>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>O(n\operatorname{log}\operatorname{log}k)</tex>.