假設(shè)集合A有n個(gè)元素，集合B有m個(gè)元素，兩個(gè)集合取自某個(gè)空間（universe）。

1.1, 首先從最naive的辦法開始。對(duì)B中元素，挨個(gè)測(cè)試是不是在A中，交集、并集都是O(m*n)，平方級(jí)別的算法。

1.2, 將A先排序，O(n*logn)，然后，對(duì)B中元素，挨個(gè)測(cè)試是不是在A中，這時(shí)可以二分了，O(m*logn），一共是O(n*logn)+O(m*logn)=O((m+n)*logn)。

所以如果m<n的話，對(duì)調(diào)一下A和B比較好，也就是復(fù)雜度是O( (m+n) * log( min(m, n) ) ).

這種思路的本質(zhì)是，只利用了“A是集合”這個(gè)事實(shí)，然后對(duì)B中元素進(jìn)行is in A的測(cè)試，測(cè)試過程需要O(m*logn)的復(fù)雜度。

1.3, A、B都排序一下，剩下的工作就和merge-sort很像了，兩個(gè)指針交替往前走。最壞情況下，需要max(m, n)次比較。

對(duì)于基于sorting的辦法，也許可以再優(yōu)化？

2.1，既然已經(jīng)排完序了，那么立刻就知道兩邊元素的范圍了，譬如 A in [a1, a2], B in [b1, b2]，根據(jù)這個(gè)上下界，可以去掉一部分，然后對(duì)真正有overlap的部分，進(jìn)行merge。極端情況下，根據(jù)上下界可以去掉絕大部分乃至全部元素。

另一種思路，用hash-table來。

3.1, A構(gòu)造一個(gè)hash-table，O(n)的插入。然后，對(duì)B中元素，挨個(gè)測(cè)試是不是在表中。這次，連二分也不用了，O(m)的測(cè)試，一共是O(m + n)。

代價(jià)呢？額外的hash-table，O(n)的table（根據(jù)hash-table的性質(zhì)，通常還會(huì)更大）。

其他一些思路，可能適用于某些特定場(chǎng)合。

4.1, 倘若元素范圍不大，可以上bitmap（本質(zhì)上也是hash-table），兩個(gè)集合用兩個(gè)bitmap表示，交集就是and，并集就是or，太方便了。

4.2, 另外一個(gè)可能的解決方案，bloom filter。另開博文吧，參見： http://www.cnblogs.com/qsort/archive/2011/05/06/2039223.html

Finding intersection and union of two sets.