随机存取机器模型_在线百科全书查询

随机存取机器模型

随机存取机器模型是算法分析与计算复杂性理论中重要的串行计算模型，简称 RAM。引进它是为了便于从理论上分析计算机串行程序所耗费的时间、空间等资源。

一个RAM由k个变址器I1,I2,…,Ik、无穷个普通寄存器R0,R1,R2,…和一个有穷长的程序所组成。变址器也是寄存器，每个寄存器中可以存放一个自然数，但只有变址器的内容可以作为间接地址。

RAM的程序使用两种形式的地址。一种是直接地址，形式为Ij(j=1,2,…,k)或Ri(i=0,1,2,…);另一种是间接地址,形式为Ij(j=1,2,…,k)。如果Ij中存的自然数为i，则Ij代表地址Ri。

RAM的指令为下列形式之一:①A←a,表示把地址A的内容改为自然数a;

②A←B,表示把地址A的内容改为地址B的内容;

③A←B*C,表示把地址B中的内容和地址C中的内容作为运算*之后,送入地址A。

这里*可以是自然数的加法、减法、乘法或整数除法。

减法的定义为：若a≥b则等于a-b,否则等于0；

④A←F(B,C)，此处F是一个可以用多带图灵机器在多项式空间和对数多项式的巡回中实现的变换（见多带图灵机模型）。A、B、C可以是直接地址，也可以是间接地址。A是写入地址,B、C是读出地址。

RAM除了可以用以上的指令编程序外,还可以判断某个寄存器或变址器的内容是否为0，以实现条件转移。

变址器是用来实现间接地址的，所以要求在运算过程中变址器中所存的自然数不大于所用到的普通寄存器数目的某个常数倍。

RAM程序的一个例子是：设n个自然数a1,a2,…,an分别存放在R1,R2,…，Rn中，n存放在R0中,要求把这n个数的和计算出来,结果放在R0中。程序如图：

RAM的资源耗费有两种定义方式,即均匀耗费和对数耗费。

是指计算中曾经使用过的寄存器的总数。均匀的时间耗费是指自始至终被执行的指令和转移的总条数。均匀耗费常用于算法分析中。

此时空间耗费指计算中普通寄存器存过的自然数的最大长度之和。时间耗费则指被执行的每条指令的时间耗费之和。而一条指令的时间耗费则被认为与被运算的自然数的长度成正比的。

对于RAM,还可以定义巡回（虚拟的并行时间）。它是计算中周相的总数，而一个周相则是 RAM工作的一个阶段，在此阶段中，没有任何一个普通寄存器先被写入然后又被读出。