什麼是這種方法的尋找k個最大N個

雖然我理解的方式，我不明白他們O((n-k)*k)計算時間複雜度。

從我的角度來看，您正在對n-k元素進行線性遍歷並對每個元素進行單一比較。然後可能替換K元素的臨時數組中的一個元素。

更具體地說，O((n-k)*k)的O((n-k)*k)計算的時間複雜度的*k方面從哪裏來？爲什麼他們乘以n-k？

也許是因爲你必須臨時數組（K）與初始陣列的每個剩餘元素中的每個元素進行比較（N - k）的，即K *（N - k）。看起來算法描述有點不對，因爲如果我沒有弄錯，你必須重複步驟＃2和＃3： – Ivan

使用最大堆來存儲數字，那麼總的複雜度就是'O（n ）'爲build-heap和'O（k * lg（n））'找到k個最大的元素。 –

@SandipanDey或更好，但爲第一個_k_元素構建最小堆，然後爲_（nk）logk_時間執行_（nk）_插入和刪除 - 分鐘，然後爲另一個_klogk_執行_k_ find-mins和delete-mins _nlogk_時間。 –

讓我們考慮，在kth iteration：

arr[k] > min(temp[0..k-1]

現在，你將與arr[k]取代min(temp[0..k-1])。

現在你又需要計算temp[0..k-1],的更新min，因爲這會改變。它可以是您更新的任何數字temp[0..k-1]

因此，在最壞的情況下，您每次更新min，因此更新O(k)。

因此，時間複雜 = O((n-k)*k)

2017-02-14 12:46:24

回答