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

About Bitset in c++ !!
Автор eGoMask, 2 года назад, По-английски

with bitset<2001> bits[1000][1000];

what time complexity of operation shifting ( =<< or =>> ) !!

and what is Memory ?

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

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

Standard doesn't says anything about it, but I think it's safe to assume, that bitsets inside just static array of unsigned numbers. So shifting must be just loop over that array. So complexity would be O(N / bits_per_number). And what memory you are asking?

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

    so time complexity this operation bits[ 1 ][1] |= ( bits[ 0 ][0] >> 1 ) take O( 1 ) !

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

      O(1) with big constant (if bitset stores 32bit numbers that it would be ceil(2001 / 32) = 66)

      → Ответить