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

What's time complexity of swap operator of 2 bitset?
Автор JioFell, история, 6 лет назад, По-английски

In this problem(1070L - Odd Federalization), I used gaussian elimination (O(n^3)) but I have used bitset because I think it will be faster. Finally, I got AC (44701036) but I still don't understand all details of bitset's complexity. Thanks for reading my blog

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

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

See http://www.cplusplus.com/reference/algorithm/swap/. If you swap anything but two arrays, it's constant. That means even bitset or vector.

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

Its O(1) always because it swaps iterators/doesn't actually copy the contents over.

So when you see (sz(a) < sz(b)) swap(a,b) for thing like merge small to large this swap is constant (or else it would not be nlogn overall)

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If I want to swap iteraters of 2 things a and b, I always use a.swap(b). But I can't use that way with bitset so I think it's O(n^3) without reducing by complexity of bitset. Tks you :3 :3

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

It's n/64 because data is stored insidebitset itself (like in an array but unlike in a vector)

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by JioFell (previous revision, new revision, compare).

→ Ответить