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.

El número de clasificación n se da mediante la fórmula ^[1]${\estilo de visualización 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 ${\estilo de visualización n=1}$

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}$

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}$

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]