Possiamo ottenere qualsiasi successiva di taglia $ \ ge \ lfloor \ frac {n} {2} \ rfloor $ in un ordine ordinato da una sequenza in tempo lineare?

Question

Dato una sequenza $ A $ di $ N $ numeri interi distinti, esistono una strategia perOttieni almeno una successive con dimensioni $ \ geq \ lfloor \ frac {n} {2} \ rfloor $ della sequenza in ordine ordinato in $ o (n) $ tempo?

Ad esempio, diciamo che $ a= [4, 11, 6, 2, 9, 7] $ .Quindi, una delle sequenze richieste può essere $ [2, 7, 11] $ , che è la versione ordinata della successiva $ [11, 2, 7] $ .La tua strategia può fornire tali successive in un ordine ordinato.

Sì, penso che sia impossibile dal 99,99%.Ma, non lo so per certo.Qualcuno può dimostrare che non ci può esistere una tale strategia o dimostrare altrimenti?

Answer 1

È impossibile (supponendo che utilizzi solo i confronti).Innanzitutto, aumentiamo tutti gli elementi con indici: $ a [i] \ a (a [i], i) $ .Avremo bisogno di questo quando rimuoveremo la sequenza dall'array in tempo lineare.

Considera il seguente algoritmo di ordinamento:

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

.

In risultato, il tempo di esecuzione è $ o (n + \ frac n2 + \ frac n4 + ...)= o (n) $ , che violaUn limite inferiore noto per l'ordinamento.