除了中位数算法,还有其他方法可以在最坏情况下以O(n)的时间进行k选择吗?实现中位数算法是否有意义?我的意思是,性能优势是否足够好,适用于实际目的?
std::nth_element
保证期望的时间复杂度是O(n)。因此,如果你使用C++,你可以轻松地运行一些测试,看看性能是否足够好来满足你的需求。这要看情况。如果你担心最坏情况会意外发生,那就不必费心了。随着数据越来越大,最坏情况变得如此不太可能,以至于不值得防范。
如果你在选择时处于客户端可能按最坏情况顺序提供数据以对你的服务器进行拒绝服务攻击的情况下,那么使用中位数算法来确保最坏情况不会对性能造成重大影响可能是值得的。
更新:
有一种线性时间算法,是快速排序的发明者Hoare本人提出的修改版。我建议参考CLRS书中的第9.3节“最坏情况下线性时间选择”。
以下是简要算法,假设我们有一个从快速排序中使用随机枢轴进行分区的方法random_partition
:
FindKth(array, l, u, k)
{
int m = random_partition(array, l, u);
if m == k : return array[k] /*we have found the kth element*/
if m > k: return FindKth(array, l, m-1, k); /* we have found element > kth largest, concentrate on the left partition */
else: return FindKth(array, m+1, u, k-m); /* find the k-m th element in the right partition */
}
您还可以参考Donald Knuth的TAOCP Vol.3 Sorting and Searching p.633 这种方法的美妙之处在于,数组不需要完全排序! 我认为STL nth_permutation使用了这种技术,您可以参考注释部分。