76
правок
Изменения
→Доказательство корректности алгоритма
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключами элементов <tex>\mathtt{elt}(x)</tex>.
===Доказательство корректности оптимальности ==={{Утверждение|statement=Пусть имеется последовательность <tex>S=\{\pi_1,~\dots,~\pi_n\}</tex>, разбитая на <tex>\lceil n/m \rceil</tex> блоков <tex>C_i</tex> длины <tex>m</tex>. В результате описанного выше алгоритмаполучается очередь <tex>B</tex>, размер которой равен длине НВП последовательности <tex>S</tex>.|proof=Докажем по индукции, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь <tex>B</tex> хранит ключи наилучших элементов для каждой длины возрастающих подпоследовательностей, входящих в уже обработанную последовательность элементов.* Пусть перед обработкой блока <tex>C_i</tex> в очереди <tex>B</tex> хранятся ключи наилучших элементов, вычисленные для подпоследовательности <tex>S_{(i-1)m}=\{\pi_1,~\dots,~\pi_{(i-1)m}\}</tex>.* После слияния элементов очереди <tex>B</tex> и блока <tex>C_i^s</tex> получаем отсортированный список <tex>\mathtt{merged}</tex>. Cопоставив ключи элементам в списке, как их позиции в нём, выполняется условие <tex>(\pi_{u_j}<\pi_{u_k} \Longleftrightarrow \mathtt{key}(\pi_{u_j})<\mathtt{key}(\pi_{u_k}))</tex>, где <tex>\pi_{u_j},\pi_{u_k}\in \mathtt{merged}</tex>. Тогда справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов.* Во время обработки ключей элементов алгоритм <tex>\mathtt{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, ключи которых не находятся в очереди. Так как на каждой итерации алгоритма <tex>\mathtt{LIS}</tex> сохраняется описанный инвариант для наилучших значений ключей элементов каждой длины возрастающих подпоследовательностей обработанной последовательности <tex>S_j</tex>, которые соответствуют ключам наилучших элементов <tex>S_j</tex>. то по завершению работы алгоритма <tex>\mathtt{LIS}</tex> на блоке <tex>C_i</tex> результатом его работы будет очередь, в которой хранятся ключи, соответствующие наилучшим элементам каждой длины возрастающих подпоследовательностей, входящих в <tex>S_{im}</tex>.* Таким образом, после обработки последнего блока, в очереди <tex>B</tex> будут храниться ключи наилучших элементов для каждой длины возрастающих подпоследовательностей последовательности <tex>S_n=S</tex>. Тогда последний элемент в очереди <tex>B</tex> соответствует наилучшему элементу длины НВП последовательности <tex>S</tex>, а так как в очереди <tex>B</tex> хранятся наилучшие элементы длин всех возрастающих подпоследовательностей <tex>S</tex>, то размер очереди <tex>B</tex> равен длине НВП последовательности <tex>S</tex>.}}
===Пример===
