No es posible ordenar más rápido que el tiempo Ω (nlogn) suponiendo que el algoritmo se base en hacer comparaciones de 2 vías. El argumento se basó en mostrar que cualquier clasificación basada en la comparación podría representarse como un árbol de decisión, el árbol de decisión debe tener al menos n! hojas, para distinguir entre las n! diferentes permutaciones en las cuales las claves podrían ingresarse, y por lo tanto su altura debe ser al menos lg (n!) ∈ Ω (nlgn).
Este límite inferior implica que si esperamos ordenar los números más rápido que en el tiempo O (nlogn), no podemos hacerlo haciendo solo comparaciones. Ahora, la cuestión de si es posible ordenar sin el uso de comparaciones. Responden que sí, pero solo bajo circunstancias muy restrictivas.
Ejemplo: orden de conteo
- Estoy tratando de incrementar un elemento de matriz de caracteres inicializado a cero pero no puedo, ¿por qué?
- ¿Qué tipo de algoritmo es efectivo (95-100%) para detectar hasta 15 dentro de una habitación?
- ¿Qué es el algoritmo SURF en el procesamiento de imágenes?
- ¿Cuál es la diferencia entre un algoritmo de autoaprendizaje y un algoritmo de IA?
- ¿O (log n) siempre implica base 2?
El ordenamiento de conteo supone que cada entrada es un número entero en el rango de 1 a k. El algoritmo se ordena en tiempo Θ (n + k). Si se sabe que k es Θ (n), entonces esto implica que el algoritmo de clasificación resultante es el tiempo Θ (n). Verifique el recuento para los detalles de implementación.
