算法：什么是检查集合包含的最快方法？

拥有一组N集合，生成这些集合的包含图的最快方法是什么？算法：什么是检查集合包含的最快方法？

2010-08-12 banx

如果你有一组N组，其中没有一组包含另一组，所有相同的大小，你将需要做N^2组比较。

2010-08-12 12:23:18 deinst

我相信如此。如果这些集合的大小相同，我们可以散列，但如果它们的大小几乎相同，那我平均无法看到O（元素数量）比较。只要我们知道包含不可能发生（我们可以尽快退出）（较小集合不匹配或者较大集合中有太多不匹配），但这无济于事。 – deinst 2010-08-12 12:36:42

包含比较将花费多少钱？一个元素的比较操作？这是否让我们用O（N^2 * A）算法？ – banx 2010-08-12 12:37:07

我可能是错的。我经常是。 – deinst 2010-08-12 12:37:09

那么，让我们就最坏的情况进行推理，为了简单起见，假设您有一个有效的集合表示，您可以在其中检查恒定时间的成员资格。

要确定一个集合X是否是Y的子集，您必须执行| X | Y的成员资格测试次数与时间成线性比例| X |。所以如果你有N个集合，并且想弄清哪些集合是其他集合的子集，那么你就必须做这样的子集测试，因此我想你最终的复杂度是O （AN ）其中A是最大集合中元素的数量。

即使你可以做一些聪明的事情来同时决定“X子集Y”和“Y子集X”，你不会获得超过一个因子2，所以复杂性不会提高。

2010-08-12 12:30:42 aioobe

我想最终的复杂性是O（N^2 * A），其中A是集合中元素的最大数量。 – banx 2010-08-12 13:31:41

当然。我把它混合起来。更新答案... – aioobe 2010-08-12 13:48:16

首先，您可以显示该图将包含给定n个集合的O（n^2）个边：考虑集合A1，...，An，其中每个集合= {1，...，k}。然后，在包含图中，A1子集A2，A1子集A3，...，A1子集An，A2子集A3，...是n（n-1）/ 2个边。

鉴于此，我可以想出一个合理简单的方法来解决这个问题。让Ai可能是子集Aj，如果Aj中有一些x不在Ai中。现在，Ai子集Aj如果Ai可能是子集Aj而不是Aj可能是子集Ai。

现在，对于每个元素x将您的集合分为两个：那些包含x和那些没有。后者可能是前者的子集。将相应的边添加到maybe-subset图中。每当我们在每个方向上都有一对顶点连接时，我们知道两个顶点都不是另一个的子集。对于m个元素和n个集合，这个算法是O（mn^2）。

Et瞧！

2010-08-13 03:08:07 Rafe

回答