c++ 位集逻辑运算的时间复杂度为 O(log n)？

Question

根据这篇文章对位集进行按位运算的性能性能是

O(n)

我如何做到

O(log n)

。

Answer 1

答案是你不知道。

假设您有一个

n

大小的位集。 让我们看看异或运算符

^

。 显然，它必须查看两个操作数中的每一位，因此它会进行

2n

查找。 这导致复杂性为

O(n)

。

您可以使用汇编指令，例如一次执行 32 位，因此操作数为

(n+31)/32

，但这并不能改变复杂性为

O(n)

。在计算

n

到无穷大的所有复杂性后，忽略常数因子。