Considere el algoritmo Quicksort. Supongamos que existe un procedimiento para encontrar un elemento pivote que divide la lista en dos sublistas, cada una de las cuales contiene al menos una quinta parte de los elementos. Sea T(n) el número de comparaciones necesarias para clasificar n elementos. Entonces
(A) T(n) <= 2T(n/5) + n
(B) T(n) <= T(n/5) + T(4n/5) + n
(C) T(n) < = 2T(4n/5) + n
(D) T(n) <= 2T(n/2) + n
Respuesta: (B)
Explicación: Para el caso donde n/5 elementos están en un subconjunto, T(n/ 5) se necesitan comparaciones para el primer subconjunto con n/5 elementos, T(4n/5) es para el resto 4n/5 elementos, y n es para encontrar el pivote.
Si hay más de n/5 elementos en un conjunto, el otro conjunto tendrá menos de 4n/5 elementos y la complejidad del tiempo será menor que T(n/5) + T(4n/5) + n porque el árbol de recurrencia será más equilibrado.
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