我们可以从线性时间的序列中排序订单是否可以获得任何尺寸$ \ ge \ lfloor \ frac {n} \ rfloor $。

Question

给定序列 $ a $ $ n $ distinct整数，是否存在策略在 $ \ ge \ lfloor \ frac {n} \ rfloor $ 。-Container“> $ O（n）$ 时间？

例如，假设<跨度类=“math-container”> $ 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）$ ，它违反用于分类的众所周知的下限。