Complejidad de tiempo asintótica de insertar n elementos en un montón binario que ya contiene n elementos

Question

Supongamos que tenemos un montón binario de n elementos y deseamos insertar n elementos más (no necesariamente uno después de otro). ¿Cuál sería el tiempo total requerido para esto?

Creo que es theta (n logn) ya que una inserción toma logn.

Answer 1

Suponiendo que se nos da: cola

• prioridad implementado por el montón binario estándar H (implementado en la matriz de)
• n tamaño actual del montón

Hemos siguiente inserción propiedades:

• W (n) = peor caso (n) = Θ (lg n) (Theta). -> W (n) = Ω (lg n) y W (n) = O (lg n)
• A (n) = AverageCase (n) = Θ (lg n) (Theta). -> W (n) = Ω (lg n) y W (n) = O (lg n)
• B (n) = BestCase (n) = Θ (1) (Theta). -> W (n) = Ω (1) y W (n) = O (1)

Así que para todos los casos, tenemos

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

peor caso es cuando, insertamos nuevo valor mínimo, por lo hasta-montón tiene que viajar rama conjunto.

BestCase es cuando, para el montón mínimo (montón con mínimo en la parte superior), insertamos el valor GRANDE (mayor en la rama actualizada) (por lo que el up-heap se detiene inmediatamente).

Ha pedido acerca serie de operaciones n en el montón que contiene n elementos ya, su tamaño crecerá

from n to 2*n 

lo asintóticamente es ...

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

Lo que simplifica nuestras ecuaciones. (No tenemos que preocuparnos por el crecimiento de n, ya que su crecimiento es constante).

Por lo tanto, tenemos "para n inserciones" de la operación:

• Xi (n) = X_for_n_insertions (n)
  • Wi (n) = Θ (n lg n)
  • Ai (n) = Θ (n lg n)
  • Bi (n) = Θ (n)
• que implica, para "todo caso":
  • Ti (n) = Ω (n) y Ti (n) = O (n lg n)

P.S. Para mostrar símbolos Theta Θ, Omega Ω, debe tener UTF-8 instalado/ser compatible.

Answer 2

no es theeta (nlogn) ... su orden (nlogn) ya que algunas de las inserciones puede tomar menos tiempo exacto logn ... por lo tanto, para n inserciones que tomará tiempo < = nlogn

= > complejidad de tiempo = O (nlogn)

Answer 3

dado: montón de n elementos yn más elementos para insertar. Entonces, al final habrá 2 * n elementos. ya que heap se puede crear de 2 formas 1. Inserción sucesiva y 2. Método de pila de compilación. Con este método de acumulación de acumulaciones, O (n) tarda en crear el montón que se explica en How can building a heap be O(n) time complexity?. el tiempo total requerido es O (2 * n) que es igual que O (n)