Comments 6
Упомянутые алгоритмы собрал по ссылке
Без затей смотрим на скопипащеный quicksort. Ага, имеем т.н. помойный вариант, характеризующийся требованиями по доп. памяти всегда O(N), а отнюдь не
O(log2(N))
Как такое могло произойти? Увы, такое случается сплошь и рядом.
Кстати, я не имею ничего против помойный быстрой сортировки, у неё есть достоинство - её легко может воспроизвести неопытный новичек, рискующий в честной реализации не справиться с границами, индексами и т.п. Как автор этой публикации, например.
данный массив преобразуется в двоичную кучу: занимает эта операция O(N*log2(N))
Операция построения двоичной кучи из неупорядоченного массива имеет оптимальную сложность O(N). Пример доказательства можно найти, в том числе, на хабре https://habr.com/ru/post/195832/
Хм, после Стивенса:
Сложнее определить время работы алгоритма. Чтобы построить исходную кучу, ему приходится прибавлять каждый элемент к растущей куче. Всякий раз он размещает его в конце дерева и просматривает структуру данных до самого верха, чтобы убедиться, что она является кучей. Поскольку дерево полностью бинарное, количество его уровней равно O(log N). Таким образом, передвижение элемента вверх по дереву может занять максимум O(log N) шагов. Алгоритм осуществляет шаг, при котором добавляется элемент и восстанавливается свойство кучи, N раз, поэтому общее время построения исходной кучи составит O(N log N).
Для завершения сортировки алгоритм удаляет каждый элемент из кучи, а затем восстанавливает ее свойства. Для этого он меняет местами последний элемент кучи и корневой узел, а затем передвигает новый корень вниз по дереву. Дерево имеет высоту O(log N) уровней, поэтому процесс может занять O(log N) времени. Алгоритм повторяет такой шаг N раз, отсюда общее количество нужных шагов — O(N log N).
Суммирование времени, необходимого для построения исходной кучи и окончания сортировки, дает следующее: O(N log N) + O(N log N) = O(N log N).
[Стивенс, Р., 2016. Алгоритмы. Разработка и применение. М.: Издательство "Э". - С. 148]
и Вирта:
[Вирт Н. АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ. М.Мир 1989 - С. 112]
как-то даже не возвращался к вопросу, спасибо за уточнение!
Соглашусь, что нужно было добавить "в худшем случае".
Худший случай тут не при чем. Существует несколько алгоритмов построения бинарной кучи. Способ, который вы описали в сообщении действительно работает за O(N log N). По сути мы наращиваем кучу: добавляем новый элемент в конец и выполняем для него процедуру sift_up (восстанавливаем кучу). На последнем шаге будет N/2 * log(N/2) сравнений, что уже ограничивает снизу сложность алгоритма.
Однако это не оптимальный способ, можно построить кучу быстрее за O(N). Так как массив эквивалентен бинарному дереву, нам нужно лишь сделать из этого дерева кучу. Вместо процедуры sift_up мы будем двигать элементы вниз с помощью процедуры sift_down, начиная с конца. Количество сравнений будет таково: N/2*0 + N/4*1 + ... + 1*log(N). Удивительно, но асимптотика суммы данного ряда будет линейной! Магия, да и только :)
Вот тут есть еще одно объяснение. Ну и не грех заглядывать на википедию, особенно английскую.
Срезали, принимается :)
В качестве развития темы: в общем-то, в питоновской heapq.heapify тоже заявлена O(N) ("linear time"). И судя по исходным кодам (поправьте если ошибаюсь), как раз обсуждаемый нами алгоритм (heapify хотя и использует функцию _sifup, сама _siftup внутри использует в конечном итоге _siftdown).
Думаю, что-то похожее сделали и в NumPy.
Алгоритмы сортировки NumPy (и танцы, и мемы)