查找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）更好。在選擇過程中在索引'i'處找到中位數的中位數後，我們進行以下遞歸調用。

如果中值i是中值的指數> K，遞歸地調用的左子陣列甲選擇第k個最小的元素[0 ... I]

如果i是< K，遞歸地選擇在右子陣列A [i + 1 ... n]中第n + i + k個最小元素。

，在上面的遞歸調用作如下修改這將因子「K」減少「登錄K」？

如果中位數i的中位數的索引大於k，則遞歸地選擇左子數組A中的第k個最小元素A [0 ... i]，並遞歸地選擇右子數組中的第n-k個最小元素A [i + 1 ... n]。

如果i是< k，遞歸地選擇右子陣列A [i + 1 ... n]中的第n-i + k個最小元素，並遞歸地選擇左子陣列A [ 0 ... i]。

主要呼叫將只選擇（A，K，N）。

Answer 1

我還沒有經過你的方法，但這是來自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部分將收斂更快，但你可能要解決更嚴格。請注意，提取2個分位數和修整陣列的任務將在O（n）中完成

Answer 2

請注意，我們使用修改後的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，因爲分區圍繞給定的順序統計的中位數（已完成從我到j）。

在遞歸樹的每一層都有Θ（n）個操作，所以運行時間是Θ（nlgk）。