algorithm - 获取 M 排序集并集的前 N ​​项的最有效方法是什么

Question

假设您有 4 个排序集，其中包含成千上万个键和分数。由于它们是有序集合，因此可以在对数时间复杂度内完成获取顶部项目。

最简单的方法是对集合进行并集，然后获取最上面的项。但这样做至少与所有集合中所有项目的总和呈线性关系。

我能想到的最好的方法是:

1. 从每组中取出前 N 个项目
2. 找到排名最低且得分最高的项目。
3. 将该分数除以组数。 (任何低于此分数的键永远不会在前N个)
4. 获取这些键的并集。 (忽略分数)
5. 找出所有组中所有键的分数。 (一个键可能在一组中得分为 1，在另一组中得分为 10000)

这就像，找到可能位于顶部列表中的所有键，并与这些键进行并集。可能有更有效的方法来限制要考虑的项目数量。

[编辑] 键出现在一组或多组中，它们的总分决定了最终得分。 因此，在所有集合中得分较低的 key 可能比仅在一个集合中得分较高的 key 具有更高的得分。

Answer 1

你提出的算法看起来很尴尬。只需采取以下其中一项:

简单的方法

for i = 1 to n
    loop through all sets and look at their smallest element,
    pick the smallest element and remove it from the sets

复杂性: O(n * s) 其中 n 是您想要的项目数，s 是集合数。

当然，如果您不允许从集合中删除元素，您也可以在每个集合中维护迭代器，以按排序顺序从中获取元素，而无需更改集合。

更高效的方式

为每个集合的所有最小元素维护一个优先级队列。每当从该优先级队列中移除最小元素 e 时，重新插入 e 来自的集合中的下一个元素。

复杂性:假设一个简单的优先级队列具有O(log n)“插入”和O(log n)“移除最小元素”的复杂性。有更好的，如斐波那契堆，但这个就可以了。然后我们有:

• s 插入以在开始时填充优先级队列，因此 O(s log s)。
• n "删除最小元素"+ 插入一个新元素，所以 O(n log s) (因为总有 s 元素在队列中)

因此，我们实现了更好的 O(s log s + n log s)。

比较

只要s很小，算法之间应该没有太大区别，你也可以选择简单的。如果您有很多组，那么您绝对应该选择第二种方法。

查找复杂度

在我的分析中，我省略了为每个集合查找最小元素的对数查找因子，并假设可以在 O(1) 中检索每个集合的最小元素，就像在排序中一样列表。将查找成本从 O(1) 更改为 O(log n) 只是引入了一个不会改变算法的额外因素。此外，您通常只需在第一次查找时支付一次 O(log n)。之后，您通常会有一个指向最小元素的迭代器。然后使用迭代器访问每个进一步的元素仅为 O(1)。