Что такое сложность времени установки операции BitSet в java?

Question

У меня есть сценарий, где я должен установить диапазон индекса BITSET к 1. Так что, если я использую

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

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

Что бы временная сложность для приведенного выше кода? будет ли он проходить через 40 элементов или будет выполняться какая-то бит-операция?

Answer 1

Для одного бита это будет O (1), сложность установки n бит равна O (N).

Для скептиков: установка n бит равна O (N), поскольку установка 10_000 бит занимает примерно 10 раз дольше, чем установка 1_000 бит.

Тем не менее, это более эффективно для вызова myBitSet.set(10,50) чем писать for (int i=10; i<=50; i++) myBitSet.set(i);

Answer 2

По какой-то причине он не указан в Javadoc, но реализация Oracle - это, конечно, O (1) для получения, установки, перевода и очистки одним параметром; O (N) с двумя параметрами. «Вектор бит» может быть предназначен как подсказка.

Answer 3

Поскольку он использует массив как множество/получаем являются О (1)

Answer 4

Операция набор будет устанавливать биты (fromIndex будет 10 и toIndex будет 49) Он будет перебирать 40 элементов, начиная с 10 до 49. И да, сложность будет равна O (1)