为什么 IntSet 查找是 O(min(n,W))，而不是 O(1)？
Why is IntSet lookup O(min(n,W)), and not O(1)?
根据https://hackage.haskell.org/package/containers-0.5.7.1/docs/Data-IntSet.html，member函数查找一个int是否在IntSet中，需要O(min(n,W))时间，其中n是IntSet中的元素个数，在32位机器上W=32，在64位机器上W=64。
我想在实践中，W 可能小于 n，所以函数将是 O(W) 时间。
在实践中（在固定架构上），O(W) 是常数，因此这个函数可能运行得非常快（或者至少不会随着 n 变慢）。
但是，理论上，这并没有那么快。如果我们允许无限大小的整数 a₁,...,aₙ（并令 W = log a，其中 a = maxₚ aₚ，则此函数在 O(log a) 中运行。为什么我们不能使用散列并实现此功能的 O(1) 摊销成本？
（上下文：我正在做一个算法作业，对于我的问题伪代码的一部分，我想要一个数据结构来检查一个整数是否在常数时间内是我的集合的成员，不管集合中整数的数量，或集合中整数的大小。我尝试查找 Haskell Set 类数据结构以获取灵感。）
正如@DerekElkins 在评论中所说，仅读取一个无限大小的整数最少需要 O(log a) 时间。因此，无论如何都不可能做得更好。
如果你没有固定大小的图元，基本上什么都不是 O(1)。
根据https://hackage.haskell.org/package/containers-0.5.7.1/docs/Data-IntSet.html，member函数查找一个int是否在IntSet中，需要O(min(n,W))时间，其中n是IntSet中的元素个数，在32位机器上W=32，在64位机器上W=64。
我想在实践中，W 可能小于 n，所以函数将是 O(W) 时间。
在实践中（在固定架构上），O(W) 是常数，因此这个函数可能运行得非常快（或者至少不会随着 n 变慢）。
但是，理论上，这并没有那么快。如果我们允许无限大小的整数 a₁,...,aₙ（并令 W = log a，其中 a = maxₚ aₚ，则此函数在 O(log a) 中运行。为什么我们不能使用散列并实现此功能的 O(1) 摊销成本？
（上下文：我正在做一个算法作业，对于我的问题伪代码的一部分，我想要一个数据结构来检查一个整数是否在常数时间内是我的集合的成员，不管集合中整数的数量，或集合中整数的大小。我尝试查找 Haskell Set 类数据结构以获取灵感。）
正如@DerekElkins 在评论中所说，仅读取一个无限大小的整数最少需要 O(log a) 时间。因此，无论如何都不可能做得更好。
如果你没有固定大小的图元，基本上什么都不是 O(1)。