Блог пользователя nkamzabek

Автор nkamzabek, история, 5 лет назад, По-английски

Despite I am big fan of bitsets, I don't even know what is the exact time complexity. I think operation OR, XOR and etc. works in $$$O(\frac{size}{64})$$$, the explanation is that solutions which used it got AC. But on the other hand, I have read in blogs that there would be $$$32$$$ instead of $$$64$$$. Please help me, what is the exact time complexity for each function and which factors it depends on and explain work principles.

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

GNU libstdc++ represents the bitset by an array of type unsigned long. Using custom invocation you can check that on Codeforces, we have sizeof(unsigned long) == 4, so 4*8=32 bits are handled in one operation and thus we get the bound $$$O(\frac{\mathrm{size}}{32})$$$.

Note that most modern (64-bit) systems will have sizeof(unsigned long) == 8, indeed yielding $$$O(\frac{\mathrm{size}}{64})$$$, so Codeforces is a bit of an exception.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In java, I've seen it's implementation. It's long array(64 bit). so the complexity of iterating over all masks is size/64. You can compute the time complexity of different operations.

»
5 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Were you actually ignorant of it!? It is oviously, isn't it?

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +26 Проголосовать: не нравится

$$$O(\frac{size}{64})$$$ or $$$O(\frac{size}{32})$$$ is not the normal way of using big $$$O$$$ notation.

A better way is to use $$$O(\frac{size}{w})$$$ instead of $$$O(\frac{size}{constnumber})$$$.Whether $$$w$$$ equals to $$$32$$$ or $$$64$$$ is not important.