Какова временная сложность копирования bitset?

Question

[F58]

Предположим у нас есть два битсета размера N. Я хочу перенести все значения одного битсета в другой. Какова будет временная сложность данной операции?

Comments

[Армянское Радио]

Вы язык забыли указать

[Илья]

N - это размер в битах?

Answer 1

[Griboks]

Это очень сильно зависит от языка, процессора и памяти. Если мы рассматриваем классическую машину Тьюринга, то копирование одного бита занимает время чтения+записи+сдвига*смещение адресов => k*N.

Если мы рассматриваем ячейки памяти как m бит в одной, то k*N÷m=p*N.
Если мы копируем биты в языке через сдвиг, то еще медленнее первого варианта.