Considere n elementos que están igualmente distribuidos en k pilas. En cada pila, sus elementos están dispuestos en orden ascendente (min está en la parte superior de cada pila y luego aumenta hacia abajo).
Dada una cola de tamaño n en la que tenemos que poner los n elementos en orden creciente. ¿Cuál será la complejidad temporal del algoritmo más conocido?
(A) O(n logk)
(B) O(nk)
(C) O(n 2 )
(D) O(k 2 )
Respuesta: (A)
Explicación:
En nlogk, se puede hacer creando un montón mínimo de tamaño k y agregando todos los elementos superiores de todas las pilas. Después de extraer el mínimo, agregue el siguiente elemento de la pila de la que obtuvimos nuestro primer mínimo.
Complejidad de tiempo = O(k) (para crear un montón de tamaño k) + (nk)log k (inserciones en el montón).
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA