RAM模型
概述
RAM模型（随机存取机模型）是CLRS中用于分析算法运行时间的标准计算模型。它抽象了真实计算机的核心特征，忽略实现细节，为算法的数学分析提供了统一基础。
定义
RAM模型
RAM模型是一种单处理器计算模型，具有以下假设：
- 指令顺序执行（无并行）。
- 基本操作（算术运算、数据移动、控制流）均在常数时间内完成。
- 数据字长不受限制（可存储任意大小的整数）。
- 内存是随机存取的，访问任意地址的数据耗时相同。
核心性质
- 真实模型的抽象：RAM模型忽略了缓存层次、流水线、并行执行等真实计算机的复杂特性。
- 基本操作：算术运算（加、减、乘、除、取余）、数据移动（加载、存储）、控制操作（条件/无条件跳转、子程序调用/返回）均为 。
- 数据规模假设：模型假设每个数据字可以容纳任意大小的整数，实际中需考虑字长限制。
- RAM模型是CLRS中所有算法时间复杂度分析的统一基准。
章节扩展
第2章：入门
- 2.2 算法分析：在RAM模型下分析插入排序的运行时间，将算法执行的操作分为代价不同的类别，分别计数后求和。