@F58

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

Предположим у нас есть два битсета размера N. Я хочу перенести все значения одного битсета в другой. Какова будет временная сложность данной операции?
  • Вопрос задан
  • 111 просмотров
Решения вопроса 1
Griboks
@Griboks
Это очень сильно зависит от языка, процессора и памяти. Если мы рассматриваем классическую машину Тьюринга, то копирование одного бита занимает время чтения+записи+сдвига*смещение адресов => k*N.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы