haskell - 为什么 IntSet 查找是 O(min(n,W))，而不是 O(1)？

Question

根据https://hackage.haskell.org/package/containers-0.5.7.1/docs/Data-IntSet.html ，member 函数查找 intSet 中是否有一个 int，需要 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 的数据结构来获取灵感。)

Answer 1

正如 @DerekElkins 在评论中所说，仅读取单个无限大小的整数至少需要 O(log a) 时间。因此，在任何意义上都不可能做得更好。

如果没有固定大小的基元，基本上没有什么是 O(1) 的。