补充资料：随机存取机

随机存取机
random access machine

上，RAM更接近通常计算机，因而，用它来分析算法的时空复杂度，结果更接近实际，也更具实用价值。 随机存取机的结构见图1。它包括一条只读输 人带，一条只写输出带，一个程序 和相应的地址计数器，以及一个无 限存储器。输入带分成小格，每格 可放一整数。每读一个数，输人带 头右移一格。输出带亦分成小格， 每写一数，带头亦右移一格。R气M 的核心是程序。不同的程序代表 不同的RAM。程序是有机组成的 一串指令。地址计数器标明要执 行指令的地址。通常，每执行完一 条指令，地址加1。如遇转移指令， 计数器内容作相应改变。存储器 由无穷多个寄存器r0，r1，r2，…组 成。每个寄存器可放一整数。r0 专作累加器，各种计算在此进行。…亚再同蕊 ┌─┐ │ │ ├─┤┌──┐│ ││程序│├─┤│ ││ ││ │└─┘└──┘ 只写输出带 图1随机存取机 1劝划功的指令系统包含通常计算机的各种基本算术逻辑指令。一个典型的指令系统包括4类12条指令:运算指令(加、减、乘、除)，传输指令(读、写、存、取)，转移指令(无条件转、零转、大于零转)和停机指令。指令可带标号，这有利于实现转移。操作数可用三种方式给定:立即数二i，地址i，间接地址*i。在指令系统中增加一般指令，既不从本质上增加计算能力，也不在数量级上改变问题的复杂度。 RAM可作为语言识别器，但更多时候是用作实现算法的计算机。一个算法的时空复杂度是执行相应RAM程序时实际耗费的时间和存储空间，它们与输入数据的长度有关。这里有两种核算方式:一致方式和对数方式。在一致方式下，每条指令占一个单位时间，每个寄存器占一个单位空间。在对数方式下，时空的核算比较精确，要考虑操作类型和操SU!』1 CUnqUI!随机存取机‘。nd~。一。~。。二__、，、本。算法复杂性的一种重要计算模型，简作RAM。现已证明，RAM在计算能力上与图灵机等价。但在结构作数的位数。一般采用一致方式。 RAM是一种串行计算模型。为分析并行算法复杂度，又提出并行随机存取机P-RAM，例如互斥读写的EREWP一RAM，并发读互斥写的CREWP-R了、M和并发读写的CRCW P-RAM等。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。