Espero que alguien sepa algo sobre esto, así que no tengo que leer la literatura ...
Considere una secuencia de números . Piense en la secuencia como n - 1 intervalos [ x 1 , x 2 ] , [ x 2 , x 3 ] , … , [ x n - 1 , x n ] . Claramente, la secuencia original es bitónica si algún punto en la línea real apuñala en la mayoría de los 2 intervalos. Nos referiremos a una secuencia donde un punto apuñala en la mayoría de los intervalos k como k-idiótico . Visualmente, si dibuja la gráfica de la secuencia (es decir, conecta los puntos en orden), lo anterior corresponde a la condición de que ninguna línea horizontal intersecte la gráfica más de k veces.
No es demasiado difícil (pero tampoco demasiado fácil) ver que las secuencias -idióticas se pueden clasificar en el tiempo O ( n log k ) , que es claramente óptimo.
Pregunta: Este resultado debe ser conocido. ¿Conoces alguna referencia apropiada?
fuente
Echa un vistazo a
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017 .
Una medida de desorden según el documento son las Subsecuencias Monótonas Barajadas (SMS, página 7 abajo) que es más de lo que solicitó.
El papel
"Clasificación de secuencias monótonas mezcladas" por Christos Levcopoulos y Ola Petersson
http://www.springerlink.com/content/79551g82q1p856n1/
da un algoritmo con el tiempo de ejecución óptimo wrt esa medida que es lo que buscas.
fuente
A continuación, analicé la clasificación de redes para hacer el trabajo:
http://www.sciencedirect.com/science/article/pii/S074373150500136X .
Joel Seiferas
fuente