Vea la respuesta de Pritam Kumar Paul para la prueba de por qué cualquier algoritmo de clasificación basado en comparación nunca puede ordenar una lista de números en menos de O (n log n).
Sin embargo, la clasificación en O (n log n) es posible con algunos algoritmos como la clasificación por radix [1] , la clasificación por recuento [2] y otros algoritmos de clasificación no basados en comparación [3] que solo tomarían un tiempo lineal, es decir, O (n) para ordenar una lista de n números.
¿Significa esto que la prueba es incorrecta? ¡Definitivamente no! Los algoritmos no basados en comparación solo aprovechan las estructuras y operaciones de datos más “poderosas” (que pueden depender también de la naturaleza de los datos de entrada) que las simples comparaciones. Es posible que estos algoritmos no sean prácticos para todo tipo de datos, pero cuando solo ordena listas de números simples, tiene algunas buenas opciones.
- Cómo encontrar la menor supercadena de 2 subcadenas
- Estoy obteniendo una precisión del 52% en los datos de mi celda, como el volumen, etc., que son valores extremadamente pequeños. He usado el árbol de decisión. ¿Cómo puedo mejorar?
- Para ubicarse dentro del top 3 en el próximo ICPC regional, ¿qué le sugeriría a un codificador de nivel medio que tenga suficiente conocimiento?
- Cómo habilitar la compresión gzip
- Cuando quitamos un borde de un árbol, parece obvio que nos quedan dos árboles, pero ¿cómo podríamos probar esto?
¿Pero podemos ir incluso más bajo que O (n)? No se conocen algoritmos de clasificación de propósito general que tengan complejidad sub-lineal . Por propósito general , quiero decir que deberían poder ordenar cualquier tipo de lista, sin ninguna suposición sobre el orden existente (como ordenar una lista “casi ordenada”), etc.
Una forma intuitiva de explicar este límite sería que, en el caso general, cualquier algoritmo de clasificación necesitaría al menos examinar todos los elementos de la lista, lo que a su vez resultaría en una complejidad O (n).
Por otro lado, se podría hacer un argumento similar en el sentido de que la búsqueda lineal (con complejidad O (n)) es óptima para buscar en una lista general desordenada.
[1] Clasificación de radix, estructuras de datos y algoritmos: clasificación de radix
[2] Tipo de conteo
[3] Algoritmos de clasificación no comparativos
