Algoritmos | Clasificación | Pregunta 13

El límite inferior más estricto en el número de comparaciones, en el peor de los casos, para la clasificación basada en comparaciones es del orden de
(A) N
(B) N^2
(C) NlogN
(D) N(logN)^2

Respuesta: (C)
Explicación: El número de comparaciones que requiere un algoritmo de ordenación por comparación aumenta en proporción a Nlog(N), donde N es el número de elementos a ordenar. Este límite es asintóticamente estrecho:

Dada una lista de números distintos (podemos suponer esto porque este es un análisis del peor de los casos), hay N permutaciones factoriales, exactamente una de las cuales es la lista en orden ordenado. El algoritmo de clasificación debe obtener suficiente información de las comparaciones para identificar las permutaciones correctas. Si el algoritmo siempre se completa después de un máximo de f(N) pasos, no puede distinguir más de 2^f(N) casos porque las claves son distintas y cada comparación tiene solo dos resultados posibles. Por lo tanto,

2^f(N) >= N! o equivalentemente f(N) >= log(N!).
Como log(N!) es Omega(NlogN), la respuesta es NlogN.
Para más detalles, lea aquí

Cuestionario de esta pregunta