两个不同数量集合嵌套循环，怎样效率高？

Question

两个不同数量相互有交集的集合嵌套循环，判断元素是否交集并进行处理。

是大集合在外部循环效率高，还是小集合在外部循环效率高？

Answer 1

这个好像跟分配到内存有关系，当分配的内存不足以将两个集合的数据都读入内存时就要涉及到i/o问题了，这时候较大的作为内循环会比较好，争取一次将内循环的集合（即较大的集合）整个读入内存

Answer 2

这个要看你的集合是不是有序的，如果是无序的话，他们的时间复杂度是一样的。如果两个集合都是有序的话，小集合在外，大集合在里面。你可以在最里面的for循环中，打印一个count字段，用来统计for循环了多少次。

Answer 3

假设集合 A 的元素数为 m，集合 B 的元素数目为 n，且 m > n。那么两种循环下：最佳情况的时间复杂度均为 O(n2) 即 n 的平方，最差情况的时间复杂度均为 O(mn)所以，两者在时间复杂度上是相同的。