java集合中元素比较的性能

Question

问题:

给定两个Collection<?>s,检查两者是否包含相同的元素.

• 假设集合的实际实现是未知的
• 假设元素不以相同的顺序出现
• 假设在同一个集合中没有元素确实出现过两次

解决方案1:

boolean equals = c1.containsAll(c2) && c2.containsAll(c1);

解决方案2:

boolean equals = new HashSet<?>(c1).equals(new HashSet<?>(c2));

我认为解决方案2比解决方案1(O(n ^ 2))更有效(O(n )).

我纠正还是错过了什么？

Answer 1

这些的大O复杂性是正确的,解决方案1涉及对另一个列表O (n)中的每个项目迭代一个列表(),即O (n^2).解决方案2涉及两个O (n)副本并迭代一个set(O (n))并对O (1) .contains()另一个set 进行检查.总而言之,那就是O (n).

但是根据你的约束,你可以做得更好(不是渐近更好,只是更好的实现).

• 由于我们假设没有重复元素,因此无需进行第二次.containsAll()检查.只需检查它们是否相同(可能是O (n),但它仍然比复制O (n^2)支票更好)然后执行.containsAll().

• 没有必要转换c2成a Set,因为它会反过来迭代; 只需转换c1和使用.containsAll().

• 您可以使用instanceof Set来测试c1或c2已经是一个Set,并使用该对象的.containsAll()方法; O (n)即使另一个对象不是一个集合,这将及时运行,并避免解决方案2具有的复制开销.