从 long 转换的 C++ bitset 构造函数的复杂性是什么？
What is the complexity of C++ bitset constructor that converts from long?
我的猜测是 O(n)，其中 n 是编号。位。或者它是常数 w.r.t。 ñ？我的意思是它不应该只是能够从内存中复制位吗？
从数学上讲，long 的长度是固定的，因此复制它的内容是常量时间操作。另一方面，您需要将位集中的其余位清零，并且您无法在相对于 bit_set 的长度的小于线性时间内完成。所以，理论上你不能比 O(n) 做得更好，其中 n 是位集的长度。
我想从渐近复杂性的角度来看，您可以安全地假设构造函数的复杂性与将分配的内存清零相同。
然而，此分析仅对 n 的巨大值有一定价值，使用长构造函数初始化百万位的位集对我来说没有多大意义。所以，如果 bitset 的大小与 long 的大小在同一尺度上，它实际上是恒定时间的。
我的猜测是 O(n)，其中 n 是编号。位。或者它是常数 w.r.t。 ñ？我的意思是它不应该只是能够从内存中复制位吗？
从数学上讲，long 的长度是固定的，因此复制它的内容是常量时间操作。另一方面，您需要将位集中的其余位清零，并且您无法在相对于 bit_set 的长度的小于线性时间内完成。所以，理论上你不能比 O(n) 做得更好，其中 n 是位集的长度。
我想从渐近复杂性的角度来看，您可以安全地假设构造函数的复杂性与将分配的内存清零相同。
然而，此分析仅对 n 的巨大值有一定价值，使用长构造函数初始化百万位的位集对我来说没有多大意义。所以，如果 bitset 的大小与 long 的大小在同一尺度上，它实际上是恒定时间的。