212
правок
Изменения
м
→Сложность
Во время построения последовательности куч <tex dpi = 120> O(N) </tex> раз выполняется вставка элемента. И потом ещё <tex dpi = 120> O(N) </tex> раз выполняется удаление элемента при процедуре получения отсортированного массива. Таким образом сложность плавной сортировки составляет <tex dpi = 120> O(N\log{N}) </tex>.
Однако если подать на вход плавной сортировке уже отсортированный массив , асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что во время процедуры получения последовательности куч мы всегда будем вставлять элемент, который больше остальных уже находящихся в последовательности. Поэтому восстановление свойства последовательности будет выполняться за <tex dpi = 120> O(1) </tex> (так как алгоритм только посмотрит на корень соседней кучи, а просеивание закончится сразу потому что новый элемент будет больше своих детей). Операция получения и удаления максимального элемента будет тоже выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге, так как алгоритм <tex dpi =120> O(N) </tex> раз вставляет, а потом и удаляет элементы, получается асимптотика <tex dpi = 120> O(N) </tex>.
===Достоинства===
