有什么算法可以很快地取到交集。

cokeboL

回复 9# selfrun


    树本身的操作带来的额外复杂度可能已经太大了

shan_ghost

selfrun 发表于 2013-04-01 10:45

这个好。不排序时间复杂度就下去了。

设各集合总数据量为N，则空间复杂度O(N)（用hash_map的话，应该是O(N*(1+x%))，x为额外保留、用于避免key冲突的空间），时间复杂度O(2N)=O(N)。

cokeboL

回复 10# shan_ghost


    我感觉排序没必要，直接遍历比较应该更省

selfrun

回复 11# cokeboL


    红黑树增删查的复杂度都是log(n)，空间嘛，每个节点3*sizeof(void*) + sizeof(byte) + sizeof(key) + sizeof(value)；百万数量级的小case

cokeboL

回复 14# selfrun


我是说，map或树本身的操作，就一堆代码，同样的O(n)，用树和for(  i < n  )相比，实际操作数上树、map要多很多

而且你看看遍历比较的，复杂度也没多高

selfrun

回复 15# cokeboL


    你说的方法复杂度是o(n)的,n=sum(N_1....N_max);若能实现当然最好；
不过实际问题里key的值域是很大的范围，空间复杂度太高； 若是用hash算法把key转成0~n-1的值，又很难保证不重复；或者用关联数组从key映射到索引，又回到关联数组上了...

cokeboL

回复 16# selfrun


空间复杂度没多大的，用C++的话也可以vector之类的，如果事先就找出各个数组中长度最小的n_min，空间复杂度最大也不会超过n_min，而且还可以不超过

第一个找出的交集长度，时间却会省很多

hbmhalley

开一个大小可以忍受的 bool 数组，比如 bool its[0x10000] = {false..}
扫每个集合，过程略，最终: 对于 m，若所有集合里都存在某个 X 使得 (X&0xffff)=m，则 its[m] == true 否则 false
每个集合的每个元素 X 都附带一个 flag (初始true) ，扫完一遍后， flag &= its[X&0xffff]
这样筛掉后 16 位，用同样的方法筛 32 48 64位等等
最终 flag 为 true 的就是交集中的元素

复杂度 O(mn*log(65536,maxnum))，约等于下限 O(mn)

+实际上，这应该就是下限
因为判断两个数是否相等下限是 log(2^32,maxnum)=log(2^16,maxnum)/2
+排序是不必要的，而且楼上复杂度里都忽略了大数比较的复杂度

__BlueGuy__

数组 1 排序后， 对数组2进行二分查找

这是最自然的了， 看看速度再说吧.

__BlueGuy__

看你们说的津津乐道， 我就想笑