单元探测模型

形式陈述 ​

Cell-probe 模型把内存划分为至多 $S$ 个 $w$ bit cell。一次 probe 读取或写入一个由算法指定地址的 cell；地址计算和对已读 word 的任意内部计算免费。静态问题先把输入预处理为内存表示，再以查询 probe 数 $t_q$ 衡量访问；动态问题还接收更新，并分别报告 $t_u,t_q$ 的最坏、摊还或期望界。空间 $S$、cell 宽 $w$、随机性和错误概率必须与 probe 界同时声明。

每个 Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。 算法的内存访问序列都给出一个 cell-probe 上界，因为后者免除了其余指令成本；反过来，cell-probe 上界可能依赖不可实现的免费计算，不能直接当作真实运行时间。若在更强的 cell-probe 模型中仍证明需要 $t$ 次访问，则任何对应 Word-RAM 实现也至少需要这些访问。

直觉 ​

模型故意把 CPU 变成无限快，只问数据必须从多少个存储单元中取出或写回。这样得到的下界直指信息在内存中的分布与传递，而不会被某条算术指令的选择绕开。

计算免费不表示信息容量无限。每个 cell 仍只有 $w$ bit，地址范围受空间 $S$ 限制；若同时放松字宽和空间，算法可以把整份答案表塞入一个单元，模型便失去意义。

例子与边界 ​

对宇宙大小 $U$ 的静态集合，可用 $U$ bit 向量表示，按每 $w$ bit 一个 cell 分块。成员查询计算所在 cell 和位偏移，读取一个 cell 后免费检查对应 bit，因此 $t_q=1$、空间 $S=\lceil U/w\rceil$。这个上界展示了空间换访问：若 $U$ 巨大而集合稀疏，位向量空间可能不可接受。

一个自适应查询可以根据第一次读到的内容决定第二个地址；非自适应查询则必须预先确定全部地址。两种模型能力不同，相关下界不能混用。动态结构的更新还会改变未来查询可见的信息，不能拿静态预处理下界直接替代。

声称“查询只需一次 probe”也不保证真实程序快：计算地址可能涉及模型中免费的复杂函数，预处理甚至可能不可行。Cell-probe 负责访存瓶颈，工程成本仍需 Word-RAM 或机器实验补充。

推论与应用 ​

单元探测模型是动态字典、前驱、范围查询和数据结构时间—空间权衡的主要下界框架。通信下界归约公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds将受限算法的执行切成双方可本地模拟的片段，把跨切口状态或访存内容变成消息并保留全部参数。常让一方持查询或更新，另一方持预处理后的内存；每次 probe 的地址与返回的 $w$-bit cell 内容形成交互消息。要从通信下界推出 probe 下界，必须把每轮消息长度、probe 的适应性、空间地址长度与错误概率一并换算，而不能只把“访问了 $t$ 个 cell”写成“通信了 $t$ bit”。

比较结果时必须完整写成参数化陈述，例如“在 $w=\mathrm{\Theta }(\log n)$、多项式空间、最坏查询下”。省略任一条件，都可能把适用于一个存储预算或错误模型的下界错误推广。

参考资料

• Andrew Chi-Chih Yao, “Should Tables Be Sorted?” Journal of the ACM 28(3), 1981, pp. 615–628.
• Peter Bro Miltersen, “Cell Probe Complexity—A Survey,” in Advances in Data Structural Query Processing, American Mathematical Society, 2000, pp. 183–217.