Ejecución de una secuencia

En informática , una serie de secuencias es un rango no decreciente de la secuencia que no se puede extender. El número de series de una secuencia es el número de subsecuencias crecientes de la secuencia. Esta es una medida de preclasificación y, en particular, mide cuántas subsecuencias se deben fusionar para ordenar una secuencia.

Definición

Sea una secuencia de elementos de un conjunto totalmente ordenado . Una serie de es una secuencia máxima creciente . Es decir, y ^{[ aclaración necesaria ]} suponiendo que y existen. Por ejemplo, si es un número natural , la secuencia tiene las dos series y . ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ ${\displaystyle X}$ ${\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle }$ ${\displaystyle x_{i-1}>x_{i}}$ ${\displaystyle x_{j}>x_{j+1}}$ ${\displaystyle x_{i-1}}$ ${\displaystyle x_{j+1}}$ ${\displaystyle n}$ ${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$ ${\displaystyle \langle n+1,\dots ,2n\rangle }$ ${\displaystyle \langle 1,\dots ,n\rangle }$

Sea definida como el número de posiciones tales que y . Se define de manera equivalente como el número de ejecuciones de menos uno. Esta definición asegura que , es decir, si, y solo si, la secuencia está ordenada. Como otro ejemplo, y . ${\displaystyle {\mathtt {runs}}(X)}$ ${\displaystyle i}$ ${\displaystyle 1\leq i<n}$ ${\displaystyle x_{i+1}<x_{i}}$ ${\displaystyle X}$ ${\displaystyle {\mathtt {runs}}(\langle 1,2,\dots ,n\rangle )=0}$ ${\displaystyle {\mathtt {runs}}(X)=0}$ ${\displaystyle X}$ ${\displaystyle {\mathtt {runs}}(\langle n,n-1,\dots ,1\rangle )=n-1}$ ${\displaystyle {\mathtt {runs}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n}$

Ordenar secuencias con un número bajo de ejecuciones

La función es una medida de clasificación previa. La ordenación por combinación natural es óptima en cuanto a ejecuciones. Es decir, si se sabe que una secuencia tiene una cantidad baja de ejecuciones, se puede ordenar de manera eficiente utilizando la ordenación por combinación natural. ${\displaystyle {\mathtt {runs}}}$

Carreras largas

Una serie larga se define de manera similar a una serie, excepto que la secuencia puede ser no decreciente o no creciente. La cantidad de series largas no es una medida de preclasificación. Una secuencia con una cantidad pequeña de series largas se puede ordenar de manera eficiente invirtiendo primero las series decrecientes y luego utilizando una ordenación por combinación natural.

Referencias

• Powers, David MW; McMahon, Graham B. (1983). "Un compendio de programas prolog interesantes". Informe técnico 8313 del DCS (informe). Departamento de Ciencias de la Computación, Universidad de Nueva Gales del Sur.
• Mannila, H (1985). "Medidas de preclasificación y algoritmos de clasificación óptimos". IEEE Trans. Comput. (C-34): 318–325. doi :10.1109/TC.1985.5009382.