76
правок
Изменения
→Доказательство оптимальности
|proof=
Докажем, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь <tex>B</tex> хранит ключи наилучших элементов для всех возможных длин возрастающих подпоследовательностей обработанной последовательности элементов.
* Пусть перед обработкой блока <tex>C_i</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>. Сопоставив ключи элементам в списке, как их позиции в нём, будет выполняться условие <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>\mathttmathrm{LIS}</tex> сохраняется описанный инвариант для наилучших значений ключей элементов каждой длины возрастающих подпоследовательностей обработанной последовательности выражение инварианта, что в очереди <tex>S_jB</tex>хранятся наилучшие значения ключей элементов, которые соответствуют ключам наилучших элементов <tex>S_j</tex>наилучшим элементам, для всех возможных длин возрастающих подпоследовательностей обработанной подпоследовательности, то, по завершению в результате работы алгоритма <tex>\mathttmathrm{LIS}</tex> на блоке будет очередь <tex>C_iB</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>.
}}
