Foo*_*oon 7 c++ time-complexity bitset std-bitset
我的猜测是O(n),其中n是no.比特.或者它是不变的？我的意思是它不应该只能从内存中复制这些位吗？
从数学上讲,long有一个固定的长度,因此复制它的内容是恒定时间操作.另一方面,您需要将bitset中的其余位清零,并且相对于bit_set的长度,您不能在小于线性的时间内执行此操作.所以,理论上你不能比O(n)做得更好,其中n是bitset的长度.
我想从渐近复杂的角度来看,你可以放心地假设构造函数的复杂性与清零已分配的内存相同.
然而,这种分析仅对n的巨大值有一些价值,并且使用长构造函数初始化百万位的位集对我来说没有多大意义.因此,如果bitset的大小与long的大小相同,则实际上是恒定时间.