java - HashSet disjoint() 复杂度

Question

两个整数哈希集的 Java Collections disjoint() 方法的大 O/时间复杂度是多少？

非常感谢任何帮助，因为我不确定它是 O(1) 还是 O(n)。

我知道哈希集包含是一个 O(1) 操作，但我不确定不相交的操作是否循环遍历集 1 的所有元素并检查集 2 是否包含这些元素中的任何一个。

标签： javatimecollectionscomplexity-theory

Answer 1

是 O(n)。

假设集合查询是 O(1)。您需要遍历其中一组，并在另一组中进行查询以查看它是否包含项目。

因此，集合迭代至少需要 O(n) 时间（您可以选择以较小的大小迭代集合。这就是他们在源代码中所做的）。

总的来说，时间复杂度是 O(n)。