15.1计算模型 ·在进行问题的计算复杂性分析之前,首先必须建立求解问题 所用的计算模型,包括定义该计算模型中所用的基本运算。 目的:为了使问题的计算复杂性分析有一个共同的客观尺度。 ·3个基本计算模型: 随机存取机RAM( Random access machine); 随机存取存储程序机RASP( Random Access stored Program Machine) 图灵机( Turing Machine) √这3个计算模型在计算能力上是等价的,但在计算速度上是不 同的2 15.1 计算模型 • 在进行问题的计算复杂性分析之前，首先必须建立求解问题 所用的计算模型，包括定义该计算模型中所用的基本运算。 • 目的: 为了使问题的计算复杂性分析有一个共同的客观尺度。 • 3个基本计算模型： – 随机存取机RAM (Random Access Machine)； – 随机存取存储程序机RASP (Random Access Stored Program Machine) – 图灵机(Turing Machine)。 ✓ 这3个计算模型在计算能力上是等价的，但在计算速度上是不 同的