假設集合A有n個元素，集合B有m個元素，兩個集合取自某個空間（universe）。
1.1, 首先從最naive的辦法開始。對B中元素，挨個測試是不是在A中，交集、并集都是O(m*n)，平方級別的算法。
1.2, 將A先排序，O(n*logn)，然后，對B中元素，挨個測試是不是在A中，這時可以二分了，O(m*logn），一共是O(n*logn)+O(m*logn)=O((m+n)*logn)。
所以如果m<n的話，對調一下A和B比較好，也就是復雜度是O( (m+n) * log( min(m, n) ) ).
這種思路的本質是，只利用了“A是集合”這個事實，然后對B中元素進行is in A的測試，測試過程需要O(m*logn)的復雜度。
1.3, A、B都排序一下，剩下的工作就和merge-sort很像了，兩個指針交替往前走。最壞情況下，需要max(m, n)次比較。
對于基于sorting的辦法，也許可以再優化？
2.1，既然已經排完序了，那么立刻就知道兩邊元素的范圍了，譬如 A in [a1, a2], B in [b1, b2]，根據這個上下界，可以去掉一部分，然后對真正有overlap的部分，進行merge。極端情況下，根據上下界可以去掉絕大部分乃至全部元素。
另一種思路，用hash-table來。
3.1, A構造一個hash-table，O(n)的插入。然后，對B中元素，挨個測試是不是在表中。這次，連二分也不用了，O(m)的測試，一共是O(m + n)。
代價呢？額外的hash-table，O(n)的table（根據hash-table的性質，通常還會更大）。
其他一些思路，可能適用于某些特定場合。
4.1, 倘若元素范圍不大，可以上bitmap（本質上也是hash-table），兩個集合用兩個bitmap表示，交集就是and，并集就是or，太方便了。
4.2, 另外一個可能的解決方案，bloom filter。另開博文吧，參見： http://www.cnblogs.com/qsort/archive/2011/05/06/2039223.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
