找到n元素集的第k个分位数.(来自cormen)

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 [i +中的第n个k个最小元素1 ... n].

如果i是<k,则递归地选择右子阵列A [i + 1 ... n]中的第n-i + k个最小元素,并递归地选择左子阵列A中的第k个最小元素[0 ...一世].

主要调用只是选择(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).

Answer 2

我没有经历过你的方法，但这是 Int 的问题。Cormen 的算法。无论如何，我自己正在寻找解决方案，并且我很乐意分享我的算法版本。尝试反驳其正确性：

我假设我们有一个 O(n) 统计查找算法。所以我可以在 O(n) 时间内找到第 k 个统计量。假设我说我将使用分治法找到所有 n/k k 个分位数，这样：

如果我有 n' 个元素，我将数组分成 n'/2 个部分，报告两个 n'/2 个分区的边界 k 个分位数。并递归报告剩余的分位数。本质上，我所做的是，在使用中位数分区后，我将从左侧数组中提取最右侧的分位数，从右侧分区中提取最左侧的分位数，并在修剪这些数组后递归运行算法。我的复杂性分析结果是：

T(n,k) = 2*T(n/2,k/2) + O(n)。

结果是 O(nlogk)，因为 k/2 部分收敛得更快，尽管您可能想更严格地解决这个问题。此外，我们还使用了 n>k( 从问题中显而易见。请注意，提取 2 个分位数并修剪数组的任务将在 O(n) 内完成