Можем ли мы получить любую подпоследовательность размера $ \ ge \ lfloor \ frac {n} {2} \ Rfloor $ в отсортированном порядке из последовательности в линейном времени?

Question

Учитывая последовательность $ a $ $ n $ Отличные целые числа, существует ли стратегияПолучите хотя бы одну подпоследовательность с размером $ \ geq \ lfloor \ frac {n} {2} \ Rfloor $ последовательности в отсортированном порядке в $ o (n) $ time?

Например, скажем, что $ a= [4, 11, 6, 2, 9, 7] $ .Затем одна из необходимых последовательностей может быть $ [2, 7, 11] $ , что является отсортированной версией подпоследовательности $ [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) $ , который нарушаетхорошо известная нижняя оценка для сортировки.