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

Question

考虑在一组 N 个独立且同分布的浮点值中找到前 k 个元素的任务。通过使用优先级队列/堆，我们可以对所有 N 个元素进行一次迭代，并通过以下操作维护一个 top-k 集合:

• 如果元素 x 比堆头“差”:丢弃 x ⇒ 复杂度 O(1)

• 如果元素 x 比堆头“更好”:移除堆头并插入 x ⇒ 复杂度 O(log k)

这种方法的最坏情况时间复杂度显然是 O(N log k)，但是平均时间复杂度呢？由于独立同分布假设，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)，您可以从那里计算平均成本。