algorithm - 查找 n 元素集的第 k 个分位数。 (来自科门)

Question

n 元素集合的第 k 个分位数是将排序集合划分为 k 个大小相等的集合(在 1 以内)的 k - 1 阶统计量。给出一个时间复杂度为 O(n lg k) 的算法来列出集合的第 k 个分位数。

直接的解决方案是选择每个 k、2k、3k .. ik 最小元素，其运行时间为 O(kn)(k 调用 O(n) 的选择过程)。但这可以优化为比 O(kn) 做得更好。在 select 过程中找到索引“i”处的中位数的中位数后，我们进行以下递归调用。

如果中位数i的中位数索引>k，递归调用选择左子数组A[0 ... i]中第k小的元素

如果i < k，则递归选择右子数组A[i+1 ... n]中第n - i + k个最小的元素。

能否将上述递归调用修改如下，从而将因子“k”减少为“log k”？

如果中位数i的中位数索引> k，则递归选择左子数组A[0 ... i]中第k小的元素，同时递归选择右子数组A中的第n-k小元素[i+1 ... n].

如果 i < k，递归选择右子数组 A[i+1 ... n] 中第 n - i + k 个最小元素，同时递归选择左子数组 A[0] 中第 k 个最小元素...我].

主要的调用只是 select(A, k, n)。

Answer 1

请注意，我们使用修改后的 PARTITION，它被赋予了一个枢轴索引，用作其最后一个输入参数。

你从KTH-QUANTILES(A, 1, n, 1, k-1, k)开始

KTH-QUANTILES(A, p, r, i, j, k)
n=A.length
m=floor((i+j)/2)
q=floor(m(n/k))
q=q-p+1
q=SELECT(A, p, r, q)
q=PARTITION(A, p, r, q)
if i<m
    L=KTH-QUANTILES(A, p, q-1, i, m-1, k)
if m<j
    R=KTH-QUANTILES(A, q+1, r, m+1, j, k)
return L U A[q] U R

递归树的深度是 lg k，因为分区是围绕给定顺序统计信息(从 i 到 j)的中位数进行的。

递归树的每一层都有Θ(n)次操作，所以运行时间为Θ(nlgk)。