¿Cuál es la cota inferior de la ordenación basada en comparaciones?
Opciones
- O(n)
- O(n log n) (Opción correcta)
- O(log n)
- O(n²)
Respuesta
O(n log n)
Por qué
Una ordenación por comparación solo aprende sobre los datos comparando dos elementos ('¿es a < b?'). Se puede demostrar que, en el peor caso, cualquier algoritmo así necesita unas n log n comparaciones.
Así que merge sort, heapsort y Timsort (O(n log n)) ya son óptimos.
Las ordenaciones que no comparan, como counting sort o radix sort, pueden ser O(n) para ciertos tipos de claves (por ejemplo enteros pequeños).
Recuerda
Ordenar comparando no puede bajar de O(n log n).