76
правок
Изменения
→Доказательство оптимальности
Докажем, что перед обработкой блока и после его обработки сохраняется инвариант, что очередь <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_jj}<\pi_{u_kk} \Longleftrightarrow \mathtt{key}(\pi_{u_jj})<\mathtt{key}(\pi_{u_kk}))</tex>, где <tex>\pi_{u_j},\pi_{u_k}\in \mathtt{merged}</tex>. Тогда , то справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов.
* Во время обработки ключей элементов алгоритм <tex>\mathtt{LIS}</tex> работает только с очередью <tex>B</tex> и не зависит от предыдущих элементов последовательности, ключи которых не находятся в очереди. Так как на каждой итерации алгоритма <tex>\mathrm{LIS}</tex> сохраняется выражение инварианта, что в очереди <tex>B</tex> хранятся наилучшие значения ключей элементов, которые соответствуют наилучшим элементам, для всех возможных длин возрастающих подпоследовательностей обработанной подпоследовательности, то в результате работы <tex>\mathrm{LIS}</tex> будет очередь <tex>B</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>.
