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

Question

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

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

Answer 1

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

Answer 2

При условии, что нам даны:

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

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

• W (n) = WorstCase (n) = Θ(LG N) (Тета).-> W (n) = Ω (lg n) и W (n) = O (lg n)
• A (n) = AverageCase (n) = Θ (lg n) (тета).-> W (n) = Ω (lg n) и W (n) = O (lg n)
• B (n) = BestCase (n) = Θ (1) (тета).-> W (n) = Ω (1) и W (n) = O (1)

Так что для в каждом случае мы имеем

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

WorstCase - это когда мы вставляем новое минимальное значение, поэтому восходящая куча должна перемещаться по всей ветви.

BestCase - это когда для минимальной кучи (куча с минимальной вершиной) мы вставляем значение BIG (наибольшее в обновленной ветке) (поэтому восходящая куча немедленно останавливается).

Выспросив о серии из 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)
• для «всех случаев» это означает:
  • Ti (n) = Ω (n) иTi (n) = O (n lg n)

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

Answer 3

это не theeta (nlogn) ... его порядок (nlogn), поскольку для некоторых вставок может потребоваться меньше точного времени входа в систему ... поэтому для n вставок это займет время <= nlogn </p>

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