Асимптотическая временная сложность вставки n элементов в двоичную кучу, уже содержащую n элементов

Предположим, у нас есть двоичная куча из n элементов и мы хотим вставить еще n элементов (не обязательно один за другим). Какое общее время потребуется для этого?

Я думаю, что это тета (n logn), так как одна вставка занимает logn.


algorithm data-structures binary-heap asymptotic-complexity
person Community    schedule 04.11.2011    source источник
comment
Я думаю, что размер существующей кучи должен как-то войти в результат.   -  person Kerrek SB    schedule 04.11.2011

Ответы (3)


arrow_upward
4
arrow_downward

Предположим, что нам дано:

  • очередь с приоритетом, реализованная стандартной двоичной кучей H (реализованная в массиве)
  • n текущий размер кучи

У нас есть следующие свойства insert:

  • W(n) = наихудший случай(n) = Θ(lg n) (тета). -> W(n)=Ω(lgn) и W(n)=O(lgn)
  • A(n) = AverageCase(n) = Θ(lg n) (тета). -> W(n)=Ω(lgn) и W(n)=O(lgn)
  • B(n) = BestCase(n) = Θ(1) (тета). -> W(n)=Ω(1) и W(n)=O(1)

Таким образом, для каждого случая у нас есть

  • T(n) = Ω(1) и T(n) = O(lg n)

В худшем случае мы вставляем новое минимальное значение, поэтому up-heap должен пройти всю ветвь.

BestCase — это когда для минимальной кучи (куча с минимальной вершиной) мы вставляем БОЛЬШОЕ (самое большое на обновленной ветке) значение (поэтому ап-куча немедленно останавливается).

Вы спрашивали о серии из n операций над кучей, содержащей уже n элементов, ее размер будет расти

from n to 2*n

что такое асимптотически...

n=Θ(n)
2*n=Θ(n)

Что упрощает наши уравнения. (Нам не нужно беспокоиться о росте n , так как он растет на постоянный коэффициент).

Итак, имеем операцию «для n вставок»:

  • Xi(n) = X_for_n_insertions(n)
    • Wi(n) = Θ(n lg n)
    • Ai(n) = Θ(n lg n)
    • Bi(n) = Θ(n)
  • it implies, for "all case":
    • Ti(n) = Ω(n) and Ti(n) = O(n lg n)

P.S. Для отображения символов Theta Θ , Omega Ω у вас должна быть установлена/совместима UTF-8.

person Grzegorz Wierzowiecki    schedule 09.01.2012

arrow_upward
6
arrow_downward

задано: куча из n элементов и еще n элементов, которые нужно вставить. Таким образом, в конце будет 2 * n элементов. поскольку куча может быть создана двумя способами: 1. Последовательная вставка и 2. Метод построения кучи. Среди этих методов сборки кучи требуется O (n) времени для создания кучи, что объясняется в Как построить кучу может быть O ( n) временная сложность?. поэтому общее требуемое время составляет O (2 * n), что совпадает с O (n)

person Hegde    schedule 23.01.2013

arrow_upward
1
arrow_downward

это не theeta(nlogn)... его порядок(nlogn), так как некоторые из вставок могут занять меньше точного времени logn... поэтому для n вставок потребуется время ‹=nlogn

=> временная сложность=O(nlogn)

person shahbaz    schedule 28.12.2011