我们可以从线性时间的序列中排序订单是否可以获得任何尺寸$ \ ge \ lfloor \ frac {n} \ rfloor $。
-
29-09-2020 - |
题
给定序列 $ 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%不可能。但是,我不确定。任何人都可以表明不能存在这样的策略或证明否则?
解决方案
是不可能的(假设你只使用比较)。首先,我们使用索引增强所有元素: $ 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)$ ,它违反用于分类的众所周知的下限。 不隶属于 cs.stackexchange