algorithm - 查找前 k 个元素的平均时间复杂度

Question

考虑在一组 N 个独立且同分布的浮点值中找到前 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。

这个平均时间复杂度是否记录在任何可引用的参考资料中？平均时间复杂度是多少？如果您的答案有可引用的参考资料，请附上。

Answer 1

考虑第 i 个最大的元素和特定的排列。如果它出现在不超过排列中 (i - 1) 个较大元素的 k-1 个之前，它将插入到 k 大小的堆中。

如果 i <= k，则发生堆插入的概率为 1，如果 i > k，则为 k/i。

由此，您可以使用期望的线性度来计算堆调整次数的期望。它是 sum(i = 1 to k)1 + sum(i = k+1 to n)k/i = k + sum(i = k+1 to n)k/i = k * (1 + H(n) - H(k))，其中 H(n) 是第 n 次谐波数。

这大约是 k log(n)（对于 k << n），您可以从那里计算平均成本。