57
правок
Изменения
→Сложность
== Сложность ==
Создадим массив [[стек|стеков]] для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем [[Целочисленный двоичный поиск|бинарный поиск]]. Соответственно, поиск самой левой стопки занимает <tex>O(\log</tex> <tex>p)</tex>, где p {{---}} количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает <tex>O(n \log n)</tex>. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма формирования стопок составляет <tex>O(n \log \log n)</tex>. Такая оценка основывается на структуре данных [[Дерево ван Эмде Боаса|Дерево ван Эмде Боаса]].
Для получения отстортированного массива используем [[Двоичная куча|бинарную кучу]]. На каждом шаге алгоритма необходимо извлечь из кучи стек с минимальной вершиной за <tex>O(\log</tex> <tex>p)</tex>, где p - количество стеков в куче. Снять вершину выбранного стека и вернуть его в кучу за <tex>O(\log</tex> <tex>p)</tex>. Получение отсортированного массива займёт <tex>O(n \log</tex> <tex>n)</tex> времени.
Получение наибольшей возрастающей подпоследовательности выполняется за <tex>O(n)</tex> по описанному выше алгоритму.
Таким образом, алгоритм сортировки требует <tex>O(n \log n)</tex> времени в худшем случае и <tex>O(n)</tex> дополнительной памяти при любом раскладе. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма сортировки составляет <tex>O(n \log \log n)</tex>. Такая оценка основывается на структуре данных [[Дерево ван Эмде Боаса|Дерево ван Эмде Боаса]].
== Псевдокод ==
