c++ - 对位集进行位运算的性能

Question

在 C++ 中，如果我对两个位集执行逻辑或(或与)操作，例如:

bitset<1000000> b1, b2;
//some stuff
b1 |= b2;

这是在 O(n) 还是 O(1) 时间内发生的？为什么？

此外，这是否可以在 O(1) 时间内使用 bool 数组来完成？

谢谢。

Answer 1

它必须在 O(N) 时间内发生，因为给定处理器平台在任何给定时间内可以处理的位数是有限的。换句话说，bit-set 越大，每个操作所花费的时间就越长，并且增加将与 bitset 中的位数成线性关系。

使用 bool 类型的数组时，您也会遇到同样的问题。虽然每个单独的操作本身将花费 O(1) 时间，但 N 个对象的总时间将为 O(N)。