C++ битовые логические операции в O(log n)?

Question

C++ битовые логические операции в O(log n)?

Согласно этому посту Производительность выполнения побитовых операций над производительностью битовых наборов составляет O(n), как мне сделать это O(log n). Благодарю.

2

c++11 time-complexity bitwise-operators std-bitset

Источник

user5186709 13 июн '17 в 11:22

1 ответ

Решение

Другие вопросы по тегам c++11 time-complexity bitwise-operators std-bitset

user1173638 13 июн '17 в 11:30 2017-06-13 11:30 · Accepted Answer · 2017-06-13 11:30

Ответ - нет.

Предположим, у вас есть набор n размер. Давайте посмотрим на оператор XOR ^, Очевидно, он должен смотреть на каждый бит в обоих операндах, поэтому 2n поиск. Это приводит к сложности O(n),

Вы можете использовать инструкции ассемблера, которые, например, делают это по 32 бита за раз, поэтому количество операций (n+31)/32, но это не меняет того, что сложность O(n), Ведь сложность рассчитана на n к бесконечности и постоянные факторы не учитываются.