根据这篇文章Performance of doing bitwise operations on bitsets性能是 O(n) 我如何使它成为 O(log n)。 谢谢。
最佳答案
答案是你不知道。
假设您有一个 n 大小的位集。
让我们看看异或运算符 ^。
它显然必须查看两个操作数中的每一位，因此它进行 2n 查找。
这导致复杂度为 O(n)。
您可以使用汇编器指令，例如一次做32位，所以操作次数是(n+31)/32，但这并没有改变复杂度是O(n)。在为无穷大计算n 的所有复杂度后，忽略常数因子。
关于c++11 - O(log n)中的c++ bitset逻辑运算？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44520123/