선형 시간의 시퀀스에서 정렬 된 순서로 SIZE $ \ GE \ LFLOROR \ FRAC {n} {2} \ RFLOOR $의 서브 시퀀스를 얻을 수 있습니까?

Question

시퀀스 $ a $ $ n $ 별개의 정수가 있으며, 전략이 존재합니까?크기 $ \ geq \ lfloor \ floor {n} {2} \ rfloor $ 을 $ o (n) $ 시간?

예를 들어 $ a= [4, 11, 6, 2, 9, 7] $ 이라고 가정 해 봅시다.그런 다음 필요한 시퀀스 중 하나는 $ [2, 7, 11] $ 이 될 수 있습니다. 이는 subsis $ [11, 2, 7] $ .전략은 정렬 된 순서로 그러한 서브 시퀀스를 제공 할 수 있습니다.

예, 나는 그것이 99.99 % 불가능하다고 생각합니다.그러나 나는 확실히 모른다.누구든지 그러한 전략이 존재할 수 없거나 달리 증명할 수 없다는 것을 보여줄 수 있습니까?

Answer 1

불가능합니다 (비교 만 사용하는 것만 가정).첫째, 모든 요소를 인덱스로 보완합니다. $ a [i] \ to (a [i], i) $ .선형 시간으로 배열에서 시퀀스를 제거 할 때이 문제가 필요합니다.

다음 정렬 알고리즘을 고려하십시오 :

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

.

결과적으로 실행 시간은 $ o (n + \ frac n2 + \ frac n4 + ...)= O (n) $ ,정렬을위한 잘 알려지지 않은 하한.