¿Cuál de las siguientes es la ecuación de recurrencia para la complejidad temporal del peor de los casos del algoritmo Quicksort para clasificar n(≥ 2) números? En las ecuaciones de recurrencia dadas en las siguientes opciones, c es una constante.
(A) T(n) = 2T (n/2) + cn
(B) T(n) = T(n – 1) + T(0) + cn
(C) T(n) = 2T (n – 2 ) + cn
(D) T(n) = T(n/2) + cn
Respuesta: (B)
Explicación: En el peor de los casos, el pivote elegido siempre se coloca en una posición de esquina y se realiza una llamada recursiva para seguir.
a) para subarreglo a la izquierda del pivote que es de tamaño n-1 en el peor de los casos.
b) para subarreglo a la derecha del pivote que es de tamaño 0 en el peor de los casos.
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