Asymptotyczna złożoność czasowa wstawiania n elementów do binarnych stert zawierających już elementy n

Question

Załóżmy, że mamy binarną stertę n elementów i chcemy wstawić n więcej elementów (niekoniecznie jedna po drugiej). Jaki byłby całkowity czas wymagany na to?

Myślę, że to theta (n logn), ponieważ jedna wstawka przyjmuje logn.

Answer 1

Zakładając, że dane są:

• kolejek priorytetów realizowane za pomocą standardowego sterty binarnego H (realizowane w tablicy)
• n obecnej wielkości sterty

Mamy po wstawiania właściwości:

• w (n) = WorstCase (n) = Θ (log n) (Theta). -> W (n) = Ω (lg n) i W (n) = O (lg n)
• A (n) = Średnia wartość (n) = Θ (lg n) (Theta). -> W (n) = Ω (lg n) i W (n) = O (lg n)
• B (n) = BestCase (n) = Θ (1) (Theta). -> w (n) = Ω (1) oraz w (n) = O (1)

Tak na każdym przypadku mamy

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

WorstCase to moment, w którym wstawiamy nową minimalną wartość, więc up-heap musi podróżować w całym oddziale.

BestCase jest, gdy dla minimalnej sterty (sterty z minimalnym na wierzchu) wstawiamy wartość BIG (największy na zaktualizowanym odgałęzieniu) (więc up-heap zatrzymuje się natychmiast).

Prosisz o serii operacji n na stercie zawierającej już n elementów, to wielkość wzrośnie

from n to 2*n 

co asymptotycznie jest ...

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

Co upraszcza nasze równania. (Nie musimy się martwić wzrostem o n, ponieważ jego wzrost następuje według stałego współczynnika).

Mamy więc "dla n wstawkami" działania:

• XI (n) = X_for_n_insertions (N)
  • bezprzewodowy (n) = Θ (n lg n)
  • Ai (n) = Θ (n log n)
  • Bi (n) = Θ (n)
• to pociąga za "wszystkich przypadkach":
  • Ti (n) = Ω (n) i Tl (n) = O (n log n)

P.S. Aby wyświetlać symbole Theta Θ, Omega Ω, musisz mieć zainstalowany/być kompatybilny z UTF-8.

Answer 2

jej nie theeta (nlogn) ... jego zamówienie (nlogn), ponieważ niektóre z wstawkami może trwać mniej niż dokładnym czasie logN ... więc dla n wstawkami to zajmie czas < = nlogn

= > złożoność = o (nlogn)

Answer 3

podana: sterty n elementów i więcej elementów do wstawienia. Tak więc na koniec będzie 2 * n elementów. ponieważ stertę można utworzyć na 2 sposoby 1. Kolejne wstawianie i 2. Tworzenie metody stosu. W przypadku tej metody budowania stosu potrzeba czasu O (n) do zbudowania sterty, która jest wyjaśniona w How can building a heap be O(n) time complexity?. więc całkowity wymagany czas to O (2 * n), który jest taki sam jak O (n)