Para la clasificación general (es decir, basada en la comparación), está comprobado que no podemos hacerlo mejor que O (n log n).
Ver: tipo de comparación
Si no necesita comparar elementos individuales para ordenarlos, puede hacerlo mejor. Por ejemplo, puede lograr la ordenación O (n) con la ordenación Contando si puede asignar cada elemento de su lista a los números naturales, y el rango es relativamente pequeño.
- ¿Se requiere un buen conocimiento de la estructura de datos y algoritmos para saltar a la codificación competitiva?
- ¿Cómo está negando este código todos los números en mi matriz?
- Cómo mantener una matriz, admitir inserción y asignación aleatorias, y consultar el kth elemento más grande en un intervalo dado
- ¿Existe alguna noción del algoritmo más eficiente posible para alguna tarea?
- Cómo implementar un algoritmo C4.5 usando MATLAB
Entonces, con información especial, puede lograr la ordenación lineal del tiempo. ¿Puedes hacer algo mejor que eso? Bueno, para saber si algo está ordenado, debe verificar al menos cada elemento, lo que lleva tiempo O (n), por lo que no.
Finalmente, si desea dejar de lado el tiempo de ejecución asintótico y centrarse en las optimizaciones de nivel inferior, entonces seguro: siempre se están realizando nuevas mejoras en los algoritmos existentes para conjuntos de datos muy especializados.
