Podemos obter qualquer subsequence de tamanho de $\ge \lfloor \frac{n}{2} floor$ em uma ordem de classificação a partir de uma sequência linear de tempo?

Question

Dada uma seqüência de $A$ de $N$ distintos números inteiros, não existe uma estratégia para conseguir pelo menos um subsequence com tamanho $\geq \lfloor \frac{N}{2} floor$ a sequência em ordem classificada em $S(n)$ tempo?

Por exemplo, vamos dizer que $A = [4, 11, 6, 2, 9, 7]$.Em seguida, uma das sequências pode ser $[2, 7, 11]$, que é a versão classificada de subsequence $[11, 2, 7]$.A sua estratégia pode dar qualquer subsequence em uma ordem de classificação.

Sim, eu acho que é de 99,99% impossível.Mas, eu não sei ao certo.Alguém pode mostrar que não pode existir como uma estratégia ou provar o contrário?

Answer 1

É impossível (supondo que você só use comparações).Primeiro, temos que aumentar todos os elementos com os índices: $a[i] \a (a[i], i)$.Vamos precisar isso quando vamos remover a seqüência da matriz no tempo linear.

Considere o seguinte algoritmo de classificação:

def sort(a):
    subseq = get_sorted_subseq(a)  # Your function. Assume takes O(n) time
    b = a.exclude(subseq)          # Since we know indices, takes O(n) time
    return merge(subseq, sort(b)). # Takes O(n) time (see merge sort) + recursive call of size <= n/2

Em resultado, o tempo de execução é $S(n + \frac n2 + \frac n4 + ...) = O(n)$, o que viola um bem-conhecido limite inferior para a classificação.