c++ - 从 long 转换的 C++ bitset 构造函数的复杂性是多少？

Question

我的猜测是 O(n)，其中 n 是否。位。还是它是恒定的？我的意思是它不应该只是能够从内存中复制位吗？

Answer 1

从数学上讲，long 有一个固定的长度，因此复制它的内容是恒定时间的操作。另一方面，您需要将 bitset 中的其余位清零，并且您无法在相对于 bit_set 的长度小于线性的时间内完成。所以，理论上你不能比 O(n) 做得更好，其中 n 是位集的长度。

我想从渐近复杂性的角度来看，您可以安全地假设构造函数的复杂性与将分配的内存清零相同。

然而，这种分析仅对 n 的巨大值具有一些价值，并且对我来说使用长构造函数来初始化百万位的位集没有多大意义。因此，如果 bitset 的大小与 long 的大小相同，则它实际上是恒定时间。