Possiamo ottenere qualsiasi successiva di taglia $ \ ge \ lfloor \ frac {n} {2} \ rfloor $ in un ordine ordinato da una sequenza in tempo lineare?
-
29-09-2020 - |
Domanda
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?
Soluzione
È 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.