¿Por qué es imposible tener un tipo de comparación mejor que el tiempo O (nlogn)?

Potencialmente podríamos ser “afortunados” de que las comparaciones que solicite sean en realidad a0

Pero el argumento es más sutil, construimos un oráculo que responderá las consultas de comparación de tal manera que empeore su vida. El oráculo no tiene una idea preconcebida de qué objeto es más grande o más bajo. Ella conoce la ley de la tricotomía, la ley de transitividad, y construye respuestas que requieren que hagas al menos 1g (n) comparaciones entre los objetos. (lg para indicar el registro a la base 2)

¿Cómo logra esto el oráculo? Siempre que se comparen dos números, considere el número de permutaciones posibles que pueden ser una solución para cada respuesta (¿Cuántos para MENOS y cuántos para MAYOR?). Y responda con la respuesta que asegura que el número de permutaciones que quedan para investigar es mayor. No necesitamos que Oracle vuelva “IGUAL” para que este mecanismo funcione.

¿Cuál es la ley de transitividad que le impide responder con una elección, y la respuesta es forzada? Esto no causa un problema, porque el número de permutaciones válidas en esta etapa ni siquiera se reducirá en 1. Por lo tanto, hacer esa pregunta era mala desde el punto de vista del algoritmo.

Dado que menor + mayor = M. Donde M es el número de permutaciones disponibles antes de esa comparación. Y digamos menor> mayor, entonces menor> M / 2. Entonces, nos damos cuenta después de cada comparación, Oracle puede asegurarse de que el número de permutación sea la mitad o más. Para asegurarse, que solo queda una permutación, uno tiene que hacer k comparaciones, de modo que [matemáticas] n! / 2 ^ k \ le 1 [/ matemáticas]

Lo que significa [matemáticas] k \ ge lg (n!) [/ ​​Matemáticas]. No hemos respondido a la pregunta ¿existen algoritmos de clasificación que puedan lograr este límite? Algunos se acercan mucho. Conocemos algoritmos para ordenar 5 números en 7 comparaciones, por ejemplo. [matemáticas] 5! = 120 [/ matemáticas]. y [matemáticas] 2 ^ 7 = 128 [/ matemáticas]. Pero si considera 13 números, pensaríamos que podemos clasificar 33 comparaciones porque: ¡13! = 6,22,70,20,800 <8,58,99,34,592 = 2 ^ 33. Lamentablemente no podemos. Hay una prueba de que requiere al menos 34 comparaciones para ordenar.

Por lo tanto, no se conoce un límite realmente fuerte en el número de comparaciones. Pero al menos sabemos [matemáticas] O (lg (n!)) = O (n lg (n)) [/ matemáticas] como el orden. Este es un límite asintóticamente apretado. Pero nuestra búsqueda del límite inferior exacto continúa.

http://en.wikipedia.org/wiki/Com …

La siguiente es una lista de no todos, sino importantes algos de clasificación.
1. Clasificación rápida (tiene fuertes relaciones con las estadísticas de pedidos)
2. Clasificación de montón (basado en el montón o estructura de datos de árbol casi completa)
3. Ordenación por inserción (según cómo clasifique sus “cartas”)
4. Combinar clasificación (basado en dividir y conquistar como quick_sort pero es una clasificación estable, es decir, conserva el orden de entrada de elementos iguales en la salida ordenada).
5. Orden de conteo (no es un orden de comparación a diferencia de todo lo anterior).

¿Es posible la complejidad lineal del tiempo con 1-4 algoritmos de clasificación de comparación?
tratemos de obtener esto de una manera lúcida …

Se puede encontrar fácilmente utilizando un árbol de decisión. El árbol de decisión no es más que un árbol binario en el que cada nodo interno es un par de elementos (a, b) y su hijo izquierdo lleva el resultado que (a <= b) y el hijo derecho lleva el resultado (a> b) y, por lo tanto, cada una de las hojas lleva una supuesta secuencia ordenada, es decir, si las condiciones desde la raíz hasta una hoja en particular son verdaderas, el orden de los elementos en la hoja es orden ordenado.

Ahora, digamos que tiene elementos ‘n’, ¡el orden de clasificación puede ser cualquiera de n! combinaciones y el número máximo de hojas posibles es 2 ^ h, donde ‘h’ es la altura del árbol de decisión.
¡norte! <= 2 ^ h (número posible de órdenes de clasificación <= total de hojas posibles)
Nota: en la figura; ¡norte! = 6; total de hojas posibles = 8
Ahora tomando registro en ambos lados;
n (log (n)) <= h
Por lo tanto, el límite inferior en ‘h’ es n (log (n)) ..!
Por lo tanto, para alcanzar una secuencia ordenada, es necesario hacer un mínimo de n (log (n)) comparaciones.

En cualquier algoritmo de clasificación de comparación, el número mínimo de comparaciones requeridas es log (n!). Pero de acuerdo con la aproximación de Stirling, sabemos que log (n!) Está en Ω (nlogn) y, por lo tanto, no podemos tener una comparación mejor que el tiempo Ω (nlogn).

Te puedo dirigir a la respuesta.
Consulte la conferencia

“1-05 Conferencia 05_ Clasificación en tiempo lineal_LowerBounds”
de la serie de conferencias “Introducción a los algoritmos (SMA 5503)” del curso abierto del MIT.

Él tiene alguna explicación.

Puede haber n! permutaciones Uno de los cuales será el arreglo ordenado. Necesitas buscarlo. Por lo tanto, necesita tiempo de registro (n!). Lo cual es nlogn de la aproximación de Stirling.

Es esencialmente lógica simple.

Digamos que necesitas ordenar N números

• Al menos debe examinar cada número; hay N de ellos
• Debe examinar, en el peor de los casos, cada dígito de cada número y, en el mejor de los casos, el registro (N) (el índice numérico de cada uno tiene proporcionales a los dígitos del registro (N)

Así N * log (N)

Otra forma de verlo es que el contenido de información de una secuencia (sin ningún contexto) es N * log (N) y tiene que procesar toda esa información para ordenarla.