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:
Cuando elegimos la mediana como elemento pivote, luego del algoritmo de partición, irá en el medio de la array con la mitad de los elementos a la izquierda y la otra mitad a la derecha.
Por lo tanto, después del algoritmo de partición, la array se dividirá en dos partes iguales de n/2 elementos cada una.
Por lo tanto, la relación de recurrencia resultante sería
: T(n) = O(n) (para seleccionar la mediana) + O(n) (para la partición) + T(n/2) + T(n/2)
T(n) = O(n) + 2T(n/2)
Podemos resolver la relación de recurrencia anterior usando el método maestro
Referencia:
https://en.wikipedia.org/wiki/Master_theorem
Igual que http://geeksquiz.com/algorithms-searching-and-sorting-question-3/
Esta solución es aportada por Parul Sharma.
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