算法：什麼是檢查集合包含的最快方法？

擁有一組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

回答