algorithm - 细胞探针模型

Question

来自算法第 4 版

问：什么是细胞探针模型？
一种计算模型，我们只计算对足够大以容纳输入的随机存取存储器的访问，并认为所有其他操作都是免费的。

我想理解这个说法。请通过示例帮助我理解这一点。

Answer 1

问题：确定输入中是否出现数字 0，它必须是一个排序列表 L。通过二分查找，cell-probe 复杂度正好是ceil(log2(len(L) + 1))，因为这是 L 的多少个元素我们必须看看。我们不需要 big-O 来说明这个结果，因为调度探测器的开销没有被计算在内。

问题：确定输入是否是可满足的布尔公式（SAT）。尽管这个问题是 NP 完全的，因此不知道是否有多项式时间算法，但我们确实知道单元探测复杂度最多为 n，因为一种算法是读取整个输入并进行指数时间计算这不会进行任何探测。

由于细胞探针模型允许不切实际的计算量，它几乎总是被用作不可能结果的设置，也就是说，即使我们拥有世界上所有的时间和空间，也没有算法可以访问少于这么多的输入。