我想找到两个LinkedHashSet<String>之间的共同元素，主要是我写了自己的函数，但成本是o（n ^ 2）。然后我找到了一个更好的retainAll() java内置函数的解决方案。我想知道这个功能的成本是多少。 O（n）或o（n ^ 2）？
查看AbstractCollection中的实现，它迭代调用的集合的所有元素（即n），并且每个元素检查其他集合是否包含它（在LinkedHashSet的情况下为O（1）操作）。
总之 - 这是一个O（n）操作，其中n是你调用方法的集合的大小。
LinkedHashSet至少为O（N）。对于像树集一样的其他Collections，它将是O（NlogN），其余的，你回到O（N ^ 2）。
请注意，这些度量取决于您传递给retainAll方法的集合。所以传递HashSet将是O（N），TreeSet将是O（NlogN），其他任何东西都将比O（NlogN）更糟糕