查找n元素集的第k個分位數。（來自cormen）

n元素集合的第k個分位數是將排序後的集合分成k個相等大小的集合（在1之內）的k-1階統計量。給出一個O（n lg k）時間算法來列出集合的第k個分位數。查找n元素集的第k個分位數。（來自cormen）

的直接的解決方案是選擇每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）。

來源

2010-10-11 user472402

在尋求幫助之前，您有多遠了？ – 2010-10-11 15:13:44

請下載者發表評論。我的猜測是你低估了這個問題，因爲它沒有顯示user472402已經做了什麼來解決這個問題，哪裏被卡住了。 – 2010-10-11 15:22:40

海傢伙，抱歉沒有提供任何背景，我卡在哪裏。我是相當新的博客:) 海峽前進的解決方案將是選擇每個k，2k，.. ik th元素。運行時間將是O（kn）。我正在考慮如何減少因子k來記錄k。但我沒有得到任何結論。請幫忙。 – user472402 2010-10-11 15:56:30

我還沒有經過你的方法，但這是來自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）中完成

來源

2011-11-26 17:04:23 sanket

請注意，我們使用修改後的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）。

來源

2012-07-07 10:55:45

我們可以使用RANDOM-PARTITION而不是PARTITION來提高效率。 – 2016-05-02 07:50:27

查找n元素集的第k個分位數。 （來自cormen）

回答

相關問題

查找n元素集的第k個分位數。（來自cormen）