寻找前k个元素的平均时间复杂度

Question

5

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

- 如果元素x比堆的头部“更差”：舍弃x ⇒ 复杂度O(1) - 如果元素x比堆的头部“更好”：删除头部并插入x ⇒ 复杂度O(log k)

这种方法的最坏情况时间复杂度显然是O(N log k)，但平均时间复杂度如何呢？由于iid假设，O(1)操作的概率随着时间的推移而增加，我们很少需要执行代价高昂的O(log k)，尤其是对于k << N的情况。

这种方法的平均时间复杂度文献上是否有明确记录呢？如果您有可引用的参考文献，请包含在答案中。

- bluenote10

我相当确定要求“可引用参考”的分类属于推荐问题，这在[so]上是不适合讨论的，根据[help/on-topic]规定。请随意更改您的问题以适应该网站的主题。 - Bernhard Barker

1

@Dukeling：我不是在寻求建议。我是否应该修改问题，使其具有唯一的答案？例如，通过询问包含此结果的_第一个_出版物？对我来说，问题更多的是是否存在这样的参考资料。 - bluenote10

1

这个网络不适合请求可引用参考文献。询问“我该如何做到这一点/找到这个/这是什么”之类的问题是可以的，但如果你真的在寻求研究帮助，那就不合适了。 - Joe

2

元讨论请点击此处（http://meta.stackexchange.com/q/212944/212780）。 - Geobits

1

与其要求引用，为什么问题不直接是“平均时间复杂度是多少？”这并不难从第一原理推导出来（例如：可以看看我的答案）。 - Paul Hankin

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Hankin · Accepted Answer

考虑第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)，你可以从中计算出平均成本。