Word-RAM 模型

形式陈述 ​

Word-RAM 由按非负整数地址索引的内存单元组成，每个单元保存一个 $w$ bit 的 word。对输入规模 $n$，通常要求

$$w\ge \lceil {\log }_{2}n\rceil$$

以容纳输入位置和地址，并常进一步固定 $w=\mathrm{\Theta }(\log n)$，防止单字携带超多项式信息。读取或写入一个由 word 给出的地址、word 加减、比较与布尔位运算计为 $O(1)$；乘法、除法、取模和可变位移是否属于单位时间操作，必须由所用版本明确声明。算法时间按这些指令数计，空间应注明按 word 数还是 bit 数报告。

与顺序带上的图灵机公理库图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。相比，Word-RAM 允许一步访问任意已寻址单元；与不限制整数大小的单位成本 RAM 相比，它又用固定字宽约束每步能处理的信息。涉及溢出时，算术可规定为模 $2^w$，或要求中间结果始终落在可表示范围内，两种约定不能混用。

直觉 ​

现实处理器一次处理一小块固定宽度数据，也能按地址直接访问内存。Word-RAM 抽取这两个特征，让数组索引、指针和位运算得到自然的常数成本，同时拒绝把任意长整数塞进一个“单位”后免费运算。它比图灵机方便描述数据结构，又保留足够严格的信息容量边界。

位并行加速来自一个操作同时处理 $w$ 个 bit，而不是把 $w$ 当作无穷。模型结论必须随 $w$ 和操作集一起阅读；同一算法在“允许乘法”与“只允许加法和布尔运算”的 Word-RAM 上，时间界可能不同。

例子与边界 ​

用 word 数组表示长度为 $N$ 的 bitset 时，两个集合求交可对对应 word 做按位 AND，耗时 $O(\lceil N/w\rceil )$；逐 bit 检查则为 $O(N)$。这里的加速有明确上限：每条指令只合并 $w$ 个成员信息。若 $N\le w$，整个集合才可在一个 word 内处理。

随机访问数组 $A[i]$ 为 $O(1)$ 的前提是地址 $i$ 能装入一个 word，且内存规模没有超过可寻址范围。若允许 $w=N$ 且仍把任意 word 运算算作一步，整个 $N$ bit 输入可被打包进一个单元，许多问题会得到不现实的常数步“算法”；固定 $w=\mathrm{\Theta }(\log n)$ 正是为了排除这种作弊。

大整数乘法也展示操作集边界：两个 word 相乘可能产生 $2w$ bit 结果，模型需说明只保留低 $w$ 位、返回两个 word，还是不提供该指令。论文只写“RAM 上 $O(n)$”而未给 word 宽和指令集时，涉及位技巧或整数排序的界通常无法直接比较。

推论与应用 ​

Word-RAM 是哈希、整数排序、位图和大多数数组数据结构的常用分析基线。渐近复杂度公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。在这里以 word 指令为单位；若要换算 bit complexity，必须展开每个 word 操作的成本。它也为更弱的 cell-probe 模型提供参照：后者把内部计算设为免费，只保留访存次数。

工程实现仍会受到缓存、分支、流水线和内存层次影响，Word-RAM 不试图预测这些常数。它负责固定“一个可寻址数据单位有多大、哪些局部操作算一步”，让算法之间的理论比较不依赖无限精度捷径。

参考资料

• Torben Hagerup, “Sorting and Searching on the Word RAM,” in STACS 1998, LNCS 1373, Springer, 1998, pp. 366–398.
• Michael L. Fredman and Dan E. Willard, “Surpassing the Information Theoretic Bound with Fusion Trees,” Journal of Computer and System Sciences 47(3), 1993, pp. 424–436.