指针机模型

记录、入口与允许操作 ​

指针机的内存由记录组成。每条记录含 $O(1)$ 个原子数据字段和 $O(1)$ 个指针字段；算法只持有常数个寄存器及若干指定入口指针。一步可以读取或改写当前记录的字段、沿一个已取得的指针到相邻记录、比较原子键、分配新记录，或把指针设为空/指向另一条已知记录。

关键限制是：记录地址没有可供算法观察的整数值。算法不能对地址加减、从键的 bit 算出某个任意内存位置，也不能把许多指针打包进一字后并行处理。若允许数组，则访问单元也须由已持有的显式引用逐步获得；不能悄悄恢复随机地址计算。

时间按上述原语步数计算，空间按可达记录数及每条记录的常数字段计算。比较是否单位成本、是否允许随机分支、输入键是否为不可分原子，都必须随结论声明；“pointer machine”并不是唯一完全标准化的指令表。

与 Word-RAM、Cell-probe 的关系 ​

Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。把一个 $w$ bit 地址或整数装入机器字，允许由字运算算出地址并作常数时间随机访存。指针机只能沿结构中已经存在的边走到目标，因此通常更弱；Fusion Tree 的 bit 抽取、整数 Trie 的按位分支和直接表寻址都不能原样移植。

Cell-probe 模型公理库单元探测模型Cell-probe model将内部计算设为免费、只统计对 w 位内存单元读写次数的数据结构复杂度模型。则把地址计算和内部计算设为免费，只统计读写的 $w$ bit 单元。它在计算方面比 Word-RAM 还强，却保留 cell 宽与空间参数。指针机下界只约束缺少地址算术的算法，不能自动推出 Word-RAM 或 cell-probe 下界；反过来，在 cell-probe 中成立的访存下界通常能约束相应 Word-RAM 实现。

真例：链表中的第六个记录 ​

设入口指向单链表首节点，要读取第六个节点。指针机必须执行五次 next 追踪；即使节点在现实内存中恰好连续，也不能把首地址加五倍记录大小。若已额外维护每隔四个节点的跳指针，可以更快，但这些跳边占空间且要在更新时维护。

数组 RAM 会用 base + 5 一步定位同一逻辑位置。两种实现的接口都可叫“读取第六项”，成本差异来自访问模型，而不是渐近记号写法。

几何范围搜索中的模型差异 ​

正交范围查询公理库正交范围查询Orthogonal range searching在固定维点集中对轴对齐盒执行报告、计数、判空或聚合查询。的比较树、范围树和指针式报告结构只需沿节点导航，天然适合指针机。Word-RAM 结构还可能把多个秩、位图或微块答案打包在一字中，从而得到更低的对数因子。

因此一个声称“范围报告需 $\mathrm{\Omega }(f(n))$ 时间”的定理必须同时列出：静态还是动态、记录字段数、空间上界、是否允许随机化、查询是否输出 $k$ 个对象，以及下界是在 pointer machine、Word-RAM 还是 cell-probe 上证明。输出本身还需要 $\mathrm{\Omega }(k)$ 次可观察动作。

随机化与可达地址 ​

随机化可以让算法在若干已知指针或局部更新方案中抽样，却不会赋予随机地址访问。若当前只持有节点 $v$ 及其两个孩子指针，随机位可以选择走左或右，但不能凭一个随机整数直接读取尚未通过指针暴露的第 $j$ 条记录。

对固定输入 $x$ 的期望时间应写成

$${\mathbb{E}}_R[T(x;R)],$$

其中每条随机执行仍逐步沿合法指针导航。若对手能观察先前随机选择后再修改结构，还要说明保证针对 oblivious 还是 adaptive 更新序列；隐藏种子本身不是指针机原语。

空间按已分配记录还是当前入口可达记录计量也会影响结论。惰性删除后，断开但尚未回收的节点仍占实际空间；若分析只数可达结构，就必须把垃圾回收过程和成本另行说明。

树导航状态轨迹 ​

在一棵二叉搜索树中查键 $37$，算法从根开始，比较键后只取得左或右孩子指针；即使已经知道目标的数值排名，也不能跳到“中序第 $j$ 个节点”，除非节点额外保存并维护相应跳指针或索引结构。旋转只改常数条链接，因而适合本模型；按层打包整棵微树后查表则属于更强的字级表示。

失败边界 ​

现实机器既能沿指针，也能对地址附近做数组算术，并受缓存层次影响，所以它不严格等于任一抽象模型。Pointer-machine 上较慢不等于现实代码必慢；该模型的用途是隔离“只靠链接结构能做到什么”。

稳定节点身份也不表示垃圾回收免费。删除记录前要保证没有可达指针仍引用它；持久化或共享结构还要把所有权计入空间。若算法把键解释成整数、通过键构造一个表下标，模型已经增强，相关下界必须重新审计。

参考资料

• Robert E. Tarjan, “A Class of Algorithms Which Require Nonlinear Time to Maintain Disjoint Sets,” Journal of Computer and System Sciences 18(2), 1979.
• Bernard Chazelle, “Lower Bounds for Orthogonal Range Searching: I. The Reporting Case,” Journal of the ACM 37(2), 1990.
• Mihai Pătraşcu and Mikkel Thorup, “Time-Space Trade-Offs for Predecessor Search,” STOC, 2006, for model-sensitive comparisons.