在位集上执行按位运算的性能

Question

在C++中,如果我在两个位集上执行逻辑OR(或AND),例如:

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

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

此外,这可以在O(1)时间内使用一系列bool来完成吗？

谢谢.

Answer 1

它必须在O(N)时间内发生,因为在给定的处理器平台的任何给定的时间块中可以处理有限数量的比特.换句话说,比特集越大,每个操作将花费的时间越长,并且增加将相对于比特集中的比特数是线性的.

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