¿Existe una mejor complejidad que O (n log n) para ordenar?

El límite N * log (N) es realmente bastante obvio si lo miras desde una perspectiva de teoría de la información.

• El número de bits necesarios para describir el índice de un elemento en la matriz ordenada de tamaño N es proporcional a log (n)
• La única operación que usa para decidir a dónde va algo es una comparación, que proporciona 1 bit de información.
• Tienes que comparar todos los N elementos al menos una vez obviamente

Esto significa que debe crear N * log (N) bits de información de alguna manera para ordenar N elementos

Una comparación proporciona solo 1 bit de conocimiento, así que no importa lo que hagas, debes terminar haciendo N * log (N) comparaciones

Algunos tipos, como la clasificación de radix, parecen pasar por alto este límite, pero si observa con cuidado, debe haber múltiples pases, proporcionales al registro (N), de una clasificación de conteo para realizar una clasificación de radix.

Cuando haces una especie de radix de enteros de 32 bits usando 4 pasadas con un tamaño de palabras de 8 bits, explotas el hecho de que el circuito de memoria de la computadora puede hacer 8 comparaciones por ti internamente, cuando colocas un valor en la ubicación de 8 bits X, la RAM demultiplexa esos 8 bits internamente en una operación; si se representara como software, serían 8 operaciones.

Por lo tanto, incluso la clasificación de radix solo aparece como O (n) : desde una perspectiva más amplia, sigue siendo O (N * log (N))

Si está buscando algoritmos de clasificación de propósito general, entonces sí, O (n log n) es tan bueno como parece.

Pero si sabes algo sobre la entrada, puedes hacer trampa.

Por ejemplo, si sabe que el conjunto de datos de entrada solo contendrá potencias de dos entre 2 ^ 0 y 2 ^ 63 sin repeticiones, podría encontrar un algoritmo de clasificación que sea O (n).

P.ej. Utilice un entero de 64 bits como un mapa de bits que se pone a cero inicialmente; analiza la entrada y voltea los bits correspondientes a la posición de encendido en tu mapa de bits; luego itere sobre los bits en su mapa de bits para obtener la secuencia ordenada.

Cuanto más sepa acerca de sus datos y / o más suposiciones pueda hacer, más se adaptarán sus algoritmos de clasificación y búsqueda.

Para la ordenación de propósito general: O (n log n) es tan bueno como se pone.

Depende del dominio de los datos . Supongo que ordena la matriz y solo los algoritmos deterministas. Si el tamaño del dominio de datos es muy pequeño en comparación con el número de elementos, entonces se puede usar la ordenación de conteo, que tiene una complejidad mejor que O (N log N) donde N es el número de elementos en la matriz.

Si está hablando de la clasificación in situ, entonces lo mejor que puede hacer en términos de complejidad temporal es O (nlogn). Si el espacio no es un problema, puede hacerlo en el tiempo O (n) usando el conteo de clasificación, la clasificación de radix, etc.

Radix sort.

Complejidad: O (n * k), donde k es la longitud de la clave.

(Considerando que la longitud de las teclas es constante).