En matemáticas e informática, los números de clasificación son una secuencia de números introducida en 1950 por Hugo Steinhaus para el análisis de algoritmos de clasificación de comparación . Estos números indican el número del peor caso de comparaciones utilizadas tanto por la inserción binaria tipo y combinación de especie . Sin embargo, hay otros algoritmos que utilizan menos comparaciones.
Fórmula y ejemplos
La El número de clasificación viene dado por la fórmula [1]
dónde
La secuencia de números dada por esta fórmula (comenzando con ) es
La misma secuencia de números también se puede obtener de la relación de recurrencia [2]
Es un ejemplo de secuencia regular 2 . [2]
Asintóticamente , el valor de laEl número de clasificación fluctúa entre aproximadamente y dependiendo de la relación entre y la potencia más cercana de dos . [1]
Aplicación a la clasificación
En 1950, Hugo Steinhaus observó que estos números cuentan el número de comparaciones utilizadas por la ordenación por inserción binaria y conjetura (incorrectamente) que dan el número mínimo de comparaciones necesarias para ordenarelementos que utilizan cualquier tipo de comparación . La conjetura fue refutada en 1959 por LR Ford Jr. y Selmer M. Johnson , quienes encontraron un algoritmo de clasificación diferente, el tipo de fusión-inserción de Ford-Johnson , utilizando menos comparaciones. [1]
La misma secuencia de números de clasificación también proporciona el número de comparaciones en el peor de los casos utilizados por el ordenamiento combinado para ordenarartículos. [2]
Otras aplicaciones
Los números de clasificación (desplazados en una posición) también dan los tamaños de los superpatrones más cortos posibles para las permutaciones en capas . [3]
Referencias
- ^ a b c Ford, Lester R. Jr .; Johnson, Selmer M. (1959), "Un problema de torneo", American Mathematical Monthly , 66 : 387–389, doi : 10.2307 / 2308750 , MR 0103159
- ^ a b c Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de-secuencias regulares ", Informática teórica , 98 (2): 163-197, doi : 10.1016 / 0304-3975 (92) 90001-V , MR 1166363. Consulte el Ejemplo 28, pág. 192.
- ^ Albert, Michael ; Engen, Michael; Pantone, Jay; Vatter, Vincent (2018), "Permutaciones universales en capas", Electronic Journal of Combinatorics , 25 (3): P23: 1 – P23: 5