blu*_*e10 5 algorithm heap complexity-theory time-complexity top-n
考虑在一组N个独立且相同分布的浮点值中查找top-k元素的任务.通过使用优先级队列/堆,我们可以在所有N个元素上迭代一次,并通过以下操作维护top-k集:
如果元素x比堆头"更差":丢弃x⇒复杂度O(1)
如果元素x比堆头"更好":移除头部并插入x⇒复杂度O(log k)
这种方法的最坏情况时间复杂度显然是O(N log k),但是平均时间复杂度呢？由于iid假设,O(1)运算的概率随着时间的推移而增加,并且我们很少需要执行昂贵的O(log k),尤其是对于k << N.
这个平均时间复杂度是否记录在任何可引用的参考中？什么是平均时间复杂度？如果您的答案有可引用的参考,请加入.
考虑第 i 个最大的元素和特定的排列。如果它出现在排列中不超过 k-1 个 (i - 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），您可以从那里计算平均成本。