『算法导论』第 9 章:中位数与顺序统计量

主要内容

本章讨论顺序统计量,即某个集合中大小排名第几的元素。比如最小值是第一个顺序统计量,最大值是最后一个顺序统计量,中位数是集合的中点元素。如果元素有奇数个,有唯一的中位数;如果元素有偶数个,有两个中位数,一般选取较小的那个。将问题一般化,则是从含有互异元素的集合中找到特定大小排名的元素。

最小值和最大值

在一个含有$n$个元素的集合中,最多需要$n-1$次比较就能确定最小元素。下面是代码实现:

1
2
3
4
5
6
7
8
9
10
int mininum(int A[], int n)
{
int min = A[0];
for (int i = 1; i < n; i++) {
if (min > A[i]) {
min = A[i];
}
}
return min;
}

这是是最好的结果,对于最小值问题,至少也需要$n-1$次比较。

在某些应用中,我们需要同时找到最大值和最小值。最简单的办法是分别独立地找到最大值和最小值,那么一共需要$2n-2$次比较。实际上有更好的办法,可以对输入元素成对地处理:首先将它们相互比较,然后把较小的与当前最小值比较,把最大的与当前最大值比较。这样每两个元素共需要3次比较。总的比较次数至多是$3 \lfloor n/2 \rfloor$。

期望为线性时间的选择算法

一般选择问题看起来要比找最小值这样的简单问题更难,但其实这两个问题的渐进运行时间同为$\Theta(n)$。本节介绍一种解决选择问题的分治算法RANDOMIZED-SELECT。类似于快速排序,对数组进行递归划分。但不同的是,快速排序递归处理划分的两边,而该算法只处理划分的一边,所以性能也有差异。实现要用到第七章介绍的快速排序中的randomized_partition函数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int randomized_select(int A[], int p, int r, int i)
{
if (p == r) {
return A[p];
}

q = randomized_partition(A, p, r);

k = q - p + 1; // 主元是第k大的数
if (i == k) {
return A[q];
} else if (i < k) {
return randomized_select(A, p, q-1, i); // 在左边找
} else {
return randomized_select(A, q+1, r, i-k); // 在右边找
}
}

可以证明,上述算法的期望运行时间为$O(n)$,即,若所有元素是互异的,在期望线性时间内,可以找到任一顺序统计量,特别是中位数。

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

还有一个最坏情况下运行时间为$O(n)$的选择算法SELECT,也通过对数组的递归划分来找出所需元素。过程和代码从略。

习题解答

待完成。

还是贴出付款码吧,没准真有人打赏呢!