76
правок
Изменения
→Доказательство оптимальности
Следует отметить, что полученный массив также образует возрастающую последовательность, на котором мы должны выполнять операции <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.
====Доказательство оптимальности===={{Утверждение|statement=Пусть <tex>S=\{\pi_1,\pi_2,~\dots,~\pi_n\}</tex> — входная перестановка. В результате описанного алгоритма размер массива <tex>B</tex> равен длине НВП последовательности <tex>S</tex> |proof=Докажем, что перед обработкой элемента последовательности сохраняется инвариант, что в массиве <tex>B</tex> хранятся наилучшие элементы для каждой возможной длины возрастающих подпоследовательностей обработанной последовательности* Пусть перед обработкой элемента <tex>\pi_i</tex> соблюдается описанный инвариант.* Если <tex>\pi_i</tex> больше каждого элемента <tex>B</tex>, вычисленного для последовательности <tex>S_{i-1}=\{\pi_1,\pi_2,~\dots,~\pi_{i-1}\}</tex>, то он не может обновить любой из наилучших элементов, вычисленных ранее. С <tex>\pi_i</tex> можно составить возрастающую последовательность длины <tex>l+1</tex>, где <tex>l</tex> — длина НВП последовательности <tex>S_{i-1}</tex>, добавив <tex>\pi_i</tex> в конец этой НВП. Значит, <tex>\pi_i</tex> — наилучший элемент длины <tex>l+1</tex>. По предположению, размер <tex>B</tex> равен длине НВП последовательности <tex>S_{i-1}</tex>, потому что в <tex>B</tex> хранятся наилучшие элементы всех возможных длин возрастающих подпоследовательностей <tex>S_{i-1}</tex>. Тогда, добавив в конец очереди <tex>B</tex> элемент <tex>\pi_i</tex>, инвариант будет сохраняться.* Иначе <tex>\pi_i</tex> будет наилучшим элементом для уже существующей длины. Заметим, что <tex>\pi_i</tex> может обновить только один элемент. В обратном случае, если <tex>\exists l_1,l_2\colon l_2>l_1</tex>, для которых <tex>\pi_i</tex> может быть наилучшим элементом, то существует такая подпоследовательность длины <tex>l_2</tex>, в которой <tex>\pi_i</tex> является наибольшим элементом, но из этой последовательности можно составить подпоследовательность длины <tex>l_1</tex>, в которой наибольший элемент меньше <tex>\pi_i</tex>, что противоречит предположению. Таким образом, <tex>\pi_i</tex> может обновить только наименьшее <tex>k\colon B_k > \pi_i</tex>. Тогда, заменив <tex>B_k</tex> элементом <tex>\pi_i</tex>, инвариант также будет сохраняться.* После завершения алгоритма, в очереди <tex>B</tex> будут храниться наилучшие элементы для всех возможных длин возрастающих подпоследовательностей последовательности <tex>S</tex>. Тогда размер <tex>B</tex> равен длине НВП последовательности <tex>S</tex>. }}
==== Пример ====
