Supongamos que tenemos un algoritmo de tiempo O(n) que encuentra la mediana de una array no ordenada.
Ahora considere una implementación de QuickSort donde primero encontramos la mediana usando el algoritmo anterior, luego usamos la mediana como pivote. ¿Cuál será la complejidad de tiempo en el peor de los casos de este QuickSort modificado?
(A) O(n^2 Logn)
(B) O(n^2)
(C) O(n Logn Logn)
(D) O(nLogn)
Respuesta: (D)
Explicación: si usamos la mediana como elemento pivote , luego, para cada iteración, toma O (n) tiempo encontrar la mediana de la función dada y cada vez que la array se divide en 2 subpartes.
por lo que la ecuación de recurrencia se convierte en.
T(n) = 2T(n/2) + O(n)
La recurrencia anterior se puede resolver utilizando el método maestro . Cae en el caso 2 del método maestro
que da como resultado una complejidad O (nlogn).
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