选择算法
维基百科,自由的 encyclopedia
在计算机科学中,选择算法是一种在列表或数组中找到第k个最小数字的算法;这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种:最小、最大和中位数。已知存在O(n)(最坏情况下为线性时间)的选择算法,还有对于结构化数据可能有次线性的表现的算法;在极端的情况下,对于已排序数据是O(1)。选择是一些更复杂问题的子问题,如最近邻和最短路径问题。 许多选择算法是由排序算法推广而来,反之,一些排序算法可由反复应用选择算法推导出来。
此条目需要扩充。 (2017年4月13日) |
最简单的选择算法是通过遍历列表找到最小(或最大)的元素,在此过程中跟踪当前的最小(或最大)值。这种算法与选择排序有关。相反地,最困难的选择算法是寻找中位数,这必然需要n/2的空间。 事实上,一个专门的中位选择算法可用来构造一个一般选择算法,例如中位数的中位数(英语:Median of medians)。已知最好的选择算法是快速选择(quickselect),它与快速排序有关。和快速排序类似,它有渐进最佳的复杂度,但是最坏情况的复杂度较差。不过这可以通过调整基准(pivot)的选择来优化。