查找top-k元素的平均時間複雜度

Question

考慮在一組N個獨立且分佈相同的浮點值中查找top-k元素的任務。通過使用優先級隊列/堆，我們可以在所有N個元素重複一次，並保持前-K通過以下操作設置：

• 如果元素x大於堆的頭「雪上加霜」：廢棄X ⇒複雜度O（1）

• 如果元素x是大於堆的頭部 「更好」：刪除頭部和插入X⇒複雜爲O（log K）

的最壞情況下的時間複雜度這種方法顯然是O（N log k），但平均時間複雜度呢？由於iid假設，O（1）操作的概率隨着時間而增加，並且我們很少必須執行昂貴的O（log k），尤其是對於k而言，這是平均時間任何可引用參考文獻中記錄的複雜性什麼是平均時間複雜度？如果你有一個可供參考的答案，請包括它。

Answer 1

考慮第i個最大的元素和一個特定的排列。如果它在排列中不超過（i-1）個較大元素的k-1之前出現，它會插入到k大小的堆中。

如果i < = k，那麼堆插入發生的概率爲1，如果i> k，則k/i。

由此，您可以使用期望的線性來計算堆調整數的期望值。它是sum（i = 1到k）1 + sum（i = k + 1到n）k/i = k + sum（i = k + 1到n）k /i=k *（1 + H（n） - H（k）），其中H（n）是第n個諧波數。

這大約是k log（n）（對於k < n），您可以從那裏計算您的平均成本。