Word-RAM 模型

现实处理器一次处理一小块固定宽度数据，也能按地址直接访问内存。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 的字级比较、移位和位运算直接决定前驱查询公理库Word-RAM 前驱问题Predecessor problem在 Word-RAM 的有限整数宇宙中维护有序集合，并查询不大于给定键的最大成员。能在多大字长下跳过逐键扫描，也让简洁数据结构公理库简洁数据结构Succinct data structure以接近对象族信息论下界的 bit 数保存对象，同时直接支持查询。在接近信息下界的空间内并行处理一个 word 的位模式。哈希、整数排序、位图和大多数数组结构都以此为分析基线。渐近复杂度公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。在这里计 word 指令；若要换算 bit complexity，必须展开每个 word 操作的成本。更强的 cell-probe 模型把内部计算设为免费、只保留访存次数，因此其下界也适用于 Word-RAM。

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