Classificando sequências "k-tonic"

Espero que alguém conheça isso, por isso não preciso ler a literatura ...

$x_1, \ldots, x_n$$n-1$$[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$$k$$k$$p_i =(i,x_i)$$k$

$k$$O( n \log k )$

Pergunta: Este resultado deve ser conhecido. Você conhece alguma referência apropriada?

Aqui está uma referência do algoritmo de classificação de Levcopoulos-Petersson, mas diferente um pouco mais antiga que a da resposta de Andreas:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adaptated for Presorted Files", WADS '89: Anais do Workshop sobre Algoritmos e Estruturas de Dados, Lecture Notes in Computer Science, 382, ​​Londres, Reino Unido: Springer-Verlag, pp. 499– 509, doi: 10.1007 / 3-540-51542-9_41.

$O(\sum\log k_i)$$k_i$$x_i$$k$$k_i$$k$$O(n\log k)$

Dê uma olhada

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017 .

Uma medida de desordem, de acordo com o artigo, são as Subseqüências Aleatórias Monotônicas (SMS, página 7 abaixo), que são mais do que você pediu.

O papel

"Classificando seqüências monótonas embaralhadas" por Christos Levcopoulos e Ola Petersson

http://www.springerlink.com/content/79551g82q1p856n1/

fornece um algoritmo com o tempo de execução ideal, que mede qual é o que você procura.

A seguir, analisei as redes de classificação para fazer o trabalho:

http://www.sciencedirect.com/science/article/pii/S074373150500136X .

Joel Seiferas