查找top-k元素的平均时间复杂度

考虑在一组N个独立且分布相同的浮点值中查找top-k元素的任务。通过使用优先级队列/堆，我们可以在所有N个元素重复一次，并保持前-K通过以下操作设置：查找top-k元素的平均时间复杂度

的最坏情况下的时间复杂度这种方法显然是O（N log k），但平均时间复杂度呢？由于iid假设，O（1）操作的概率随着时间而增加，并且我们很少必须执行昂贵的O（log k），尤其是对于k而言，这是平均时间任何可引用参考文献中记录的复杂性什么是平均时间复杂度？如果你有一个可供参考的答案，请包括它。

2013-12-20 bluenote10

IMO对于k << N，复杂度将渐近地逼近O（N）。 –

我相当确定要求一个'可引用参考'分类为推荐问题，根据[help/on-topic]，这是一个脱离[so]主题的推荐问题。随意适当地改变你的问题。 – Dukeling

@Dukeling：我不是要求推荐。我是否应该以某种独特的方式修改问题？例如，通过询问包含此结果的_first_出版物？对我而言，问题更多的是这样的参考是否存在。 – bluenote10

考虑第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），您可以从那里计算您的平均成本。

2013-12-20 17:25:17

如果k很大，则k *（log n -log k）或k * log（n/k）给出更好的结果。例如，如果k = n/2。 – gnasher729

回答