0

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

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

我能想到的最好方法是这样的：

  1. 从每组中取出前 N 项
  2. 找到排名最低和该排名得分最高的项目。
  3. 将该分数除以组数。（分数低于此的任何键都永远无法进入前 N）
  4. 取这些键的并集。（忽略分数）
  5. 查找所有集合中所有键的分数。（一个键可能在一组中得分为 1，在另一组中得分为 10000）

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

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

4

1 回答 1

3

您提出的算法似乎很尴尬。只需采取以下措施之一：

简单的方法

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 是集合数。

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

更有效的方法

维护每个集合中所有最小元素的优先级队列。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).

于 2014-06-10T10:31:02.607 回答