B 计算模型

01B1-1 性能测度

Data Structure + Algorithm （DSA）

度量

To measure is to know.

If you can not measure it, you can not improve it.

1. 引入理想、统一、分层次的尺度
2. 运用该尺度，以测量 DSA 的性能

01B1-2 问题规模

算法分析

两个主要方面：

正确性：功能与问题要求一致？

成本：运行时间 + 储存空间。如何度量？如何比较？

对实例进行分析意义不大

问题实例的规模，往往是决定计算成本的主要因素

规模接近，计算成本也接近；规模越大，计算成本也上升

01B1-3 最坏情况

在规模为 n 的所有实例中，只关注最坏（成本最高） 的实例。

01B1-4 理想模型

为客观评价，抽象出理想模的平台或型进行对比

01B2-1 图灵机

Turing Machine （TM）

01B2-2 图灵机实例

01B3-1 RAM 模型

Random Access Machine （RAM）

寄存器顺序编号，总数没有限制

将算法的运行时间转化为算法需要执行的基本操作次数

01B3-2 RAM 实例

#待整理笔记