Фон
Согласно Википедии и другим источникам, которые я нашел, создание двоичной кучи n элементов, начиная с пустой двоичной кучи и вставляя в нее элементы n, составляют O (n log n), поскольку вставка двоичной кучи выполняется за O (log n), и вы делаете это n раз. Назовем это алгоритмом вставки.
Он также представляет альтернативный подход, в котором вы опускаете / просачиваете / просачиваете вниз / каскадируете / накапливаете вниз / пузыри вниз первую / верхнюю половину элементов, начиная со среднего элемента и заканчивая первым элементом, и что это O (n), гораздо лучшая сложность. Доказательство этой сложности основывается на понимании того, что сложность приемника для каждого элемента зависит от его высоты в двоичной куче: если он находится внизу, он будет маленьким, возможно, нулевым; если он рядом с верхом, он может быть большим, может быть, n. Дело в том, что сложность не log n для каждого элемента, погруженного в этот процесс, поэтому общая сложность намного меньше, чем O (n log n < / em>), и на самом деле это O (n). Назовем это алгоритмом стока.
Вопрос
Почему по тем же причинам сложность алгоритма вставки не такая же, как у алгоритма приемника?
Рассмотрим фактическую работу, проделанную для первых нескольких элементов в алгоритме вставки. Стоимость первой вставки не log n, она равна нулю, потому что двоичная куча пуста! Стоимость второй вставки в худшем случае равна одному свопу, а стоимость четвертого - в худшем случае двум свопам и так далее. Фактическая сложность вставки элемента зависит от текущей глубины двоичной кучи, поэтому сложность для большинства вставок меньше O (log n). Стоимость вставки даже технически не достигает O (log n) до тех пор, пока после не будут вставлены все n элементов [это O (log (< em> n - 1)) для последнего элемента]!
Эта экономия звучит так же, как экономия, полученная алгоритмом приемника, так почему же они не учитываются одинаково для обоих алгоритмов?
