高效的多選算法

我必須實現一個解決多選問題的算法。的多項選擇的問題是：高效的多選算法

給定n個元素的集合S從直線有序集合繪製，以及一組K = {K1，K2，...，KR}正整數的1和n之間，多選問題是選擇き個最小的元素對於i的所有值，1 < = I < = R

我需要解決上Θ平均情況下（N捲筒R）我發現一個實現我需要的解決方案的論文，但它假定在集合S上沒有重複的數字。問題是我不能假設這一點，而且我也不知道如何調整該算法的pap呃支持重複的數字。這篇文章在這裏：http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf 並且算法在第二頁上。任何提示都歡迎！

來源

2013-09-29 Ivan

爲什麼你不能簡單地使用快速排序對該集合進行排序並直接選擇kith元素？不知道我是否理解正確。 –

@AbhishekBansal，因爲它的成本平均是Θ（n log n），比我要求的要高 – Ivan

對於後代：Ivan提到的算法是對K進行排序，然後如下遞歸地解決問題。使用QuickSelect查找第i個最小元素x，其中i是ceil（r/2），然後遞歸K和S的較小半部分，以及K和S的較大半部分，將K分解爲i和S約x。

尋找在退化存在的算法（這裏，相同的元素）往往不是理論着作的作者的高優先級，因爲它使得常見的案例呈現更加困難，並且經常不起作用在確定問題的計算複雜性。這實質上是一個單一的問題，黑盒解決方案很簡單;用（yi，i）替換輸入yi的第i個元素，並使用第二個元素打破比較中的關係。

實際上，我們可以做得更好。而不是遞歸於{y：y in S，y < x}和{y：y in S，y> x}，使用關於x的三方分割算法（例如，參見QuickSort的每個充分完整的處理），然後用索引而不是數值來劃分數組S.

來源

2013-09-29 19:17:03

謝謝，用yi代替yi，並且使用比較指數就像一個魅力一樣 – Ivan

高效的多選算法

回答

相關問題