Supongamos que hay ⌈ log n ⌉ listas ordenadas de ⌊ n/log n ⌋ elementos cada una. La complejidad temporal de producir una lista ordenada de todos estos elementos es:
(Sugerencia: use una estructura de datos de pila)
(A) O (n log log n)
(B) θ (n log n)
(C) Ω (n log n) )
(D) Ω(n3/2)
Respuesta: (A)
Explicación: Podemos fusionar arrays x de cada tamaño y en un tiempo O(xy*Logy) usando Min Heap.
x = Iniciar sesión
y = n/ Iniciar sesión
Obtenemos O(n/Logn * Logn * Log Log n) que es O(nLogLogn)
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