雅乐网

计算机技术、学习成长

计算机 » 算法 » 选取算法:中位数和第k小数

选取算法:中位数和第k小数

选取序列的第i小元素又称为选择问题,第i小的元素又称为第i个顺序统计量。简单的,排序之后我们可以立即找到第i小的元素,这种方法的时间复杂度是排序的时间复杂度,下界是O(nlogn)。但是选取第i小元素显然和排序相比要更简单,所以我们有理由相信可以效率更高。

最小值和最大值

选取最小值和最大值是选取问题的一个特例,只需要遍历序列一遍,就可以找到最值。一个返回最小值的算法代码如下

 一般选择算法

一般选择算法利用了快速排序中的partition过程。partition执行后,就有一个轴点移动到了它正确的位置,而根据我们要选取的第i小和轴点位置的大小关系,可以把问题缩减为轴点左侧和轴点右侧的问题。代码实现如下:

该算法的时间复杂度分析和快速排序类似,不同的是这里只需要递归的求解一个子问题,而快速排序要递归求解两个子问题。

当最坏情况出现时,也就是每次的轴点正好把整个序列分成一部分,每次问题规模缩小1 ,这时有最坏时间复杂度O(n^2)

但是在实际中,由于元素是随机的,不太可能出现这种最坏情况。平均情况下这种快速选择的算法时间复杂度为O(n)。

partition过程把数组分为k-1和n-k两部分,为了得到上界,不妨设i位于较多元素的一部分。为了求得平均的复杂度,我们对轴点k从1到n进行累加然后求平均:

下面是一个大概的推导,等于号并不严格,但对渐进意义复杂度没有影响。

$$T(n) = \frac{1}{n} \sum_{k=1}^{n}{[T(max(k-1, n-k) + O(n))]}$$

k从1到n/2时,n-k比较大;k从n/2到n时,k-1比较大,此处忽略取整符号,这不会影响渐进复杂度,有

$$T(n) = \frac{2}{n} \sum_{k=n/2}^{k=n-1}{T(k) + O(n)}$$

下面用数学归纳法证明T(n) < cn 。

初始条件:n足够小时,可看做常数,自然有T(n) = O(n)

假设:   k <= n-1的时候 T(k) = O(k),即k<=n-1时 T(k)是 O(k)量级

推导:只需要证明 k=n 时 T(k) 仍然是O(n)量级。

不妨设k <= n-1时 T(k) = O(k) <= ck,则有

$$T(n) < \frac{2}{n} \sum_{k=n/2}^{n-1}{ck} +  O(n)  =   \frac{2c}{n} \sum_{k=n/2}^{n-1}{k}   + O(n)$$

显然,这个求和结果是n^2的量级,但是前面有2/n ,结果是O(n)量级。因此k=n时,T(k) = O(k)

最坏情况为线性时间的选择算法

上面的quickselect算法,最坏时间复杂度是因为划分的不平衡。只要想办法保证每次划分出的两部分成比例,而不是 常数:n ,就应该可以保证时间复杂度不至于降到O(n^2)。

下面的线性时间的选择算法就是应用了这种思想,他可以保证有一个比较好的划分:

该算法和上面的quickselect类似,只不过修改了轴点的选取。

该算法中有一个常量Q ,这个Q非常小,因此对Q个元素进行排序只需常数时间。假设该算法时间复杂度为T(n)

1. 把输入数组n个数分成 n/Q 组,每组Q个元素。用时 O(n)

2. 对n/Q 组数每组分别排序,找到每组的中位数。用时 O(n/Q)

3. 递归调用该选择算法找出 n/Q 个中位数的中位数x 。用时 T(n/Q)

4. 在partition过程中,按照中位数的中位数x来进行划分。用时 O(n)

5. 可以确信在最坏情况下把问题缩减为原问题的3/4 , 递归求解用时 T(3/4 n)

好的划分是如何保证的

下面说明为什么最坏情况下可以把问题缩减为3/4 n,这得益于轴点的选取。下图是一个Q=5的例子,每列都已经排序好。

scrn20160110172000

通过中位数的中位数来选取的轴点,可以看到,图中小于x的元素和大于x的元素均最少是n的四分之一,剩余蓝色部分大小未知。

因此,最坏情况也要把原问题缩减为3/4

时间复杂度

把上面5个步骤加起来,我们有

$$T(n) = O(n) + T(n/Q) + T(3/4)$$

要想解得T(n)为线性,只需要两个递归求解的问题之和小于n,即

n/Q + 3n/4 < n ,也就是

1/Q + 3/4 < 1

可以解得 Q  >  4

因为取Q=5 ,就可以实现这个线性的选取算法。

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/quickselect_and_linearselect.html

上一篇:

下一篇:

我要评论

验证码*: 4 + 3 =