76
правок
Изменения
→Доказательство оптимальности
Пусть имеется последовательность <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>. Тогда справедливо утверждение, что любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов.
