Java中BitSet的集合操作的时间复杂度是什么？

Question

我有一个场景，需要将BitSet索引的一定范围设置为1。

因此，如果我使用以下代码：

   /*
    *Code snippet
    */
    BitSet myBitSet = new BitSet(100);
    myBitSet.set(10, 50);

    //**************************

以上代码的时间复杂度是什么？它会遍历40个元素还是执行某种位操作？

- Abhijit

Answer 1

对于一个单独的位来说，它的复杂度是O(1)，设置n个位的复杂度是O(N)。

针对怀疑者：设置n个位的复杂度是O(N)，因为设置10,000个位需要的时间大约比设置1,000个位多10倍。

尽管如此，调用myBitSet.set(10,50)要比写for (int i=10; i<=50; i++) myBitSet.set(i);更有效率。

- Thomas Kläger

---

是的，我现在明白了。谢谢您的快速回复 :)。 - Abhijit

Answer 2

出于某些原因，Javadoc中没有明确说明，但是Oracle实现在使用一个参数进行get、set、flip和clear操作时，复杂度肯定是O(1)；使用两个参数时，则为O(N)。"位向量"可能是一种提示。

- user207421

---

谢谢您的快速回复 :)。 - Abhijit

Answer 3

由于它使用数组，因此设置/获取都是O(1)

- Trace Carrasco

---

由于它在fromIndex和toIndex之间进行迭代，因此复杂度为*O(N)*。 - user207421

“因为它使用了一个数组”是一个无中生有的论点。 - user207421

Answer 4

设置操作将设置位（fromIndex 将为 10，toIndex 将为 49） 它将从 10 到 49 开始迭代 40 个元素。是的，复杂度将为 O(1)

- Anil

---

一个迭代如何成为*O(1)*？ - user207421

O(40*1) = O(1) 是程序相关的内容。 - Terry Storm

此外，使用 fromIndex 10 和 toIndex 49，只有 39 个元素，因为 toIndex 是不包含在内的。 - yaccob