Lowed obligado a clasificar por comparación

Question

Hoy estaba leyendo un excelente artículo de Julienne Walker sobre la clasificación - Eternally Confuzzled - The Art of Sorting y una cosa me llamó la atención. Yo no entiendo muy bien la parte donde el autor demuestra que para la clasificación por comparación estamos limitados por Ω ( N · log N ) límite inferior

Inferior límites no son tan evidentes. El límite más bajo posible para la mayoría de los algoritmos de clasificación es Ω (N · log N). Esto se debe a que la mayoría de los algoritmos de clasificación usan comparaciones de elementos para determinar el orden relativo de los artículos. Cualquier algoritmo que ordene en comparación tendrá un límite inferior mínimo de Ω (N · log N) porque se usa un árbol de comparación para seleccionar una permutación que se haya ordenado. Un árbol de comparación para los tres números 1, 2 y 3 pueden ser fácilmente construidos:

      1 < 2 

      1 < 3      1 < 3 

    2 < 3   3,1,2  2,1,3   2 < 3 

1,2,3 1,3,2       2,3,1  3,2,1 

Aviso cómo cada elemento se compara con todos los demás elementos, y que cada trayectoria de resultados en una permutación válido de los tres puntos. La altura del árbol determina el límite inferior del algoritmo de clasificación. Porque debe haber tantas hojas, ya que hay permutaciones para el algoritmo que es correcta, la menor altura posible del árbol de comparación es log N!, lo que equivale a Ω (N · log N) .

parece ser una muy razonable hasta que la última parte (en negrita) que yo no entiendo muy bien - como log N ! es equivalente a Ω (N · log N). Debo perder algo de mis cursos de CopmSci y no puedo obtener la última transición. Estoy esperando ayuda con esto o por algún enlace a otra evidencia de que estamos limitados Ω (N · log N) si utilizamos la clasificación por comparación.

Answer 1

No te perdiste nada de la clase CompSci. Lo que te perdiste fue la clase de matemáticas. ¡La página de Wikipedia para la Aproximación de Stirling muestra que log n! es asintóticamente n log n + términos de orden inferior.

Answer 2

• N! < N^N
• ∴ log N! < log (N^N)
• ∴ log N! < N * log N

Con esto, puede probar θ (log N!) = O (N log N). Probar lo mismo para Ω se deja como un ejercicio para el lector, o una pregunta para mathematics stackexchange o theoretical computer science stackexchange.

Answer 3

Mi prueba favorita de esto es muy elemental.

N! = 1 * 2 * .. * N - 1 * N

Podemos hacer un límite inferior muy fácil al pretender que la primera mitad de esos productos no existe, y que la segunda mitad es solo N/2 .

(N/2)^(N/2) < = N!

log ((N/2)^(N/2) = N log/2 * (N/2) = N/2 * (log (N) - 1) = O (n log n)

Entonces, incluso cuando solo toma la segunda mitad de la expresión, y pretende que todos esos factores no son mayores que N/2, todavía está en el territorio O (n log n) para un límite inferior, y esto es súper elemental .Podría convencer a un estudiante promedio de secundaria de esto. No puedo derivar la fórmula de Stirling solo.