Sets union in O(N)

Правка en3, от Kambar_Z, 2023-06-06 01:25:21

Hello everyone!

While solving a math problem recently, I came up with an interesting trick on sets union. The ordinary solution using inclusion-exclusion principle for 3 sets looks as following:

|x1 ∪ x2 ∪ x3| = |x1| + |x2| + |x3| — (|x1 ∩ x2| + |x1 ∩ x3| + |x2 ∩ x3|) + |x1 ∩ x2 ∩ x3|

Obviously the time complexity to compute union of N sets by this approach is O(2 ^ N).

Now, lets store for each set xi (1 <= i <= N) only those subsets that are not intersected with other subsets on prefix:

u1 = x1

u2 = |x2| — |x2 ∩ u1|

u3 = |x3| — |x3 ∩ u2| — |x3 ∩ u1|

Then answer could be found as following:

|x1 ∪ x2 ∪ x3| = |u1| + |u2| + |u3|

The algorithm is simplified to O(N ^ 2).

But, we can reorder the formula to compute each ui as following:

u3 = |x3| — |x3 ∩ |u1 ∪ u2||

u4 = |x4| — |x4 ∩ |u1 ∪ u2 ∪ u3||

...

Here we only need to maintain the union of previous subsets on prefix, that could be done in O(1) since they do not intersect.

Thus total complexity to find union of N sets is reduced to O(N).

Теги math, inclusion-exclusion, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Kambar_Z 2023-06-06 01:25:21 26 Tiny change: ' found as union of all subsets (ui):\n\n|x1 ∪' -> ' found as following:\n\n|x1 ∪'
en2 Английский Kambar_Z 2023-06-06 01:24:22 19
en1 Английский Kambar_Z 2023-06-06 01:19:08 1120 Initial revision (published)