0%

快速选择算法解 Top K 问题

1. Top K 问题

Top K 问题就是在序列中寻找到 第 K 个大(或者小)的元素

对此,我们可以研究一下它的上界和下界:

  1. 上界为 NlogNNlogN

    Top K 问题只要使用排序就一定能解决,所以其最坏的时间复杂度就是排序的复杂度

  2. kk 的值较小时,如 1,2,31, 2, 3,则上界为 NN

    显然,当 k=1k = 1 时,我们只需要遍历一次数组就能获取最小或者最大元素;
    k=2k = 2 时,我们只需要遍历两次数组就可以完成工作

  3. 下界为 NN

    由 2 可知,我们可以有一个 NN 级别的算法;
    与此同时,我们至少需要遍历一次数组,才能获取到足够的信息来进行 Top K 判断

综上所述,我们可以拥有一个 O(N)O(N) 级别的算法来解决 Top K 问题,这就是这里介绍的快速选择算法。

2. 快速选择算法

快速选择算法实际上是快速排序的一个变种,通过使用快速排序的 切分 来达到选择 Top K 的目的。

事实上,由于快速排序的切分保证了:

  1. 所有左边的元素都不大于切分元素
  2. 所有右边的元素都不小于切分元素

因此,实际上切分元素的所处位置,就指示了其 Top K 特性,也就是说:

如果切分元素位于第 hh 个位置,那么切分元素就是数组中的 Top hh

2.1 算法过程

  1. 完成切分过程,获取到切分元素位置 jj

  2. k>jk > j,则对切分元素的右半边数组进行切分

  3. k<jk < j,则对切分元素的左半边数组进行切分

  4. 重复上述过程,直到 k=jk = j

2.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static Comparable select(Comparable[]a, int k) {
StdRamdom.shuffle(a);

int lo = 0;
int hi = a.length - 1;

while(hi > lo) {
int j = partition(a, lo, hi);

if (k > j) {
lo = j + 1;
}
else if (k < j) {
hi = j - 1;
}
else {
return a[k];
}
}

// 此时我们只有一个元素可以选择
// 说明此时的 a[k] 就是 Top K
return a[k];
}

3. 性能

快速选择算法的平均时间复杂度是 线性级别的(即 O(N)O(N)

其复杂度来源于切分过程,而对于切分过程,每次切分大约会将数组等分,所以需要:(N+N/2+N/4++1)2N(N + N/2 + N/4 + \cdots + 1 )\sim 2N 次的比较

一个更精确的公式如下:

CN=2N+2kln(N/k)+2(NK)ln(N/(Nk))C_N = 2N + 2kln(N/k) + 2(N - K)ln(N / (N - k))

k=N/2k = N / 2 时,有 CN=(2+2ln2)NC_N = (2 + 2ln2) N

但是与快速排序一样,快速选择的最坏情况下的时间复杂度是 平方级别 的,不过在上面的实现中,由于我们进行了随机洗牌,从而保证了性能。