¡Entonces todos conocemos el límite inferior del árbol de comparación de en el peor de los casos de comparaciones realizadas por un algoritmo de clasificación de comparación (determinista). No se aplica a la clasificación de comparación aleatoria (si medimos las comparaciones esperadas para el peor de los casos). Por ejemplo, para n = 4 , el límite inferior determinista es de cinco comparaciones, pero un algoritmo aleatorio (permutar aleatoriamente la entrada y luego aplicar el orden de fusión) funciona mejor, teniendo 4 2 comparaciones en expectativa para todas las entradas.
El enlazado sin los límites máximos todavía se aplica en el caso aleatorio, por un argumento teórico de la información, y puede ajustarse ligeramente a k + 2 ( n ! - 2 k ) Esto se debe a que hay un algoritmo óptimo que permuta aleatoriamente la entrada y luego aplica un árbol de decisión (determinista), y el mejor árbol de decisión (si existe) es uno en el que todas las hojas están en dos niveles consecutivos.
¿Qué pasa si se sabe algo sobre los límites superiores de este problema? Para todos , el número aleatorio de comparaciones (en espera, para la entrada del peor de los casos, para el mejor algoritmo posible) siempre es estrictamente mejor que el mejor algoritmo determinista (esencialmente, porque n ! Nunca es una potencia de dos) . Pero cuanto mejor?
fuente
Respuestas:
Ya que su pregunta es: "¿Qué se sabe?" Aquí hay algo:
http://arxiv.org/abs/1307.3033
fuente