复制位集的复杂度是多少？和位掩码一样吗？
What is the complexity of copying a bitset? Is it the same as that for a bit mask?
我想了解与 bitset 相比在性能或位掩码方面的差异。我知道复制一个位掩码需要 O(1)，因为它基本上只表示为一个整数，所以位集也是如此，其中每个值由 1 位表示，因此使其大小与位掩码相同？或者复制一个位集需要 O(N) 时间。
我正在尝试衡量位掩码的有用性，特别是在竞争性编程的背景下。
谢谢！
复制位掩码不是 constant-time。它的位数为 O(n)，就像任何其他必须接触结构的每个元素一次的操作一样。
一般来说，C++ bitset 对象的行为应该与 hand-rolled 整数位掩码相当。例如，对 bitset<32> 的操作应该与对 uint32_t.
的等效按位操作执行相同
当你说某事是 O(N) 时，你是在谈论它的 渐近复杂性。 "Asymptotic" 在这里很重要。这意味着你是说事物的实际复杂性 接近 N 的一些线性函数，因为 N 无限制地增加。
所以，了解 N 是什么很重要。在 bit-mapped 集合的情况下，它可能是可以在（或不在）集合中的唯一元素的数量。但是，当您谈论适合 int 的数据结构时，N 是什么？在那种情况下，N 怎么能无限增加呢？
如果事物不 缩放，则谈论其渐近复杂性没有任何意义。 int 不缩放。 int 就是 int。说 int 上的操作是 O(1) 或 O(anythingelse) 就此而言。
我想了解与 bitset 相比在性能或位掩码方面的差异。我知道复制一个位掩码需要 O(1)，因为它基本上只表示为一个整数，所以位集也是如此，其中每个值由 1 位表示，因此使其大小与位掩码相同？或者复制一个位集需要 O(N) 时间。
我正在尝试衡量位掩码的有用性，特别是在竞争性编程的背景下。
谢谢！
复制位掩码不是 constant-time。它的位数为 O(n)，就像任何其他必须接触结构的每个元素一次的操作一样。
一般来说，C++ bitset 对象的行为应该与 hand-rolled 整数位掩码相当。例如，对 bitset<32> 的操作应该与对 uint32_t.
当你说某事是 O(N) 时，你是在谈论它的 渐近复杂性。 "Asymptotic" 在这里很重要。这意味着你是说事物的实际复杂性 接近 N 的一些线性函数，因为 N 无限制地增加。
所以，了解 N 是什么很重要。在 bit-mapped 集合的情况下，它可能是可以在（或不在）集合中的唯一元素的数量。但是，当您谈论适合 int 的数据结构时，N 是什么？在那种情况下，N 怎么能无限增加呢？
如果事物不 缩放，则谈论其渐近复杂性没有任何意义。 int 不缩放。 int 就是 int。说 int 上的操作是 O(1) 或 O(anythingelse) 就此而言。