Hay n arreglos sin clasificar: A 1 , A 2 , ….,A n . Suponga que n es impar. Cada uno de A 1 , A 2 , …., A n contiene n elementos distintos. No hay elementos comunes entre dos arreglos. La complejidad temporal en el peor de los casos de calcular la mediana de las medianas de A 1 , A 2 , ….,A n es ________ .
(A) Ο(n log n)
(B) Ο(n 2 )
(C) Ο(n)
(D) Ω(n 2 log n)
Respuesta: (B)
Explicación: dado que los arreglos dados no están ordenados, entonces la complejidad del tiempo para encontrar la mediana es O(n) en una array desordenada . Debe aplicar este agoritmo n tiempo para encontrar todas las medianas y nuevamente una vez para encontrar la mediana de todas estas medianas, por lo que la complejidad del tiempo total es,
= O(n)*O(n) + O(n) = O(n2) + O(n) ≈ O(n2)
Entonces, la opción (B) es correcta.
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