Número de clasificación

En matemáticas e informática, los números de ordenación son una secuencia de números introducidos en 1950 por Hugo Steinhaus para el análisis de algoritmos de ordenación por comparación . Estos números dan el número de comparaciones en el peor de los casos que utilizan tanto la ordenación por inserción binaria como la ordenación por combinación . Sin embargo, existen otros algoritmos que utilizan menos comparaciones.

Fórmula y ejemplos

El número de clasificación n se da mediante la fórmula ^[1] ${\displaystyle n}$

${\displaystyle \displaystyle n\lceil \log _{2}n\rceil -2^{\lceil \log _{2}n\rceil }+1.}$

La secuencia de números dada por esta fórmula (comenzando con ) es ${\displaystyle n=1}$

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... (secuencia A001855 en la OEIS ).

La misma secuencia de números también se puede obtener a partir de la relación de recurrencia ^[2] ,

${\displaystyle A(n)=A{\bigl (}\lfloor n/2\rfloor {\bigr )}+A{\bigl (}\lceil n/2\rceil {\bigr )}+n-1}$.

Es un ejemplo de una secuencia 2-regular . ^[2]

Asintóticamente , el valor del número de clasificación n fluctúa aproximadamente entre y dependiendo de la relación entre y la potencia de dos más cercana . ^[1] ${\displaystyle n}$ ${\displaystyle n\log _{2}n-n}$ ${\displaystyle n\log _{2}n-0.915n,}$ ${\displaystyle n}$

Aplicación a la clasificación

En 1950, Hugo Steinhaus observó que estos números cuentan el número de comparaciones utilizadas por el ordenamiento por inserción binario y conjeturó (incorrectamente) que dan el número mínimo de comparaciones necesarias para ordenar elementos utilizando cualquier ordenamiento por comparación . La conjetura fue refutada en 1959 por LR Ford Jr. y Selmer M. Johnson , quienes encontraron un algoritmo de ordenamiento diferente, el ordenamiento por inserción y fusión de Ford–Johnson , que utiliza menos comparaciones. ^[1] ${\displaystyle n}$

La misma secuencia de números de ordenación también proporciona el número de comparaciones en el peor de los casos que utiliza la ordenación por combinación para ordenar elementos. ^[2] ${\displaystyle n}$

Otras aplicaciones

Los números de clasificación (desplazados una posición) también dan los tamaños de los superpatrones más cortos posibles para las permutaciones en capas . ^[3]

Referencias

1. Ford, Lester R. Jr. ; Johnson, Selmer M. (1959), "Un problema de torneo", American Mathematical Monthly , 66 (5): 387–389, doi :10.2307/2308750, JSTOR  2308750, MR  0103159
2. Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de secuencias -regulares", Theoretical Computer Science , 98 (2): 163–197, doi : 10.1016/0304-3975(92)90001-V , MR  1166363 ${\displaystyle k}$. Véase el ejemplo 28, pág. 192.
3. Albert, Michael ; Engen, Michael; Pantone, Jay; Vatter, Vincent (2018), "Permutaciones en capas universales", Electronic Journal of Combinatorics , 25 (3): P23:1–P23:5, arXiv : 1710.04240 , doi : 10.37236/7386 , S2CID  52100342