Ordenar por comparación
| n | log log 2 (n ! ) {{\displaystyle \left\lceil \ log _ {2} (n!) \right \ rceil}
|
Mínimo |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 1 |
| 3 | 3 | 3 |
| 4 | 5 | 5 |
| 5 | 7 | 7 |
| 6 | 10 | 10 |
| 7 | 13 | 13 |
| 8 | 16 | 16 |
| 9 | 19 | 19 |
| 10 | 22 | 22 |
| 11 | 26 | 26 |
| 12 | 29 | 30 |
| 13 | 33 | 34 |
| 14 | 37 | 38 |
| 15 | 41 | 42 |
| 16 | 45 | 45 o 46 |
| 17 | 49 | 49 o 50 |
| 18 | 53 | 53 o 54 |
| 19 | 57 | 58 |
| 20 | 62 | 62 |
| 21 | 66 | 66 |
| 22 | 70 | 71 |
| n | ⌈ log 2 ( n ! ) {{\displaystyle \left\lceil \ log _ {2} (n!) \right \ rceil}
|
n log 2 n − n ln 2 {\displaystyle n\log _{2}n{\frac {n}{\ln 2}}}
 |
| 10 | 22 | 19 |
| 100 | 525 | 521 |
| 1 000 | 8 530 | 8 524 |
| 10 000 | 118 459 | 118 451 |
| 100 000 | 1 516 705 | 1 516 695 |
| 1 000 000 | 18 488 885 | 18 488 874 |
al número mínimo real de comparaciones (de OEIS: A036604) necesarias para ordenar una lista de n elementos (en el peor de los casos). A continuación: Utilizando la aproximación de Stirling, este límite inferior es bien aproximada por n log 2 n − n ln 2 {\displaystyle n\log _{2}n{\frac {n}{\ln 2}}}
.
El número de comparaciones que una comparación algoritmo de ordenación requiere aumenta en proporción a n log ( n ) {\displaystyle n\log(n)}
, donde n {\displaystyle n}
es el número de elementos a ordenar. Este lazo es asintóticamente apretado.
Dada una lista de números distintos (podemos suponer esto porque este es un análisis del peor de los casos), hay n permutaciones factoriales exactamente una de las cuales es la lista en orden ordenado. El algoritmo de clasificación debe obtener suficiente información de las comparaciones para identificar la permutación correcta. Si el algoritmo siempre se completa después de como máximo los pasos f(n), no puede distinguir más de 2f(n) casos porque las claves son distintas y cada comparación tiene solo dos resultados posibles. Por lo tanto,
2 f ( n ) ≥ n ! {\displaystyle 2^{f (n)}\geq n!}
, o equivalente f (n ) ≥ log 2 (n ! ) . {\displaystyle f(n)\geq \log _{2}(n!).}
Por mirar los primeros n / 2 {\displaystyle n/2}
factores de n ! = n (n − 1) {1 {\displaystyle n!= n (n-1)\cdots 1}
, obtenemos log 2 ( n ! ) ≥ log 2 ( ( n 2 ) n 2 ) = n 2 log n log 2 − n 2 = Θ ( n log n ) . {\displaystyle \log _{2} (n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}
log 2 (n ! ) = Ω ( n log n). {\displaystyle \log _{2} (n!) = \Omega (n \ log n).}
Esto proporciona la parte inferior de la reclamación. Se puede dar un mejor límite a través de la aproximación de Stirling.
Un límite superior idéntico se desprende de la existencia de los algoritmos que alcanzan este límite en el peor de los casos, como heapsort y mergesort.
El argumento anterior proporciona un límite inferior absoluto, en lugar de solo asintótico, en el número de comparaciones, a saber log log 2 (n ! ) {{\displaystyle \left\lceil \ log _ {2} (n!) \ right \ rceil }
comparaciones. Este límite inferior es bastante bueno (se puede abordar dentro de una tolerancia lineal mediante un simple tipo de fusión), pero se sabe que es inexacto. Por ejemplo, log log 2 (¡13 ! )⌉ = 33 {\displaystyle \left\lceil \log _{2} (13!) \ right \ rceil =33}
, pero se ha demostrado que el número mínimo de comparaciones para clasificar 13 elementos es de 34.
Determinar el número exacto de comparaciones necesarias para ordenar un número determinado de entradas es un problema computacionalmente difícil, incluso para n pequeñas, y no se conoce una fórmula simple para la solución. Para algunos de los pocos valores concretos que se han calculado, véase OEIS: A036604.
Límite inferior para el número medio de comparacioneseditar
Un límite similar se aplica al número medio de comparaciones. Suponiendo que
- todas las claves son distintas, es decir, cada comparación dará a > b o a< b, y
- la entrada es una permutación aleatoria, elegida uniformemente del conjunto de todas las permutaciones posibles de n elementos,
es imposible determinar en qué orden se encuentra la entrada con menos de log2 (¡n!) comparaciones en promedio.
Esto se puede ver más fácilmente usando conceptos de la teoría de la información. La entropía de Shannon de una permutación aleatoria es log2(n!) trozo. Dado que una comparación solo puede dar dos resultados, la cantidad máxima de información que proporciona es de 1 bit. Por lo tanto, después de las comparaciones k, la entropía restante de la permutación, dados los resultados de esas comparaciones, es al menos log2 (¡n!)- k bits en promedio. Para realizar la ordenación, se necesita información completa, por lo que la entropía restante debe ser 0. De ello se deduce que k debe ser al menos log2 (¡n!) en promedio.
El límite inferior derivado a través de la teoría de la información se expresa como “límite inferior teórico de la información”. El límite inferior teórico de la información es correcto, pero no es necesariamente el límite inferior más fuerte. Y en algunos casos, el límite inferior teórico de la información de un problema puede incluso estar lejos del verdadero límite inferior. Por ejemplo, el límite inferior teórico de la información de la selección es log log 2 (n) {{\displaystyle \left\lceil \ log _ {2} (n)\right \ rceil }
mientras que n − 1 {\displaystyle n-1}
las comparaciones son necesarias para un argumento contradictorio. La interacción entre el límite inferior de la teoría de la información y el límite inferior verdadero es muy similar a una función de valor real que limita el límite inferior de una función entera. Sin embargo, esto no es exactamente correcto cuando se considera el caso promedio.
Para desenterrar lo que sucede al analizar el caso promedio, la clave es a qué se refiere “promedio”? ¿Promediando sobre qué? Con cierto conocimiento de la teoría de la información, los promedios de límite inferior de la teoría de la información sobre el conjunto de todas las permutaciones en su conjunto. Pero cualquier algoritmo informático (bajo lo que se cree actualmente) debe tratar cada permutación como una instancia individual del problema. Por lo tanto, el límite inferior promedio que estamos buscando se promedia en todos los casos individuales.
Para buscar el límite inferior relacionado con la no realizabilidad de las computadoras, adoptamos el modelo de árbol de decisiones. Reformulemos un poco nuestro objetivo. En el modelo de árbol de decisión, el límite inferior que se mostrará es el límite inferior de la longitud media de los caminos de raíz a hoja de un n ! {\displaystyle n!}
– árbol binario de hojas (en el que cada hoja corresponde a una permutación). Estaría convencido de que un árbol binario completo equilibrado alcanza el mínimo de la longitud media. Con algunos cálculos cuidadosos, para un árbol binario completo equilibrado con n ! {\displaystyle n!}
hojas, la longitud media de los caminos de raíz a hoja viene dada por (2 n ! – 2 log log 2 n ! ⌋ + 1) ⋅ log log 2 n ! ⌉ + (2 log log 2 n ! + + 1-n ! ) ⋅ log log 2 n ! n n ! {\displaystyle {\frac {(2n!-2^{\lfloor \ log _ {2}n!\rfloor + 1}) \ cdot \lceil \ log _ {2} n!\rceil +(2^{\lfloor \ log _ {2}n!\rfloor + 1} – n!) \ cdot \lfloor \ log _ {2} n!\ rfloor} {n!}}}
Por ejemplo, para n = 3, el límite inferior teórico de la información para el caso promedio es aproximadamente 2,58, mientras que el límite inferior promedio derivado a través del modelo de árbol de Decisión es 8/3, aproximadamente 2,67.
En el caso de que varios elementos puedan tener la misma clave, no hay una interpretación estadística obvia para el término “caso promedio”, por lo que un argumento como el anterior no se puede aplicar sin hacer suposiciones específicas sobre la distribución de claves.
