Быстрый поиск наибольшей возрастающей подпоследовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Оптимизация до O(n log log k))
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 5 участников)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
{{Задача
 
{{Задача
|definition = Дана {{Acronym | перестановка | на самом деле может быть и мультиперестановкой }} <tex>\pi</tex> <tex>\{1, 2,~\dots,~n\}</tex>. Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> — длина НВП.
+
|definition = Дана перестановка <tex>\pi</tex> множества <tex>~\{1, 2,~\dots,~n\}</tex>. Требуется найти [[Задача о наибольшей возрастающей подпоследовательности | НВП]] <tex>\pi</tex> за <tex>O(n\operatorname{log}\operatorname{log}k)</tex>, где <tex>k</tex> — длина НВП.
 
}}
 
}}
  
 
[[Файл:Task.jpg]]
 
[[Файл:Task.jpg]]
== Алгоритм O(n log log n) ==
+
== Алгоритм за O(n log log n) ==
 
=== Нахождение длины НВП ===
 
=== Нахождение длины НВП ===
 
==== Основная идея ====
 
==== Основная идея ====
Пусть <tex>\pi(n)</tex> — входная перестановка.
+
Пусть <tex>\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка.
  
Для каждой длины <tex>l = 1, 2, \dots</tex> предполагаемой НВП находим наименьший {{Acronym | элемент| назовем его лучшим элементом для заданной длины }}, что может быть последним в возрастающей подпоследовательности длины <tex>l</tex>, запишем их в массив <tex>B[l]</tex>.
+
Будем последовательно обрабатывать элементы в порядке <tex>\pi_1, \pi_2,~\dots,~\pi_n\colon</tex>
  
Если обрабатываемый элемент <tex>\pi(i)</tex> больше последнего элемента какой-нибудь возрастающей последовательности, он может ее увеличить.  
+
Для каждой длины <tex>l = 1, 2,~\dots,~n</tex> предполагаемой НВП находим наименьший элемент, который может быть последним в возрастающей подпоследовательности длины <tex>l</tex> и запишем его в массив <tex>B_l</tex>. Будем называть его наилучшим элементом для длины <tex>l</tex>.
  
Будем последовательно обрабатывать элементы <tex>\pi(1), \pi(2),~\dots,~\pi(n)</tex>:
+
* Если <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>\pi(i)</tex> больше {{Acronym | <tex>\pi(1), \pi(2),~\dots~,\pi(i-1)</tex> | всех уже полученных значений B }}, значит с ним можно сделать максимальную, из уже рассмотренных, возрастающую подпоследовательность. Записываем его в конец <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>\pi(i)</tex> заменяет наименьший лучший элемент, из тех, что больше <tex>\pi(i)</tex>.
 
  
Следует отметить, что полученный массив также образует возрастающую последовательность, где мы должны выполнять операции <tex>insert, next, delete</tex>, соответственно целесообразно использовать [[ Приоритетные очереди | приоритетную очередь]], реализованную через [[Дерево ван Эмде Боаса]]. Таким образом получаем <tex>O(\operatorname{log}\operatorname{log} n)</tex> амортизированного времени на одну операцию.
 
 
==== Пример ====
 
==== Пример ====
===== Типы операций =====
+
''' Типы операций '''
  
 
* Добавление элемента, который больше всех предыдущих:
 
* Добавление элемента, который больше всех предыдущих:
Строка 32: Строка 29:
 
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
 
[[Файл:Operation2_1.jpg]] <tex>\longrightarrow</tex> [[Файл:Operation2_2.jpg]]
  
===== {{Acronym |Последовательность | именно она будет рассматриваться далее}} =====
+
''' Пример последовательности '''
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
|-align="center"
 
|-align="center"
 
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
 
! <tex>\pi_1</tex> || <tex>\pi_2</tex> || <tex>\pi_3</tex> || <tex>\pi_4</tex> || <tex>\pi_5</tex> || <tex>\pi_6</tex> || <tex>\pi_7</tex> || <tex>\pi_8</tex> || <tex>\pi_9</tex> || <tex>\pi_{10}</tex> || <tex>\pi_{11}</tex> || <tex>\pi_{12}</tex>
 
|-align="center"
 
|-align="center"
|  9 || 3 || 10 || 4 || 8 || 1 || 2 || 12 || 6 || 5 || 7 || 11
+
<tex>9</tex> || <tex>3</tex> || <tex>10</tex> || <tex>4</tex> || <tex>8</tex> || <tex>1</tex> || <tex>2</tex> || <tex>12</tex> || <tex>6</tex> || <tex>5</tex> || <tex>7</tex> || <tex>11</tex>
 
|}
 
|}
===== Состояние очереди при каждом добавлении =====
+
 
 +
''' Состояние очереди при каждом добавлении '''
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
|-align="center"
 
|-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>
 
! <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"  
 
|-align="center"  
| style="background:#FFCC00"| 9 ||  ||  ||  ||  || style="background: #77A9F4"| 9
+
| style="background:#FFCFCF"| <tex>9</tex> ||  ||  ||  ||  || style="background: #CFCFFF"| <tex>9</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 3 ||  ||  ||  ||  || style="background: #77A9F4"| 3
+
| style="background:#FFCFCF"| <tex>3</tex> ||  ||  ||  ||  || style="background: #CFCFFF"| <tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || style="background:#FFCC00"| 10 ||  ||  ||  || style="background: #77A9F4"| 10
+
| <tex>3</tex> || style="background:#FFCFCF"| <tex>10</tex> ||  ||  ||  || style="background: #CFCFFF"| <tex>10</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || style="background:#FFCC00"| 4 ||  ||  ||  || style="background: #77A9F4"| 4
+
| <tex>3</tex> || style="background:#FFCFCF"| <tex>4</tex> ||  ||  ||  || style="background: #CFCFFF"| <tex>4</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || 4 || style="background:#FFCC00"| 8 ||  ||  || style="background: #77A9F4"| 8
+
| <tex>3</tex> || <tex>4</tex> || style="background:#FFCFCF"| <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>8</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 || 4 || 8 ||  ||  || style="background: #77A9F4"| 1
+
| style="background:#FFCFCF"| <tex>1</tex> || <tex>4</tex> || <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>1</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 2 || 8 ||  ||  || style="background: #77A9F4"| 2
+
| <tex>1</tex> || style="background:#FFCFCF"| <tex>2</tex> || <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>2</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 8 || style="background:#FFCC00"| 12 ||  || style="background: #77A9F4"| 12
+
| <tex>1</tex> || <tex>2</tex> || <tex>8</tex> || style="background:#FFCFCF"| <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>12</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 6 || 12 ||  || style="background: #77A9F4"| 6
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCFCF"| <tex>6</tex> || <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>6</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 5 || 12 ||  || style="background: #77A9F4"| 5
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCFCF"| <tex>5</tex> || <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>5</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 5 || style="background:#FFCC00"| 7 ||  || style="background: #77A9F4"| 7
+
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || style="background:#FFCFCF"| <tex>7</tex> ||  || style="background: #CFCFFF"| <tex>7</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 5 || 7 || style="background:#FFCC00"| 11 || style="background: #77A9F4"| 11
+
| <tex>1</tex> || <tex>2</tex> || <tex>5</tex> || <tex>7</tex> || style="background:#FFCFCF"| <tex>11</tex> || style="background: #CFCFFF"| <tex>11</tex>
 
|}
 
|}
  
 
==== Псевдокод ====
 
==== Псевдокод ====
<code>
+
 
    '''int''' LIS(<tex>\pi</tex>[n])
+
'''int''' LIS(<tex>\pi</tex>[n])
        '''PriorityQueue''' B <font color=darkgreen>// рабочая приоритетная очередь</font>
+
    '''PriorityQueue''' B <font color=darkgreen>// рабочая приоритетная очередь</font>
        '''int''' k = 0      <font color=darkgreen>// длина НВП</font>
+
    '''int''' k = 0      <font color=darkgreen>// длина НВП</font>
        '''for''' i = 1 '''to''' n
+
    '''for''' i = 1 '''to''' n
            x = <tex>\pi</tex>[i]
+
        x = <tex>\pi</tex>[i]
            <font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
+
        <font color=darkgreen>// в любом случае добавляем в очередь очередной элемент</font>
            <font color=darkgreen>// устаревшие будем удалять</font>
+
        <font color=darkgreen>// устаревшие будем удалять</font>
            B.insert(x)
+
        B.insert(x)
            '''if''' <tex>\exists</tex> B.next(x)
+
        '''if''' <tex>\exists</tex> B.next(x)
                <font color=darkgreen>// добавленный элемент — не максимальный</font>
+
            <font color=darkgreen>// добавленный элемент — не максимальный</font>
                <font color=darkgreen>// удаляем предыдущее значение — заменяем {{Acronym |следующий|минимальный из бóльших}}</font>
+
            <font color=darkgreen>// удаляем следующее за x значение </font>
                B.delete(B.next(x))
+
            B.delete(B.next(x))
            '''else'''
+
        '''else'''
                <font color=darkgreen>// добавленный элемент — максимальный</font>
+
            <font color=darkgreen>// добавленный элемент — максимальный</font>
                <font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
+
            <font color=darkgreen>// предыдущие значения не трогаем, очередь увеличилась</font>
                k = k + 1           
+
            k = k + 1           
        '''return''' k</code>
+
    '''return''' k
  
 
=== Расширение алгоритма до нахождения НВП ===
 
=== Расширение алгоритма до нахождения НВП ===
Строка 93: Строка 91:
 
Будем запоминать пары: для каждого элемента записываем его "предшественника".
 
Будем запоминать пары: для каждого элемента записываем его "предшественника".
  
Тогда, выбрав какой-нибудь лучший элемент для максимальной длины, мы можем легко {{Acronym | восстановить НВП | вообще говоря, не все }}.
+
Тогда, пройдя по предшественникам, начиная с последнего элемента очереди <tex>B</tex>, мы можем восстановить НВП.
 
==== Общий вид алгоритма ====
 
==== Общий вид алгоритма ====
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
{| class="wikitable" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
Строка 99: Строка 97:
 
! <tex>B_1</tex> || <tex>B_2</tex> || <tex>B_3</tex> || <tex>B_4</tex> || <tex>B_5</tex> || <tex>~\pi_i~</tex>
 
! <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"  
 
|-align="center"  
| 9 ||  ||  ||  ||  || style="background: #77A9F4"| 9
+
| <tex>9</tex> ||  ||  ||  ||  || style="background: #CFCFFF"| <tex>9</tex>
 
|-align="center"  
 
|-align="center"  
| 3 ||  ||  ||  ||  || style="background: #77A9F4"| 3
+
| <tex>3</tex> ||  ||  ||  ||  || style="background: #CFCFFF"| <tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || 10 ||  ||  ||  || style="background: #77A9F4"| 10
+
| <tex>3</tex> || <tex>10</tex> ||  ||  ||  || style="background: #CFCFFF"| <tex>10</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || 4 ||  ||  ||  || style="background: #77A9F4"| 4
+
| <tex>3</tex> || <tex>4</tex> ||  ||  ||  || style="background: #CFCFFF"| <tex>4</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || 4 || 8 ||  ||  || style="background: #77A9F4"| 8
+
| <tex>3</tex> || <tex>4</tex> || <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>8</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 || 4 || 8 ||  ||  || style="background: #77A9F4"| 1
+
| style="background:#FFDF90"| <tex>1</tex> || <tex>4</tex> || <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>1</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FF7F00"|1 || style="background:#FFCC00"| 2 || 8 ||  ||  || style="background: #77A9F4"| 2
+
| style="background:#FFCFCF"| <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>8</tex> ||  ||  || style="background: #CFCFFF"| <tex>2</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"|2 || 8 || 12 ||  || style="background: #77A9F4"| 12
+
| <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>8</tex> || <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>12</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"|2 || 6 || 12 ||  || style="background: #77A9F4"| 6
+
| <tex>1</tex> || style="background:#FFDF90"| <tex>2</tex> || <tex>6</tex> || <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>6</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FF7F00"|2 || style="background:#FFCC00"| 5 || 12 ||  || style="background: #77A9F4"| 5
+
| <tex>1</tex> || style="background:#FFCFCF"| <tex>2</tex> || style="background:#FFDF90"| <tex>5</tex> || <tex>12</tex> ||  || style="background: #CFCFFF"| <tex>5</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FF7F00"| 5 || style="background:#FFCC00"| 7 ||  || style="background: #77A9F4"| 7
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFCFCF"| <tex>5</tex> || style="background:#FFDF90"| <tex>7</tex> ||  || style="background: #CFCFFF"| <tex>7</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 5 || style="background:#FF7F00"| 7 || style="background:#FF7F00"| 11 || style="background: #77A9F4"| 11
+
| <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" align="leftborder" style="color: black; background-color:#ffffcc;" cellpadding="10"
+
{| class="wikitable" style="color: black; background-color:#ffffcc;" cellpadding="10"
 
|-align="center"
 
|-align="center"
 
! colspan="12" | predecessor
 
! colspan="12" | predecessor
 
|-align="center"
 
|-align="center"
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12  
+
! <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex> || <tex>8</tex> || <tex>9</tex> || <tex>10</tex> || <tex>11</tex> || <tex>12</tex>
 
|-align="center"
 
|-align="center"
|  || 1 ||  || 3 || 2 || 2 || 5 || 4 ||  || 3 || 7 || 8
+
|  || <tex>1</tex> ||  || <tex>3</tex> || <tex>2</tex> || <tex>2</tex> || <tex>5</tex> || <tex>4</tex> ||  || <tex>3</tex> || <tex>7</tex> || <tex>8</tex>
 
|}
 
|}
 +
 
==== Псевдокод ====
 
==== Псевдокод ====
<code>
+
 
    '''vector<int>''' LIS(<tex>\pi</tex>[n])
+
'''int[]''' LIS(<tex>\pi</tex>[n])
        '''PriorityQueue''' B
+
    '''PriorityQueue''' B
        '''int''' k = 0
+
    '''int''' k = 0
        <font color=blue>'''int''' predecessor[n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
+
    <font color=blue>'''int''' predecessor[n]</font> <font color=darkgreen>// резервируем <tex>n</tex> позиций</font>
        '''for''' i = 1 '''to''' n
+
    '''for''' i = 1 '''to''' n
            x = <tex>\pi</tex>[i]
+
        x = <tex>\pi</tex>[i]
            B.insert(x)
+
        B.insert(x)
            <font color=blue>predecessor[x] = B.prev(x)</font>
+
        <font color=blue>predecessor[x] = B.prev(x)</font>
            '''if''' <tex>\exists</tex> B.next(x)
+
        '''if''' <tex>\exists</tex> B.next(x)
                B.delete(B.next(x))
+
            B.delete(B.next(x))
            '''else'''
+
        '''else'''
                k = k + 1
+
            k = k + 1
        <font color=darkgreen>// по цепочке от последнего элемента  
+
    <font color=darkgreen>// по цепочке от последнего элемента  
        // восстанавливаем НВП</font>
+
    // восстанавливаем НВП</font>
        <font color=blue>'''int''' result[k]
+
    <font color=blue>'''int''' result[k]
        '''int''' cur = B.max()
+
    '''int''' cur = B.max
        '''for''' i = k - 1 '''downto''' 0
+
    '''for''' i = k - 1 '''downto''' 0
            result[i] = cur
+
        result[i] = cur
            cur = predecessor[cur]
+
        cur = predecessor[cur]
        '''return''' result</font>
+
    '''return''' result</font>
</code>
 
  
 
== Оптимизация до O(n log log k) ==
 
== Оптимизация до O(n log log k) ==
=== Основная идея ===
+
===Основная идея===
 
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
 
Чтобы [[Дерево ван Эмде Боаса]] выполняло операции за <tex>O(\operatorname{log}\operatorname{log}k)</tex>, необходимо алфавит обрабатываемых значений уменьшить до <tex>O(k)</tex>.
  
Предположим, мы знаем такое {{Acronym|приближение числа <tex>k</tex>|далее рассмотрим нахождение и насколько оно точное}} числом <tex>m: m \geqslant k</tex>. Если мы разобьем всю последовательность на блоки из {{ Acronym|<tex>m</tex> элементов|последний блок может быть меньше}} и нам удастся обрабатывать каждый как перестановку из <tex>m</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>k</tex> числом <tex>m: m \geqslant k</tex>. Мы обсудим, как найти такое <tex>m</tex> позже.
  
'''''Описанный здесь алгоритм подбора <tex>m_i</tex> и получение асимптотической оценки <tex>O(n\operatorname{log}\operatorname{log}k)</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>\{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>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>
  
Будем последовательно для элементов этой последовательности запускать {{Acronym|алгоритм|о котором ниже}}. Если условие <tex>m \geqslant k</tex> перестает выполняться, прерываем выполнение. Таким образом, время работы для каждого <tex>m_j</tex> будет <tex>O(n\operatorname{log}\operatorname{log}m_j)</tex>. {{Acronym|Найдется|первый из подобных}} такой <tex>m_i</tex>, который окажется больше <tex>k</tex>, и алгоритм успешно завершится.  
+
Обозначим за <tex>C_j^s</tex> отсортированный блок <tex>C_j</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>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, рассматривая номер блока как старший разряд, элемент как младший разряд (по смещению внутри блока не сортируем), можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>.
  
<tex>\operatorname{log}\operatorname{log}m_j = 2^{j-i}\operatorname{log}\operatorname{log}m_i</tex>
+
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки <tex>\xi</tex>, элементы которой соотносятся между собой как элементы исходного блока. Т.е. если элемент <tex>\pi</tex> находится в исходной перестановке в блоке <tex>C_j</tex> на позиции <tex>i</tex>, то в блоке <tex>C_j^s</tex> он на позиции <tex>\xi_i</tex>.
 
 
{{Acronym|Общее время|для всех обработанных значений m}} работы — <tex>O(n(\sum\limits_{j = 0}\limits^{i}2^{1-j})\operatorname{log}\operatorname{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>.
+
====Пример====
=== Деление на блоки ===
+
Предположим, что <tex>m=5</tex>. Исходно получаем:
==== Основная идея ====
 
Разделим исходную перестановку <tex>\pi</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>O(\dfrac{n}{m}n)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>.
 
 
Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>.
 
==== Пример ====
 
Пусть <tex>m = 5</tex>. Исходно:
 
 
{| class="wikitable" style="text-align:center"
 
{| 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
+
| Блок ||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:#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>\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:#FF8080"|1||style="background:#FF8080"|2||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|5||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|3||style="background:#80FF80"|4||style="background:#80FF80"|5||style="background:#8080FF"|1||style="background:#8080FF"|2
+
|Смещение ||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"
 
{| 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
+
|Блок ||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:#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
+
|<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:#FF8080"|2||style="background:#FF8080"|4||style="background:#FF8080"|5||style="background:#FF8080"|1||style="background:#FF8080"|3||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|4||style="background:#80FF80"|3||style="background:#8080FF"|1||style="background:#8080FF"|2
+
|Смещение ||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>):
 
Обратные перестановки (<tex>\xi</tex>):
 
{| class="wikitable" style="center" style="background:#FFCC80"
 
{| class="wikitable" style="center" style="background:#FFCC80"
! colspan="5"|1 || colspan="5"|2 || colspan="3"|3
+
! colspan="5"|<tex>1</tex> || colspan="5"|<tex>2</tex> || colspan="3"|<tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFD0D0"|4||style="background:#FFD0D0"|1||style="background:#FFD0D0"|5||style="background:#FFD0D0"|2||style="background:#FFD0D0"|3  
+
| 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"|1||style="background:#D0FFD0"|2||style="background:#D0FFD0"|5||style="background:#D0FFD0"|4||style="background:#D0FFD0"|3  
+
| 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"|1||style="background:#D0D0FF"|2
+
| 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> будет работать непосредственно с ключами элементов.
* {{Acronym|Достаем из очереди ключи|если это первый блок — ничего не делаем}} и конвертируем их в элементы <tex>\pi</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>, получаем последовательность ключей в порядке исходного блока.
  
* Классический [[Сортировка слиянием#Принцип работы#Слияние двух массивов | merge]] только что полученных элементов <tex>\pi</tex> с элементами нового блока, но с модификацией: генерируются 2 дополнительных массива - индексы элементов исходных массивов в новом. Слияние массивов назовем <tex>merged</tex>.
+
Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке, будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
  
* На массив индексов, относящиеся к новому блоку, действует перестановка смещений сортированного варианта этого блока. Таким образом мы добиваемся эквиваленции отношений {{Acronym|ключей|смещений}} к отношениям элементов в очереди и элементов в блоке, а ключи находятся в диапазоне <tex>O(m)</tex>.  
+
Затем запускаем алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности.
  
* Первый массив индексов, который соответствует элементам, ранее находящимся в очереди, вновь кладутся в очередь (обычными <tex>insert</tex>-ами). Второй массив обрабатывается описанным выше алгоритмом <tex>LIS</tex>, при том массив <tex>predecessor</tex> строится из ключей с помощью <tex>merged</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>.
  
==== Визуализация ====
+
====Пример====
Помеченные <font color=green>зеленым</font> — условные данные. Остальное — условные операции. Например <tex>keys \longrightarrow merged</tex> значит взять элементы из массива <tex>merged</tex> c индексами из <tex>keys</tex>. <tex>merge \longrightarrow merged</tex> — здесь <tex>merged</tex> обозначает результат операции '''merge'''.
 
  
[[Файл:blockHandle.jpg]]
+
''' Первый блок '''
  
Для первого блока содержательным является лишь ветка, начинающаяся с <tex>C_j^S \longrightarrow merge \longrightarrow ind's\#1</tex>, что не противоречит представленной схеме.
+
Так как очередь <tex>B</tex> в начале пуста, то <tex>\mathtt{merged}=C_1^s</tex>. Присвоим ключи элементам в списке <tex>\mathtt{merged}</tex> как их индексы в этом списке. Восстанавливаем последовательность ключей элементов в порядке исходной последовательности, действуя перестановкой смещений <tex>\xi_1</tex> на последовательность ключей в отсортированном блоке.
  
==== Пример ====
 
===== Первый блок =====
 
 
{|
 
{|
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="text-align:center"
! colspan="5"|Первый блок
+
! colspan="6"|Сортированный
|-align="center"
+
|-
|style="background:#FFA080"|9||style="background:#FFDF80"|3||style="background:#FF9580"|10||style="background:#FFD580"|4||style="background:#FFAA80"|8
+
| <tex>\pi</tex> ||<tex>3</tex>||<tex>4</tex>||<tex>8</tex>||<tex>9</tex>||<tex>10</tex>
|-align="center"
+
|-
|style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|3||style="background:#FF9980"|4||style="background:#FF8080"|5
+
| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>
 
|}
 
|}
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="text-align:center"
! colspan="5"|Cортированный
+
! colspan="6"|Первый блок
|-align="center"
+
|-
|style="background:#FFDF80"|3||style="background:#FFD580"|4||style="background:#FFAA80"|8||style="background:#FFA080"|9||style="background:#FF9580"|10
+
| <tex>\pi</tex> ||<tex>9</tex>||<tex>3</tex>||<tex>10</tex>||<tex>4</tex>||<tex>8</tex>
|-align="center"
+
|-
|style="background:#FFCC80"|2||style="background:#FF9980"|4||style="background:#FF8080"|5||style="background:#FFE680"|1||style="background:#FFB380"|3
+
| <tex>key</tex> ||<tex>4</tex>||<tex>1</tex>||<tex>5</tex>||<tex>2</tex>||<tex>3</tex>
 +
|-
 +
| <tex>\xi_1</tex> ||<tex>4</tex>||<tex>1</tex>||<tex>5</tex>||<tex>2</tex>||<tex>3</tex>
 
|}
 
|}
 
|}
 
|}
<tex>merged</tex> аналогичен сортированному, т.к. предыдущих ключей нет.
+
 
{| class="wikitable" style="center"
+
Обработка блока с помощью алгоритма <tex>\mathrm{LIS}</tex>.
! colspan="5"|Ключи сортированного блока
+
 
|-align="center"
+
{| class="wikitable" style="center"; style="background: #ffffcc"
| 2||4||5||1||3
+
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>||<tex>\pi</tex>
|}
 
{| class="wikitable" style="center"
 
! colspan="5"| <tex>\xi</tex>
 
|-align="center"
 
| 4||1||5||2||3
 
|}
 
Пропускаем их через <tex>LIS</tex>:
 
{| class="wikitable" style="center"
 
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 4 ||  ||  || style="background: #77A9F4"| 4
+
| style="background:#FFC9C9"| <tex>4</tex> ||  ||  || style="background: #CFCFFF"| <tex>4</tex> || style="background: #B9FFB9"| <tex>9</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 ||  ||  || style="background: #77A9F4"| 1
+
| style="background:#FFC9C9"| <tex>1</tex> ||  ||  || style="background: #CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 5 ||  || style="background: #77A9F4"| 5
+
| <tex>1</tex> || style="background:#FFC9C9"| <tex>5</tex> ||  || style="background: #CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>10</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 2 ||  || style="background: #77A9F4"| 2
+
| <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> ||  || style="background: #CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>4</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 3 || style="background: #77A9F4"| 3
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>3</tex> || style="background: #CFCFFF"| <tex>3</tex> || style="background: #B9FFB9"| <tex>8</tex>
 
|}
 
|}
''' Результат работы '''
+
 
 +
В результате получаем
  
 
<tex>B: \{1, 2, 3\}</tex>
 
<tex>B: \{1, 2, 3\}</tex>
  
<tex>merged: \{3, 4, 8, 9, 10\}</tex>
+
<tex>\mathtt{merged}: \{3,4,8,9,10\}</tex>
===== Второй блок =====
+
 
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>merged: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 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> и присваиваем элементам ключи как индексы элементов в полученном списке:
 
{|
 
{|
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="center"
! colspan="5"|Второй блок
 
 
|-align="center"
 
|-align="center"
|style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FF8080"|12||style="background:#FFC080"|6||style="background:#FFCA80"|5
+
| colspan="3"|<tex>B</tex>
 
|-align="center"
 
|-align="center"
|style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FFB380"|3||style="background:#FF9980"|4||style="background:#FF8080"|5
+
| <tex>3</tex>||<tex>4</tex>||<tex>8</tex>
 
|}
 
|}
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="center"
! colspan="5"|Cортированный
 
 
|-align="center"
 
|-align="center"
|style="background:#FFF480"|1||style="background:#FFEA80"|2||style="background:#FFCA80"|5||style="background:#FFC080"|6||style="background:#FF8080"|12
+
| colspan="5"|<tex>C_2^s</tex>
 
|-align="center"
 
|-align="center"
|style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FF8080"|5||style="background:#FF9980"|4||style="background:#FFB380"|3
+
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
 
|}
 
|}
 
|}
 
|}
Строка 300: Строка 297:
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="8"|<tex>merged</tex>
+
! 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"
 
|-align="center"
| 1||2||3||4||5||6||8||12
+
|<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"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="3"|<tex>ind's\#0</tex> — индексы текущих
+
| colspan="3"|<tex>\mathtt{ind_1}</tex>
 
|-align="center"
 
|-align="center"
| 3||4||7
+
| <tex>3</tex>||<tex>4</tex>||<tex>7</tex>
 
|}
 
|}
 
| ||
 
| ||
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="5"|<tex>ind's\#1</tex> — индексы новых
+
| colspan="5"|<tex>\mathtt{ind_0}</tex>
 
|-align="center"
 
|-align="center"
| 1||2||5||6||8
+
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>
 
|}
 
|}
 
|}
 
|}
  
{| class="wikitable" style="center"
+
Получаем ключи элементов в <tex>C_2^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_2</tex>:
! colspan="5"|Ключи сортированного блока
+
 
|-align="center"
+
{|
| 1||2||5||4||3
+
| ||
 +
{| class="wikitable" style="text-align:center"
 +
! colspan="6"|Сортированный
 +
|-
 +
| <tex>\pi</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
 +
|-
 +
| <tex>key</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>
 
|}
 
|}
{| class="wikitable" style="center"
+
| ||
! colspan="5"| <tex>\xi</tex>
+
{| class="wikitable" style="text-align:center"
|-align="center"
+
! colspan="6"|Второй блок
| 1||2||5||4||3
+
|-
 +
| <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>5</tex>
 +
|-
 +
| <tex>\xi_2</tex> ||<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>4</tex>||<tex>3</tex>
 
|}
 
|}
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
 
{| class="wikitable" style="center"
 
! colspan="5"| новые ключи
 
|-align="center"
 
| 1||2||8||6||5
 
 
|}
 
|}
Обновление старых ключей:
+
 
{| class="wikitable" style="center"
+
Обновляем ключи в очереди:
 +
{| class="wikitable" style="center" style="background: #ffffcc"
 +
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>key</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 3 ||  ||  || style="background: #77A9F4"| 3
+
| style="background:#FFC9C9"| <tex>3</tex> ||  ||  || style="background: #CFCFFF"| <tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || style="background:#FFCC00"| 4 ||  || style="background: #77A9F4"| 4
+
| <tex>3</tex> || style="background:#FFC9C9"| <tex>4</tex> ||  || style="background: #CFCFFF"| <tex>4</tex>
 
|-align="center"  
 
|-align="center"  
| 3 || 4 || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
+
| <tex>3</tex> || <tex>4</tex> || style="background:#FFC9C9"| <tex>7</tex> || style="background: #CFCFFF"| <tex>7</tex>
 
|}
 
|}
<tex>LIS</tex> новых:
+
 
{| class="wikitable" style="center"
+
запускаем <tex>\mathrm{LIS}</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>key</tex>||<tex>\pi</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 || 4 || 7 ||  || style="background: #77A9F4"| 1
+
| style="background:#FFC9C9"| <tex>1</tex> || <tex>4</tex> || <tex>7</tex> ||  || style="background: #CFCFFF"| <tex>1</tex> || style="background: #B9FFB9"| <tex>1</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 2 || 7 ||  || style="background: #77A9F4"| 2
+
| <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> || <tex>7</tex> ||  || style="background: #CFCFFF"| <tex>2</tex> || style="background: #B9FFB9"| <tex>2</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 7 || style="background:#FFCC00"| 8 || style="background: #77A9F4"| 8
+
| <tex>1</tex> || <tex>2</tex> || <tex>7</tex> || style="background:#FFC9C9"| <tex>8</tex> || style="background: #CFCFFF"| <tex>8</tex> || style="background: #B9FFB9"| <tex>12</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 6 || 8 || style="background: #77A9F4"| 6
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>6</tex> || <tex>8</tex> || style="background: #CFCFFF"| <tex>6</tex> || style="background: #B9FFB9"| <tex>6</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 5 || 8 || style="background: #77A9F4"| 5
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>5</tex> || <tex>8</tex> || style="background: #CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>5</tex>
 
|}
 
|}
''' Результат работы '''
+
 
 +
В результате получаем:
  
 
<tex>B: \{1, 2, 5, 8\}</tex>
 
<tex>B: \{1, 2, 5, 8\}</tex>
  
<tex>merged: \{1,2,3,4,5,6,8,12\}</tex>
+
<tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</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>B: \{1, 2, 5, 8\}</tex> из <tex>merged: \{1,2,3,4,5,6,8,12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
 
 
{|
 
{|
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="center"
! colspan="5"|Первый блок
 
 
|-align="center"
 
|-align="center"
|style="background:#FFB580"|7||style="background:#FF8B80"|11
+
| colspan="4"|<tex>B</tex>
 
|-align="center"
 
|-align="center"
|style="background:#FFC080"|1||style="background:#FF8080"|2
+
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>12</tex>
 
|}
 
|}
 
| ||
 
| ||
{| style="center"
+
{| class="wikitable" style="center"
! colspan="5"|Cортированный
 
 
|-align="center"
 
|-align="center"
|style="background:#FFB580"|7||style="background:#FF8B80"|11
+
| colspan="2"|<tex>C_3^s</tex>
 
|-align="center"
 
|-align="center"
|style="background:#FFC080"|1||style="background:#FF8080"|2
+
| <tex>7</tex>||<tex>11</tex>
 
|}
 
|}
 
|}
 
|}
Строка 389: Строка 401:
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="8"|<tex>merged</tex>
+
! colspan="7"|<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"
 
|-align="center"
| 1||2||5||7||11||12
+
|<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"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="4"|<tex>ind's\#0</tex> — индексы текущих
+
| colspan="4"|<tex>\mathtt{ind_1}</tex>
 
|-align="center"
 
|-align="center"
| 1||2||3||6
+
| <tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>6</tex>
 
|}
 
|}
 
| ||
 
| ||
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
 
|-align="center"
 
|-align="center"
| colspan="2"|<tex>ind's\#1</tex> — индексы новых
+
| colspan="2"|<tex>\mathtt{ind_0}</tex>
 
|-align="center"
 
|-align="center"
| 4||5
+
| <tex>4</tex>||<tex>5</tex>
 
|}
 
|}
 
|}
 
|}
{| class="wikitable" style="center"
+
 
! colspan="5"|Ключи сортированного блока
+
Получаем ключи элементов в <tex>C_3^s</tex> и находим перестановку ключей в порядке исходной последовательности, действуя перестановкой <tex>\xi_3</tex>:
|-align="center"
+
 
| 1||2
+
{|
 +
| ||
 +
{|
 +
| ||
 +
{| class="wikitable" style="text-align:center"
 +
! colspan="3"| Третий блок
 +
|-
 +
| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>
 +
|-
 +
| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>
 
|}
 
|}
{| class="wikitable" style="center"
+
| ||
! colspan="5"| <tex>\xi</tex>
+
{| class="wikitable" style="text-align:center"
|-align="center"
+
! colspan="3"|Cортированный
| 1||2
+
|-
 +
| <tex>\pi</tex> ||<tex>7</tex>||<tex>11</tex>
 +
|-
 +
| <tex>key</tex> ||<tex>4</tex>||<tex>5</tex>
 +
|-
 +
| <tex>\xi_3</tex> ||<tex>1</tex>||<tex>2</tex>
 
|}
 
|}
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
 
{| class="wikitable" style="center"
 
! colspan="2"| новые ключи
 
|-align="center"
 
| 4||5
 
 
|}
 
|}
 +
 
Обновление старых ключей:
 
Обновление старых ключей:
{| class="wikitable" style="center"
+
{| class="wikitable" style="center" style="background: #ffffcc"
 +
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>
 
|-align="center"  
 
|-align="center"  
| style="background:#FFCC00"| 1 || 4 || 7 ||  || style="background: #77A9F4"| 1
+
| style="background:#FFC9C9"| <tex>1</tex> ||   ||   ||  || style="background: #CFCFFF"| <tex>1</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || style="background:#FFCC00"| 2 || 7 ||  || style="background: #77A9F4"| 2
+
| <tex>1</tex> || style="background:#FFC9C9"| <tex>2</tex> ||   ||  || style="background: #CFCFFF"| <tex>2</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || style="background:#FFCC00"| 3 ||  || style="background: #77A9F4"| 3
+
| <tex>1</tex> || <tex>2</tex> || style="background:#FFC9C9"| <tex>3</tex> ||  || style="background: #CFCFFF"| <tex>3</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 3 || style="background:#FFCC00"| 6 || style="background: #77A9F4"| 6
+
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || style="background:#FFC9C9"| <tex>6</tex> || style="background: #CFCFFF"| <tex>6</tex>
 
|}
 
|}
<tex>LIS</tex> новых:
+
 
{| class="wikitable" style="center"
+
запускаем <tex>\mathrm{LIS}</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>B_5</tex>||<tex>key</tex>||<tex>\pi</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 3 || style="background:#FFCC00"| 4 ||  || style="background: #77A9F4"| 4
+
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || style="background:#FFC9C9"| <tex>4</tex> ||  || style="background: #CFCFFF"| <tex>4</tex> || style="background: #B9FFB9"| <tex>7</tex>
 
|-align="center"  
 
|-align="center"  
| 1 || 2 || 3 || 4 || style="background:#FFCC00"| 5 || style="background: #77A9F4"| 5
+
| <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || style="background:#FFC9C9"| <tex>5</tex> || style="background: #CFCFFF"| <tex>5</tex> || style="background: #B9FFB9"| <tex>11</tex>
 
|}
 
|}
''' Результат работы '''
+
Результат завершения алгоритма:
  
 
<tex>B: \{1, 2, 3, 4, 5\}</tex>
 
<tex>B: \{1, 2, 3, 4, 5\}</tex>
  
<tex>merged: \{1,2,5,7,11,12\}</tex>
+
<tex>\mathtt{merged}: \{1,2,5,7,11,12\}</tex>
  
===== Восстановление НВП =====
+
Получаем, что длина НВП — <tex>5</tex>, и НВП оканчивается на <tex>\mathtt{merged}[5]=11</tex>.
 +
 
 +
'''Восстановление НВП'''
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
! colspan="12"| <tex>predecessor</tex>
+
! colspan="12"| <tex>\mathtt{predecessor}</tex>
 
|-align="center"
 
|-align="center"
| 1||2||3||4||5||6||7||8||9||10||11||12
+
| style="background:#DCFFFF"|<tex>1</tex>||style="background:#DCDCFF"|<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>6</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8</tex>||<tex>9</tex>||<tex>10</tex>||style="background:#FFFFC8"|<tex>11</tex>||<tex>12</tex>
 
|-align="center"
 
|-align="center"
|  ||1|| ||3||2||2||5||4|| ||3||7||8  
+
|style="background:#FFFFC8"|  ||style="background:#DCFFFF"|<tex>1</tex>|| ||<tex>3</tex>||style="background:#DCDCFF"|<tex>2</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>4</tex>|| ||<tex>3</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8</tex>
 
|}
 
|}
Начинаем восстановление с <tex>merged[5] = 11</tex>:
+
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
 
{| class="wikitable" style="center"
 
{| class="wikitable" style="center"
|+ обратный порядок
+
|-align="center"
| 11||7||5||2||1
+
| обратный порядок||style="background:#FFFFC8"|<tex>11</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFFF"|<tex>1</tex>
|}
+
|-align="center"
{| class="wikitable" style="center"
+
| НВП||style="background:#DCFFFF"|<tex>1</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#FFFFC8"|<tex>11</tex>
|+ НВП
 
| 1||2||5||7||11
 
 
|}
 
|}
 +
 +
=== Нахождение размера блоков ===
 +
 +
Рассмотрим последовательность <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_{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>.
  
 
== См. также ==
 
== См. также ==
Строка 474: Строка 519:
  
 
== Источники информации ==
 
== Источники информации ==
* [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf {{---}} Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)] (07.01.2017)
+
* [http://www.bcs.org/upload/pdf/ewic_vs08_s2paper2.pdf Computing a Longest Increasing Subsequence of Length k in Time O(n log log k)] (07.01.2017)
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]
 +
[[Категория: Классические задачи динамического программирования]]

Текущая версия на 19:07, 4 сентября 2022

Задача:
Дана перестановка [math]\pi[/math] множества [math]~\{1, 2,~\dots,~n\}[/math]. Требуется найти НВП [math]\pi[/math] за [math]O(n\operatorname{log}\operatorname{log}k)[/math], где [math]k[/math] — длина НВП.


Task.jpg

Алгоритм за 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.

Пример

Типы операций

  • Добавление элемента, который больше всех предыдущих:

Operation1.jpg

  • Замещение элемента более подходящим, т.е. добавление немаксимального элемента:

Operation2 1.jpg [math]\longrightarrow[/math] Operation2 2.jpg

Пример последовательности

[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].

См. также

Источники информации