一種隨時間複雜度爲O（nlogr）算法來找到第一KJ（1≤Ĵ≤R）在一組S

-2

最小號碼考慮到多個選擇問題。有一個S有n個元素。還有另外一組K有r個k1，k2，... kr。請找第一K1，K2，...在集合S一種隨時間複雜度爲O（nlogr）算法來找到第一KJ（1≤Ĵ≤R）在一組S

例如，K = {2,7,9,50}，也就是從n個元素，你需要找到KR小數字第二，第七，第九，第五十個最小元素。

通常的解決方案是對每個kj（1≤j≤r）運行SELECT算法以找到第一個kj小元素，那麼總時間複雜度爲Θ（r⋅n），請給出一個具有時間複雜度的算法O（nlogr）來解決這個問題。

證明時間複雜度爲O（nlogr）。

這是我第一次使用StackOverflow。

我首先想到的是通過添加標籤來修改SELECT算法來標記，如果A [1]（A [i]是集合S的元素）已在它的位置被確認。例如，在前者的訪問中，我已經確認了A [5]和A [18]（然後A [5]是第5小的數字，A [18]是第19個最小的數字，A [5]和A [18]只是在索引5和索引18之間）。

如果我現在需要找到第9 smllest數。我只需要SELECT（A，9，5，18）而不是SELECT（A，9，1，n）。

我對不對？我不知道如何計算這種複雜情況下的時間複雜度。要做到這一點

來源

2017-04-20 LeoKnuth

沒有冒犯，但這聽起來像是你剛剛在這裏貼了一個作業，你在打字之前是否嘗試過一些東西？也許可以編輯帖子，告訴你如何解決這個問題，告訴你至少在別人爲你做所有的工作之前試過。 – subkonstrukt

謝謝你提醒我。這是我第一次使用StackOverflow。我的第一個想法是通過添加一個標記來修改SELECT算法，以標記A [i]（A [i]是集合S的一個元素）是否已在其位置上得到確認。例如，在前者的訪問中，我已經確認了A [5]和A [18]（然後A [5]是第5小的數字，A [18]是第19個最小的數字，A [5]和A [18]只是在索引5和索引18之間）。如果我現在需要找到第九個smllest號碼。我只需要排序（A，9，5，18）而不是排序（A，9，1，n）。 – LeoKnuth

好吧，假設兩個集合都被排序，爲了得到logr時間複雜度，你將不得不做大量的工作（用英文劃分和規則（？））算法，簡單的二分查找會得到對數時間複雜度（https： //en.wikipedia.org/wiki/Binary_search_algorithm），請考慮我們給定的複雜性要求，你最壞的情況下需要爲n * logr，所以你可以保證你必須至少走低谷集S線性 - 希望可以幫助你，也是的，當然對於已排序的數組，您可以假設已經檢查的範圍之下的所有數據都低於您已經指出的 – subkonstrukt

一種方式：

在以下討論中，k是陣列K的長度，並且s是陣列S的長度。

掃描K以獲得最大數量。致電此r。複雜性：O（k）。在S
呼叫Quickselect選擇r最小的號碼。複雜性：O（s）。
從＃2的結果中構建一個二進制最小堆。叫這個堆rSmallest。複雜度：O（r）
從K創建一個集合。基本上，一個數據結構將在O（1）時間告訴集合中是否存在一個項目。請撥打kSet。複雜性：O（k）。

你現在擁有的是一個包含你想要的物品編號的集合，以及一個在數組中具有k最小值的二進制堆。然後：

i = 0; 
while (!kSmallest.isEmpty()) 
{ 
    ++i; 
    item = kSmallest.pop() // O(log r) 
    if (R.Contains(i))  // O(1) 
    { 
     output item 
    } 
}

循環是O（r log r）。因此，總的複雜度是O（s）+ O（r）+ O（k）+ O（r log r），它與O（s log r）的順序相同，因爲r <= s。

一種替代步驟2是使用最小堆選擇算法，這將是D（S日誌R）。這將節省您不得不包括第3步，但它不會提高複雜性。

來源

2017-04-20 15:00:54

一種隨時間複雜度爲O（nlogr）算法來找到第一KJ（1≤Ĵ≤R）在一組S

回答

相關問題