c++11 - O(log n)中的c++ bitset逻辑运算？

Question

根据这篇文章Performance of doing bitwise operations on bitsets性能是 O(n) 我如何使它成为 O(log n)。谢谢。

Answer 1

答案是你不知道。

假设您有一个 n 大小的位集。让我们看看异或运算符 ^。它显然必须查看两个操作数中的每一位，因此它进行 2n 查找。这导致复杂度为 O(n)。

您可以使用汇编器指令，例如一次做32位，所以操作次数是(n+31)/32，但这并没有改变复杂度是O(n)。在为无穷大计算n 的所有复杂度后，忽略常数因子。